Clever Geek Handbook

ブラウザーおよびWebAssemblyでの64ビット演算

WebAssemblyは積極的に開発されており、設定のチェックボックスをオンにすることで、Chrome CanaryとFirefox Nightlyでアセンブルされたモジュールを試すことができるようになりました。







WebAssembly、asm.js、PNaCl、およびネイティブコードで、64ビットの数値と算術計算のパフォーマンスを比較します。 WebAssemblyで現在利用できるツールを見て、近い将来を見てみましょう。







免責事項



WebAssemblyは現在開発中です。1か月後には記事が古くなる可能性があります。 この記事の目的は、興味のある人のために、状況について話すことです。







TL; DR



デモ グラフィックス







アルゴリズム



ベンチマークとして、最近ブラウザーで計算する必要があったArgon2を見てみましょう。

Argon2（ github 、 Habr ）は、鍵生成の比較的新しい暗号化関数（鍵導出関数、KDF）であり、 パスワードハッシュコンペティションで優勝しました 。







64ビット演算に基づいています。1回の反復で約60M回実行される関数は次のとおりです。 







uint64_t fBlaMka(uint64_t x, uint64_t y) { const uint64_t m = UINT64_C(0xFFFFFFFF); const uint64_t xy = (x & m) * (y & m); return x + y + 2 * xy; } uint64_t rotr64(const uint64_t w, const unsigned c) { return (w >> c) | (w << (64 - c)); }


asm.jsでの実装の問題



すべてが単純なように思えます。たとえば、sse命令を呼び出すことによって、argon2ネイティブコードで行われるように、2つの64ビット数を取り、乗算します。 しかし、ブラウザではそうではありません。







V8では、ご存知のように、64ビット整数はないため、より良いものがないことを示すすべての算術演算は、31ビットのsmi（小さな整数）によってエミュレートされます。 これは非常に遅いです。 Unityの開発者から繰り返し言及され、64ビット型がWebAssembly MVPに含まれていたため、最初は後で延期したかったのですが、非常に遅くていです。







2つのint64の乗算関数用にasm.jsによって生成されたコードを見てみましょう。これは、compiler-rtの関数です。 







 function ___muldsi3($a, $b) { $a = $a | 0; $b = $b | 0; var $1 = 0, $2 = 0, $3 = 0, $6 = 0, $8 = 0, $11 = 0, $12 = 0; $1 = $a & 65535; $2 = $b & 65535; $3 = Math_imul($2, $1) | 0; $6 = $a >>> 16; $8 = ($3 >>> 16) + (Math_imul($2, $6) | 0) | 0; $11 = $b >>> 16; $12 = Math_imul($11, $1) | 0; return (tempRet0 = (($8 >>> 16) + (Math_imul($11, $6) | 0) | 0) + ((($8 & 65535) + $12 | 0) >>> 16) | 0, 0 | ($8 + $12 << 16 | $3 & 65535)) | 0; }


ここにあり 、ここにJavaScriptがあります 。 ちなみに実装は非常に優れており、V8でdeopt-sを引き起こすことはありません。 念のためチェックしてみましょう：







asm.jsをコンパイルし、変数名の変更を無効にしてコード内の関数名を読み取り可能にし、 IR Hydraでアーティファクトを開くことができるフラグを使用して実行します（npm i -g node-irhydraをインストールするだけです）：









ご覧のとおり、V8は__muldi3の__muldsi3関数もインライン化し__muldi3



。 また、この関数のアセンブラコードを確認することもできます。







IR 
 v50 EnterInlined ___muldsi3 Tagged i71 Constant 65535 Smi i72 Bitwise BIT_AND i234 i71 TaggedNumber i76 Bitwise BIT_AND i236 i71 TaggedNumber t79 LoadContextSlot t47[13] Tagged t82 CheckValue t79 0x3d78a90c3b59 <JS Function imul (SharedFunctionInfo 0x3d78a9058f91)> Tagged i83 Mul i76 i72 TaggedNumber i88 Constant 16 Smi i89 Shr i234 i88 TaggedNumber i94 Shr i83 i88 TaggedNumber i100 Mul i76 i89 TaggedNumber i104 Add i94 i100 TaggedNumber i111 Shr i236 i88 TaggedNumber i118 Mul i111 i72 TaggedNumber i125 Shr i104 i88 TaggedNumber i131 Mul i111 i89 TaggedNumber i135 Add i125 i131 TaggedNumber i142 Bitwise BIT_AND i104 i71 TaggedNumber i145 Add i142 i118 TaggedNumber i151 Shr i145 i88 TaggedNumber i153 Add i135 i151 TaggedNumber t238 Change i153 i to t v158 StoreContextSlot t47[12] = t238 changes[ContextSlots] Tagged v159 Simulate id=319 var[3] = t47, var[1] = i234, var[2] = i236, var[6] = i83, var[5] = t6, var[8] = i104, var[4] = t6, var[10] = i118, var[9] = t6, var[7] = t6, push i153 Tagged i163 Add i104 i118 TaggedNumber i166 Shl i163 i88 TaggedNumber i170 Bitwise BIT_AND i83 i71 TaggedNumber i172 Bitwise BIT_OR i166 i170 TaggedNumber v179 LeaveInlined Tagged v180 Simulate id=172 pop 1 / push i172 Tagged v181 Goto B3 Tagged


