如何实现前端高性能计算？
爱情de悬崖
7年前
<p>最近做一个项目，里面涉及到在前端做大量计算，直接用js跑了一下，大概需要15s的时间， 也就是用户的浏览器会卡死15s，这个完全接受不了。</p> <p>虽说有V8这样牛逼的引擎，但大家知道js并不适合做CPU密集型的计算，一是因为单线程，二是因为动态语言。我们就从这两个突破口入手，首先搞定“单线程”的限制，尝试用WebWorkers来加速计算。</p> <p><strong>前端高性能计算之一：WebWorkers</strong> 什么是WebWorkers</p> <p>简单说， <a href="/misc/goto?guid=4959755513439751260" rel="nofollow,noindex">WebWorkers</a> 是一个HTML5的新API，web开发者可以通过此API在后台运行一个脚本而不阻塞UI，可以用来做需要大量计算的事情，充分利用CPU多核。</p> <p>大家可以看看这篇文章介绍https://www.html5rocks.com/en/tutorials/workers/basics/， 或者 <a href="/misc/goto?guid=4959755513537301648" rel="nofollow,noindex">对应的中文版</a> 。</p> <p>引用</p> <p>The Web Workers specification defines an API for spawning background scripts in your web application. Web Workers allow you to do things like fire up long-running scripts to handle computationally intensive tasks, but without blocking the UI or other scripts to handle user interactions.</p> <p>可以打开 <a href="/misc/goto?guid=4959755513641942577" rel="nofollow,noindex">这个链接</a> 自己体验一下WebWorkers的加速效果。</p> <p>现在浏览器基本都 <a href="/misc/goto?guid=4959755513732710251" rel="nofollow,noindex">支持WebWorkers</a> 了。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/95d97be96fc64acc065697d3c5a381f0.png"></p> <p>Parallel.js</p> <p>直接使用 <a href="/misc/goto?guid=4959755513439751260" rel="nofollow,noindex">WebWorkers</a> 接口还是太繁琐，好在有人已经对此作了封装： <a href="/misc/goto?guid=4959755513838232541" rel="nofollow,noindex">Parallel.js</a> 。</p> <p>注意 <a href="/misc/goto?guid=4959755513838232541" rel="nofollow,noindex">Parallel.js</a> 可以通过node安装：</p> <pre> $ npm install paralleljs</pre> <p>不过这个是在node.js下用的，用的node的cluster模块。如果要在浏览器里使用的话， 需要直接应用js:</p> <pre> <script src="parallel.js"></script></pre> <p>然后可以得到一个全局变量，Parallel。Parallel提供了map和reduce两个函数式编程的接口，可以非常方便的进行并发操作。</p> <p>我们先来定义一下我们的问题，由于业务比较复杂，我这里把问题简化成求1-1,0000,0000的和，然后在依次减去1-1,0000,0000，答案显而易见： 0！ 这样做是因为数字太大的话会有数据精度的问题，两种方法的结果会有一些差异，会让人觉得并行的方法不可靠。此问题在我的mac pro chrome61下直接简单地跑js运行的话大概是1.5s（我们实际业务问题需要15s，这里为了避免用户测试的时候把浏览器搞死，我们简化了问题）。</p> <pre> const N = 100000000;// 总次数1亿 // 更新自2017-10-24 16：47：00 // 代码没有任何含义，纯粹是为了模拟一个耗时计算，直接用 // for (let i = start; i <= end; i += 1) total += i; // 有几个问题，一是代码太简单没有任何稍微复杂一点的操作，后面用C代码优化的时候会优化得很夸张，没法对比。 // 二是数据溢出问题， 我懒得处理这个问题，下面代码简单地先加起来，然后再减掉，答案显而易见为0，便于测试。 function sum(start, end) { let total = 0; for (let i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total += i; } else if (i % 5 == 0 || i % 7 == 1) { total += i / 2; } } for (let i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total -= i; } else if (i % 5 == 0 || i % 7 == 1) { total -= i / 2; } } return total; } function paraSum(N) { const N1 = N / 10;//我们分成10分，没分分别交给一个web worker，parallel.js会根据电脑的CPU核数建立适量的workers let p = new Parallel([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) .require(sum); return p.map(n => sum((n - 1) * 10000000 + 1, n * 10000000))// 在parallel.js里面没法直接应用外部变量N1 .reduce(data => { const acc = data[0]; const e = data[1]; return acc + e; }); } export { N, sum, paraSum }</pre> <p>代码比较简单，我这里说几个刚用的时候遇到的坑。</p> <p><strong>require所有需要的函数</strong></p> <p>比如在上诉代码中用到了sum，你需要提前require(sum)，如果sum中由用到了另一个函数f，你还需要require(f)，同样如果f中用到了g，则还需要require(g)，直到你require了所有用到的定义的函数。。。。</p> <p><strong>没法require变量</strong></p> <p>我们上诉代码我本来定义了N1，但是没法用</p> <p><strong>ES6编译成ES5之后的问题以及Chrome没报错</strong></p> <p>实际项目中一开始我们用到了ES6的特性：数组解构。本来这是很简单的特性，现在大部分浏览器都已经支持了，不过我当时配置的babel会编译成ES5，所以会生成代码_slicedToArray，大家可以在线上Babel测试，然后Chrome下面始终不work，也没有任何报错信息，查了很久，后来在Firefox下打开，有报错信息：</p> <pre> ReferenceError: _slicedToArray is not defined</pre> <p>看来Chrome也不是万能的啊。。。</p> <p>大家可以在 <a href="/misc/goto?guid=4959755513942415570" rel="nofollow,noindex">此Demo页面</a> 测试， 提速大概在4倍左右，当然还是得看自己电脑CPU的核数。 另外我后来在同样的电脑上Firefox55.0.3（64位）测试，上诉代码居然只要190ms！！！在Safari9.1.1下也是190ms左右。。。</p> <p>Refers</p> <ul> <li><a href="/misc/goto?guid=4959755514031864356" rel="nofollow,noindex">https://developer.mozilla.org/zh-CN/docs/Web/API/WebWorkersAPI/Usingwebworkers</a></li> <li><a href="/misc/goto?guid=4959755514129009746" rel="nofollow,noindex">https://www.html5rocks.com/en/tutorials/workers/basics/</a></li> <li><a href="/misc/goto?guid=4959755513838232541" rel="nofollow,noindex">https://parallel.js.org/</a></li> <li><a href="/misc/goto?guid=4959755514232043071" rel="nofollow,noindex">https://johnresig.com/blog/web-workers/</a></li> <li><a href="/misc/goto?guid=4959755514328481687" rel="nofollow,noindex">http://javascript.ruanyifeng.com/htmlapi/webworker.html</a></li> <li><a href="/misc/goto?guid=4959755514416327147" rel="nofollow,noindex">http://blog.teamtreehouse.com/using-web-workers-to-speed-up-your-javascript-applications</a></li> </ul> <p><strong>前端高性能计算之二：asm.js & webassembly</strong></p> <p>前面我们说了要解决高性能计算的两个方法，一个是并发用WebWorkers，另一个就是用更底层的静态语言。</p> <p>2012年，Mozilla的工程师 <a href="/misc/goto?guid=4958877633663440241" rel="nofollow,noindex">Alon Zakai</a> 在研究 <a href="/misc/goto?guid=4958202556373490960" rel="nofollow,noindex">LLVM</a> 编译器时突发奇想：能不能把C/C++编译成Javascript，并且尽量达到Native代码的速度呢？于是他开发了 <a href="/misc/goto?guid=4959755514566249791" rel="nofollow,noindex">Emscripten</a> 编译器，用于将C/C++代码编译成Javascript的一个子集 <a href="/misc/goto?guid=4958964949747011447" rel="nofollow,noindex">asm.js</a> ，性能差不多是原生代码的50%。大家可以看看这个PPT。</p> <p>之后Google开发了[Portable Native Client][PNaCI]，也是一种能让浏览器运行C/C++代码的技术。 后来估计大家都觉得各搞各的不行啊，居然Google, Microsoft, Mozilla, Apple等几家大公司一起合作开发了一个面向Web的通用二进制和文本格式的项目，那就是 <a href="/misc/goto?guid=4959741138207899058" rel="nofollow,noindex">WebAssembly</a> ，官网上的介绍是：</p> <p>引用</p> <p>WebAssembly or wasm is a new portable, size- and load-time-efficient format suitable for compilation to the web.</p> <p>所以，WebAssembly应该是一个前景很好的项目。我们可以看一下 <a href="/misc/goto?guid=4959755514725568641" rel="nofollow,noindex">目前浏览器的支持情况</a> ：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/aee8d4d3a2d0a15482652faca421ec1a.png"></p> <p>安装Emscripten</p> <p>访问https://kripken.github.io/emscripten-site/docs/getting_started/downloads.html</p> <p>1. 下载对应平台版本的SDK</p> <p>2. 通过emsdk获取最新版工具</p> <p> </p> <pre> bash # Fetch the latest registry of available tools. ./emsdk update # Download and install the latest SDK tools. ./emsdk install latest # Make the "latest" SDK "active" for the current user. (writes ~/.emscripten file) ./emsdk activate latest # Activate PATH and other environment variables in the current terminal source ./emsdk_env.sh</pre> <p>3. 将下列添加到环境变量PATH中</p> <pre> ~/emsdk-portable ~/emsdk-portable/clang/fastcomp/build_incoming_64/bin ~/emsdk-portable/emscripten/incoming</pre> <p>4. 其他</p> <p>我在执行的时候碰到报错说LLVM版本不对，后来参考文档配置了LLVM_ROOT变量就好了，如果你没有遇到问题，可以忽略。</p> <pre> LLVM_ROOT = os.path.expanduser(os.getenv('LLVM', '/home/ubuntu/a-path/emscripten-fastcomp/build/bin'))</pre> <p>5. 验证是否安装好</p> <p>执行emcc -v，如果安装好会出现如下信息：</p> <pre> emcc (Emscripten gcc/clang-like replacement + linker emulating GNU ld) 1.37.21 clang version 4.0.0 (https://github.com/kripken/emscripten-fastcomp-clang.git 974b55fd84ca447c4297fc3b00cefb6394571d18) (https://github.com/kripken/emscripten-fastcomp.git 9e4ee9a67c3b67239bd1438e31263e2e86653db5) (emscripten 1.37.21 : 1.37.21) Target: x86_64-apple-darwin15.5.0 Thread model: posix InstalledDir: /Users/magicly/emsdk-portable/clang/fastcomp/build_incoming_64/bin INFO:root:(Emscripten: Running sanity checks)</pre> <p>Hello, WebAssembly!</p> <p>创建一个文件hello.c：</p> <pre> #include <stdio.h> int main() { printf("Hello, WebAssembly!\n"); return 0; }</pre> <p>编译C/C++代码：</p> <pre> emcc hello.c</pre> <p>上述命令会生成一个a.out.js文件，我们可以直接用Node.js执行：</p> <pre> node a.out.js</pre> <p>输出：</p> <pre> Hello, WebAssembly!</pre> <p>为了让代码运行在网页里面，执行下面命令会生成hello.html和hello.js两个文件，其中hello.js和a.out.js内容是完全一样的。</p> <pre> emcc hello.c -o hello.html</pre> <pre> ➜ webasm-study md5 a.out.js MD5 (a.out.js) = d7397f44f817526a4d0f94bc85e46429 ➜ webasm-study md5 hello.js MD5 (hello.js) = d7397f44f817526a4d0f94bc85e46429</pre> <p>然后在浏览器打开hello.html，可以看到页面：；；</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/a4dc249bbbf8f6719e44da011ad9c40b.png"></p> <p>前面生成的代码都是asm.js，毕竟Emscripten是人家作者Alon Zakai最早用来生成asm.js的，默认输出asm.js也就不足为奇了。当然，可以通过option生成wasm，会生成三个文件：hello-wasm.html, hello-wasm.js, hello-wasm.wasm。</p> <pre> emcc hello.c -s WASM=1 -o hello-wasm.html</pre> <p>然后浏览器打开hello-wasm.html，发现报错TypeError: Failed to fetch。原因是wasm文件是通过XHR异步加载的，用file:////访问会报错，所以我们需要启一个服务器。</p> <pre> npm install -g serve serve .</pre> <p>然后访问http://localhost:5000/hello-wasm.html，就可以看到正常结果了。</p> <p>调用C/C++函数</p> <p>前面的Hello, WebAssembly!都是main函数直接打出来的，而我们使用WebAssembly的目的是为了高性能计算，做法多半是用C/C++实现某个函数进行耗时的计算，然后编译成wasm，暴露给js去调用。</p> <p>在文件add.c中写如下代码：</p> <pre> #include <stdio.h> int add(int a, int b) { return a + b; } int main() { printf("a + b: %d", add(1, 2)); return 0; }</pre> <p>有两种方法可以把add方法暴露出来给js调用。</p> <p>通过命令行参数暴露API</p> <pre> emcc -s EXPORTED_FUNCTIONS="['_add']" add.c -o add.js</pre> <p>注意方法名add前必须加_。 然后我们可以在Node.js里面这样使用：</p> <pre> // file node-add.js const add_module = require('./add.js'); console.log(add_module.ccall('add', 'number', ['number', 'number'], [2, 3]));</pre> <p>执行node node-add.js会输出5。如果需要在web页面使用的话，执行：</p> <pre> emcc -s EXPORTED_FUNCTIONS="['_add']" add.c -o add.html</pre> <p>然后在生成的add.html中加入如下代码：</p> <pre> <button onclick="nativeAdd()">click</button> <script type='text/javascript'> function nativeAdd() { const result = Module.ccall('add', 'number', ['number', 'number'], [2, 3]); alert(result); } </script></pre> <p>然后点击button，就可以看到执行结果了。</p> <p>Module.ccall会直接调用C/C++代码的方法，更通用的场景是我们获取到一个包装过的函数，可以在js里面反复调用，这需要用Module.cwrap，具体细节可以参看 <a href="/misc/goto?guid=4959755514823925601" rel="nofollow,noindex">文档</a> 。</p> <pre> const cAdd = add_module.cwrap('add', 'number', ['number', 'number']); console.log(cAdd(2, 3)); console.log(cAdd(2, 4));</pre> <p>定义函数的时候添加EMSCRIPTEN_KEEPALIVE</p> <p>添加文件add2.c。</p> <pre> #include <stdio.h> #include <emscripten.h> int EMSCRIPTEN_KEEPALIVE add(int a, int b) { return a + b; } int main() { printf("a + b: %d", add(1, 2)); return 0; }</pre> <p>执行命令：</p> <pre> emcc add2.c -o add2.html</pre> <p>同样在add2.html中添加代码：</p> <pre> <button onclick="nativeAdd()">click</button> <script type='text/javascript'> function nativeAdd() { const result = Module.ccall('add', 'number', ['number', 'number'], [2, 3]); alert(result); } </script></pre> <p>但是，当你点击button的时候，报错：</p> <pre> Assertion failed: the runtime was exited (use NO_EXIT_RUNTIME to keep it alive after main() exits)</pre> <p>可以通过在main()中添加emscripten_exit_with_live_runtime()解决：</p> <pre> #include <stdio.h> #include <emscripten.h> int EMSCRIPTEN_KEEPALIVE add(int a, int b) { return a + b; } int main() { printf("a + b: %d", add(1, 2)); emscripten_exit_with_live_runtime(); return 0; }</pre> <p>或者也可以直接在命令行中添加-s NO_EXIT_RUNTIME=1来解决，</p> <pre> emcc add2.c -o add2.js -s NO_EXIT_RUNTIME=1</pre> <p>不过会报一个警告：</p> <pre> exit(0) implicitly called by end of main(), but noExitRuntime, so not exiting the runtime (you can use emscripten_force_exit, if you want to force a true shutdown)</pre> <p>所以建议采用第一种方法。</p> <p>上述生成的代码都是asm.js，只需要在编译参数中添加-s WASM=1中就可以生成wasm，然后使用方法都一样。</p> <p>用asm.js和WebAssembly执行耗时计算</p> <p>前面准备工作都做完了， 现在我们来试一下用C代码来优化前一篇中提过的问题。代码很简单：</p> <pre> // file sum.c #include <stdio.h> // #include <emscripten.h> long sum(long start, long end) { long total = 0; for (long i = start; i <= end; i += 3) { total += i; } for (long i = start; i <= end; i += 3) { total -= i; } return total; } int main() { printf("sum(0, 1000000000): %ld", sum(0, 1000000000)); // emscripten_exit_with_live_runtime(); return 0; }</pre> <p>注意用gcc编译的时候需要把跟emscriten相关的两行代码注释掉，否则编译不过。 我们先直接用gcc编译成native code看看代码运行多块呢？</p> <pre> ➜ webasm-study gcc sum.c ➜ webasm-study time ./a.out sum(0, 1000000000): 0./a.out 5.70s user 0.02s system 99% cpu 5.746 total ➜ webasm-study gcc -O1 sum.c ➜ webasm-study time ./a.out sum(0, 1000000000): 0./a.out 0.00s user 0.00s system 64% cpu 0.003 total ➜ webasm-study gcc -O2 sum.c ➜ webasm-study time ./a.out sum(0, 1000000000): 0./a.out 0.00s user 0.00s system 64% cpu 0.003 total</pre> <p>可以看到有没有优化差别还是很大的，优化过的代码执行时间是3ms!。really？仔细想想，我for循环了10亿次啊，每次for执行大概是两次加法，两次赋值，一次比较，而我总共做了两次for循环，也就是说至少是100亿次操作，而我的mac pro是2.5 GHz Intel Core i7，所以1s应该也就执行25亿次CPU指令操作吧，怎么可能逆天到这种程度，肯定是哪里错了。想起之前看到的 <a href="/misc/goto?guid=4959755514923035385" rel="nofollow,noindex">一篇rust测试性能的文章</a> ，说rust直接在编译的时候算出了答案， 然后把结果直接写到了编译出来的代码里， 不知道gcc是不是也做了类似的事情。在知乎上 <a href="/misc/goto?guid=4959755515011958263" rel="nofollow,noindex">GCC中-O1 -O2 -O3 优化的原理是什么？</a> 这篇文章里， 还真有loop-invariant code motion（LICM）针对for的优化，所以我把代码增加了一些if判断，希望能“糊弄”得了gcc的优化。</p> <pre> #include <stdio.h> // #include <emscripten.h> // long EMSCRIPTEN_KEEPALIVE sum(long start, long end) { long sum(long start, long end) { long total = 0; for (long i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total += i; } else if (i % 5 == 0 || i % 7 == 1) { total += i / 2; } } for (long i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total -= i; } else if (i % 5 == 0 || i % 7 == 1) { total -= i / 2; } } return total; } int main() { printf("sum(0, 1000000000): %ld", sum(0, 100000000)); // emscripten_exit_with_live_runtime(); return 0; }</pre> <p>执行结果大概要正常一些了。</p> <pre> ➜ webasm-study gcc -O2 sum.c ➜ webasm-study time ./a.out sum(0, 1000000000): 0./a.out 0.32s user 0.00s system 99% cpu 0.324 total</pre> <p>ok，我们来编译成asm.js了。</p> <pre> #include <stdio.h> #include <emscripten.h> long EMSCRIPTEN_KEEPALIVE sum(long start, long end) { // long sum(long start, long end) { long total = 0; for (long i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total += i; } else if (i % 5 == 0 || i % 7 == 1) { total += i / 2; } } for (long i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total -= i; } else if (i % 5 == 0 || i % 7 == 1) { total -= i / 2; } } return total; } int main() { printf("sum(0, 1000000000): %ld", sum(0, 100000000)); emscripten_exit_with_live_runtime(); return 0; }</pre> <p>执行：</p> <pre> emcc sum.c -o sum.html</pre> <p>然后在sum.html中添加代码</p> <pre> <button onclick="nativeSum()">NativeSum</button> <button onclick="jsSumCalc()">JSSum</button> <script type='text/javascript'> function nativeSum() { t1 = Date.now(); const result = Module.ccall('sum', 'number', ['number', 'number'], [0, 100000000]); t2 = Date.now(); console.log(`result: ${result}, cost time: ${t2 - t1}`); } </script> <script type='text/javascript'> function jsSum(start, end) { let total = 0; for (let i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total += i; } else if (i % 5 == 0 || i % 7 == 1) { total += i / 2; } } for (let i = start; i <= end; i += 1) { if (i % 2 == 0 || i % 3 == 1) { total -= i; } else if (i % 5 == 0 || i % 7 == 1) { total -= i / 2; } } return total; } function jsSumCalc() { const N = 100000000;// 总次数1亿 t1 = Date.now(); result = jsSum(0, N); t2 = Date.now(); console.log(`result: ${result}, cost time: ${t2 - t1}`); } </script></pre> <p>另外，我们修改成编译成WebAssembly看看效果呢？</p> <pre> emcc sum.c -o sum.js -s WASM=1</pre> <table> <tbody> <tr> <td>Browser</td> <td>webassembly</td> <td>asm.js</td> <td>js</td> </tr> <tr> <td>Chrome61</td> <td>1300ms</td> <td>600ms</td> <td>3300ms</td> </tr> <tr> <td>Firefox55</td> <td>600ms</td> <td>800ms</td> <td>700ms</td> </tr> <tr> <td>Safari9.1</td> <td>不支持</td> <td>2800ms</td> <td>因不支持ES6我懒得改写没测试</td> </tr> </tbody> </table> <p>感觉Firefox有点不合理啊， 默认的JS太强了吧。然后觉得webassembly也没有特别强啊，突然发现emcc编译的时候没有指定优化选项-O2。再来一次：</p> <pre> emcc -O2 sum.c -o sum.js # for asm.js emcc -O2 sum.c -o sum.js -s WASM=1 # for webassembly</pre> <table> <tbody> <tr> <td>Browser</td> <td>webassembly -O2</td> <td>asm.js -O2</td> <td>js</td> </tr> <tr> <td>Chrome61</td> <td>1300ms</td> <td>600ms</td> <td>3300ms</td> </tr> <tr> <td>Firefox55</td> <td>650ms</td> <td>630ms</td> <td>700ms</td> </tr> </tbody> </table> <p>居然没什么变化， 大失所望。号称asm.js可以达到native的50%速度么，这个倒是好像达到了。但是今年 <a href="/misc/goto?guid=4959755515109247394" rel="nofollow,noindex">Compiling for the Web with WebAssembly (Google I/O '17)</a> 里说WebAssembly是1.2x slower than native code，感觉不对呢。 <a href="/misc/goto?guid=4958964949747011447" rel="nofollow,noindex">asm.js</a> 还有一个好处是，它就是js，所以即使浏览器不支持，也能当成不同的js执行，只是没有加速效果。当然 <a href="/misc/goto?guid=4959741138207899058" rel="nofollow,noindex">WebAssembly</a> 受到各大厂商一致推崇，作为一个新的标准，肯定前景会更好，期待会有更好的表现。</p> <p>Refers</p> <p>人工智能是最近两年绝对的热点，而这次人工智能的复兴，有一个很重要的原因就是计算能力的提升，主要依赖于GPU。去年Nvidia的股价飙升了几倍，市面上好点的GPU一般都买不到，因为全被做深度学习以及挖比特币的人买光了</p> <p> </p> <p>来自：http://www.iteye.com/news/32773</p> <p> </p>