アセンブラー

140 andl r8,0xffff

;; <@ 43、＃72>ギャップ

147 movq r9、rdx

;; <@ 44、＃76>ビットi

150 andl r9,0xffff

;; <@ 48、＃79> load-context-slot

170 movq r11、[r11 + 0x77]

;; <@ 50、＃82>チェック値

174 movq r10,0x3d78a90c3b59 ;; オブジェクト：0x3d78a90c3b59 <JS Function imul（SharedFunctionInfo 0x3d78a9058f91）>

184 cmpq r11、r10

187 jnz 968

;; <@ 51、＃82>ギャップ

193 movq rdi、r9

;; <@ 52、＃83> mul-i

196イムルRDI、R8

;; <@ 53、＃83>ギャップ

200 movq r11、rax

;; <@ 54、＃89> shift-i

203 shrl r11、16

;; <@ 55、＃89>ギャップ

207 movq r12、rdi

;; <@ 56、＃94> shift-i

210 shrl r12、16

;; <@ 58、＃100> mul-i

214 imull r9、r11

;; <@ 60、＃104> add-i

218 addl r9、r12

;; <@ 61、＃104>ギャップ

221 movq r12、rdx

;; <@ 62、＃111> shift-i

224 shrl r12、16

;; <@ 63、＃111>ギャップ

228 movq r14、r12

;; <@ 64、＃118> mul-i

231 imull r14、r8

;; <@ 65、＃118>ギャップ

235 movq r8、r9

;; <@ 66、＃125> shift-i

238 shrl r8、16

;; <@ 68、＃131> mul-i

242 imull r12、r11

;; <@ 70、＃135> add-i

246 addl r12、r8

;; <@ 71、＃135>ギャップ

249 movq r8、r9

;; <@ 72、＃142>ビットi

252 andl r8,0xffff

;; <@ 74、＃145> add-i

259 addl r8、r14

;; <@ 76、＃151> shift-i

262 shrl r8、16

;; <@ 78、＃153> add-i

266 addl r8、r12

;; <@ 80、＃238> smi-tag

269 movl r12、r8

272 shlq r12、32

;; <@ 84、＃158> store-context-slot

289 movq [r11 + 0x6f]、r12

;; <@ 86、＃163> add-i

293リアルr8、[r9 + r14 * 1]

;; <@ 88、＃166> shift-i

297 shll r8、16

;; <@ 90、＃170>ビットi

301 andl rdi、0xffff

;; <@ 92、＃172>ビットi

307 orl rdi、r8







Chromeは、タイプアノテーションでできるような最適なコードを生成しません; V8開発者は、基本的にasm.js jsサブセットをサポートしたくありません。 対照的に、コードが検証に合格した場合、「asmを使用」と表示されるFirefoxは、いくつかのチェックを破棄します。その結果、結果のコードは3..4倍速くなります。







ネイティブコードと比較して、ChromeとSafariは50倍遅い、Firefox 12です。

IE11は非常に低速ですが、ChromeとFirefoxの中間の設定でasm.jsを有効にしたEdgeが有効になっています。









Webassssembly



WebAssemblyでこのコードをコンパイルします。 これを行うにはいくつかの方法があります：最初に、C / C ++ Source⇒asm2wasm⇒WebAssemblyを試してください（簡潔にするために一部のパラメーターは除外されています）： 







 cmake \ -DCMAKE_TOOLCHAIN_FILE=~/emsdk_portable/emscripten/incoming/cmake/Modules/Platform/Emscripten.cmake \ -DCMAKE_C_FLAGS="-O3" \ -DCMAKE_EXE_LINKER_FLAGS="-O3 -g0 -s 'EXPORTED_FUNCTIONS=[\"_argon2_hash\"]' -s BINARYEN=1" && cmake --build .


asen.jsのビルドと同じツールチェーンを使用して、binaryen（ -s BINARYEN=1



）を使用することを指定できます。

出力では次のようになります。









wastファイルをwasm バイナリ形式に変換します 。 







 ~/binaryen/bin/wasm-as argon2.wast > argon2.wasm


ブラウザでモジュールを使用します



wasmモジュールを呼び出す以外にjsラッパーは何ができますか？ 









 global.Module = { print: log, printErr: log, setStatus: log, wasmBinary: loadedWasmBinaryAsArrayBuffer, wasmJSMethod: 'native-wasm,', asmjsCodeFile: 'dist/argon2.asm.js', wasmBinaryFile: 'dist/argon2.wasm', wasmTextFile: 'dist/argon2.wast' }; var xhr = new XMLHttpRequest(); xhr.open('GET', 'dist/argon2.wasm', true); xhr.responseType = 'arraybuffer'; xhr.onload = function() { global.Module.wasmBinary = xhr.response; // load script }; xhr.send(null);


ここで、コンパイルされたアーティファクトの場所を示し、ログを接続して、コードを実行する方法を決定します。 次の方法から選択できます。









複数のメソッドをコンマでリストすると、最初に成功したものが実行されます。 デフォルトの方法はnative-wasm,interpret-binary



binaryです。つまり、wasmがあるかどうかを確認し、ない場合は、バイナリモジュールを解釈します。







正常にロードすると、エクスポートされたすべてのメソッドがModule



オブジェクトに表示されます。







使用例（ 完全 ）： 







 var pwd = Module.allocate(Module.intArrayFromString('password'), 'i8', Module.ALLOC_NORMAL); // ... var res = Module._argon2_hash(t_cost, m_cost, parallelism, pwd, pwdlen, salt, saltlen, hash, hashlen, encoded, encodedlen, argon2_type, version); var encodedStr = Module.Pointer_stringify(encoded);


Firefox Nightlyでは、wasmモジュールの内部を見ることができます。











Chromeにはwasmを表示するツールはまだありません。モジュールはエディターにも表示されません。 しかし、彼らはまた、リリースのビューソースを作成することを約束します。







Binaryenからの通訳



Binaryenは、テキスト形式の.wastおよびバイナリ形式の.wasm形式を実行できるインタープリターを生成します。 method



をinterpret-s-expr



またはinterpret-binary



設定することで試すことができます。 これまでのところ、インタプリタは非常に遅いため、ハッシュの計算を待たずに、より少ない反復回数で推定しました。 Chromeでは7秒、IE11では45秒でしたが、30分になりました。







コード品質



どのようなコードを取得したかを見てみましょう。 .wastが非常に小さくなるように簡単なテストを作成しました。 ここにあります： 







 uint64_t fBlaMka(uint64_t x, uint64_t y) { const uint64_t m = UINT64_C(0xFFFFFFFF); const uint64_t xy = (x & m) * (y & m); return x + y + 2 * xy; } int exp_fBlaMka() { for (unsigned i = 0; i < 100000000; i++) { if (fBlaMka(i, i) == i - 1) { return 1; } } return 0; }


.wastを見て、関数を見つけてください。 







 (func $_exp_fBlaMka (result i32) (local $0 i32) (set_local $0 (i32.const 0) ) (loop $while-out$0 $while-in$1 (if #  ,     (i32.and (i32.eq (call $___muldi3 #   (call $_i64Add (call $_bitshift64Shl (get_local $0) (i32.const 0) (i32.const 1) ) (i32.load (i32.const 168) ) (i32.const 2) (i32.const 0) ) (i32.load (i32.const 168) ) (get_local $0) (i32.const 0) ) (i32.add (get_local $0) (i32.const -1) ) ) # ...


I32再び？ これはなぜですか？ asm.jsをコンパイルしてwasmコードを取得したことを思い出してください。したがって、ここではi64は表示されません。 このようなコードの実行にも長い時間がかかることは驚くことではありません。







ただし、Chromeの実行速度はFirefoxと同じであり、Firefoxのasm.jsよりも少し高速です。







LLVM WebAssemblyバックエンド



次に、より複雑な方法、C / C ++ソース⇒WebAssembly LLVMバックエンド⇒s2wasm⇒WebAssemblyを試してみましょう。







LLVMは、スクリプトを使用せずにこれを行うことでWebAssemblyを生成することを学びました。 しかし、彼はこれまでのところひどくそれを行っており、結果のモジュールは常に機能するとは限りません。







WebAssemblyサポートを使用してLLVMをビルドします。 







 cmake -G Ninja -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD=WebAssembly .. && ninja


コンパイルに含めます： 







 export EMCC_WASM_BACKEND=1 -DCMAKE_EXE_LINKER_FLAGS="-s WASM_BACKEND=1"


emscriptenで異なるバージョンのLLVMを試すには、〜/ .emscripten、LLVM_ROOTでパスを指定します。 そして...モジュールをブラウザにロードする際にエラーが発生します。







emccで使用されるfastcompフォークではなく、アップストリームのバニラLLVMを使用して、次のようにコンパイルできます。 







 clang -emit-llvm --target=wasm32 -S perf-test.c llc perf-test.ll -march=wasm32 ~/binaryen/bin/s2wasm perf-test.s > perf-test.wast ~/binaryen/bin/wasm-as perf-test.wast > perf-test.wasm


また落ちる。 おそらく、V8のwastからの無駄は、binaryenではなくsexpr -wasm-prototypeで構築する必要がありますが、それでも助けにはなりません。







ただし、簡単なテストはそれ自体で機能し、少なくとも1つの関数を例として使用してパフォーマンスを評価できます。 結果の.wastを見てみましょう： 







 (func $fBlaMka (param $0 i64) (param $1 i64) (result i64) (i64.add (i64.add (get_local $1) (get_local $0) ) (i64.mul (i64.and (i64.shl (get_local $0) (i64.const 1) ) (i64.const 8589934590) ) (i64.and (get_local $1) (i64.const 4294967295) ) ) ) )


やったー、i64！ ブラウザにダウンロードして、以前のバージョンと比較して時間を評価します。 







 console.time('i64'); Module._exp_fBlaMka(); console.timeEnd('i64'); i32: 1851.5ms i64: 414.49ms


明るい未来では、64ビット演算の速度が数倍向上しています。







スレッディング



PthreadはMVP WebAssemblyには含まれていません。 後でのみ表示されます。 一般的に、来年に何が起こるかを言うのはまだ難しいです-答えはノーです。 ただし、WebAssemblyは、デモページで確認できるように、パフォーマンスを低下させることなく、Webワーカーで問題なく使用できます。







PNaCl



次に、パフォーマンスをPNaClと比較します。 PNaClは、GoogleがChrome向けに開発したバイナリコード形式でもあり、デフォルトで有効になっています。 一度他のブラウザでサポートすることになっていたが、 Mozillaはオファーを拒否したが 、他の人は考えなかった。 離陸しませんでした。







したがって、PNaClは実行時にjitする.pexeです。 簡単なモジュールを作成しましょう。 







 class Argon2Instance : public pp::Instance { public: virtual void HandleMessage(const pp::Var& msg) { pp::VarDictionary req(msg); //     int t_cost = req.Get(pp::Var("time")).AsInt(); // ... int res = argon2_hash(t_cost, m_cost, parallelism, pwd, pwdlen, salt, saltlen, hash, hashlen, encoded, encodedlen, argon2_type == 1 ? Argon2_i : Argon2_d, version); pp::VarDictionary reply; reply.Set(pp::Var("res"), res); PostMessage(reply); //   } };


これを呼び出すには、 <embed>



ページに.pexeを埋め込み、メッセージを送信します。 







 //      listener.addEventListener('message', e => console.log(e.data)); //   moduleEl.postMessage({ pwd: 'password', ... });


WASMとは異なり、PNaClは64ビット型とpthreadの両方をサポートするようになったため、動作がはるかに高速になり、実行速度はネイティブコードの1.5..2倍になりました。 しかし、それはクロムのみです。 唯一の悲しいことはロード時間です。これは数秒であり、ユーザーがPNaClを最初に使用した場合、30秒程度の非常に大きな数字に成長する可能性があります。







グラフ



さまざまな環境での平均コード実行時間：









ダウンロードと初回実行：









コードサイズ



コードサイズ、KiB 解説
asm.js 109 完全にすべてのjsニック
Webassssembly 43 .wasmのみ、ラッパーなし
PNaCl 112 .pexe


node.jsはどうですか？



node.jsでは、ネイティブコードのコンパイルが非常に簡単になりました。バインディングをいくつか追加するだけです。 V8が何らかのバージョンに更新されると、node.jsを--expose-wasm



付けて--expose-wasm



でき（そのサポートは実験段階です）、ノードでもwasmを使用できます。 V8は十分に古いため、起動するまで。







結論



Firefoxではasm.jsを、ChromeではPNaClを使用するのが賢明です。 WASMはすでに十分に優れており、MVPの頃にはLLVMのコンパイルが思い浮かぶでしょうが、もちろん、ナイトリービルドでもデフォルトではオフになっています。 ただし、wasmのパフォーマンスはすでに示されており、i64サポートがなくてもasm.jsの速度を超えています。







参照資料





More articles:


All Articles