WebAssemblyの多倍長演算ではCarryの扱いが重要　それ以上速くするにはclangの_Extlntに期待

WebAssemblyではどう計算するか

光成滋生氏（以下、光成）：本題に戻ってWebAssemblyなのですが、レジスタは32bitと64bitのレジスタをもっています。加算は64bit＋64bitで、結果は64bitになります。Carryはもっていません。乗算は32bit×32bitの64bitです。128bitに出力する命令はありません。素直なCでできる範囲しかありません。詳しい資料はここに載っています。

Carry演算をエミュレートしないといけません。どうやってやるかですが、やることはそんなに難しくありません。64bitのxとyを足して、65bitになって、そのCarryがなくなったということは、2つの足した値が足す前よりもcに小さくなっているとCarryが発生するということです。

この命令に対応するWebAssemblyのコードは、lt_uというunsignedのless thanという意味でxとyを比較してxがyより小さかったら1になる、そうでなければ0を使います。他にle (less than or equal)とかequalとか同様にsignedに対する命令や、selectという条件演算子相当の命令もあります。

64bitなので、ここでTをunit64_tとして、入力がx、y、cの時に出力をx＋yとadoc相当をエミュレートしようとすると、xにCarryに足してその値が元より小さくなっていたらCarryが発生。yに足し込んで、そのあともう1回Carryを更新します。

1回の計算で、addが3回でlt_uが2回。今までのIntelの命令だと1命令でできていたのがこのぐらいかかるのでけっこうヘビーです。しかもlt_uみたいなのは多分JIT化して内部的にはcmpとかcmovとかになるのでもっと重くなります。

32bit単位ベースで実装するとどうなるか

数年間これを使って、64bitベースで実装していたのですが、ふと32bit単位になったらどうなるのかなと思いました。32bitのxとyに対して、ゼロ拡張してから足した値を32bit右シフトします。するとこれはCarryが入ってきます。先ほどの例でいうと、xとyとcに対してxを64bit拡張してからyとcを足します。下位32bitを取り出して、上位32bitをCarryします。

32bitのCPUでCarryがない場合は同じことをしようと思っても、64bit拡張するとC言語的に内部的に同じことをするので無駄ですが、WebAssemblyは32bitのレジスタと64bitのレジスタの2つもっているので、ちょっと様子が違います。

1回の要素辺りaddが2回、シフトが1回でゼロ拡張が2回です。64bit単位でやるところを32bit単位でやると2倍の要素になります。例えば256の場合、64bitだと4つでいけたのが32bitだと8個いるので演算回数は増えます。マイクロベンチを取ってみて、もしかしたら速くなるかなと思ったんですが、微妙に64bit版のほうが速いです。

JITがどうなるかわからないので、ブレが大きいです。昔考えた時は、ここで遅くなったので諦めたのですが、もう少し考えてみました。32bit単位の場合、このCarryのｃは先ほどは1bitだったのですが、32bitあるわけですね。ということは、途中のCarryをまとめて足してから操作できます。

ここは非常に複雑な話になるので、ざっくりと結果だけ言います。256bit×256bitで512bitの乗算をやって、64bit単位で実装をしてみました。64×64から128はもっていないので、32×32の64を組み合わせて実装しました。それと今回32bit単位で実装したものを比較すると、1割から2割ぐらい速くなりました。これはちょっと意外だったのですがおもしろい結果だと思っています。

最初に紹介したペアリングは、乗算がプロファイルのかなりの部分を占めるので、これだけ速くなると全体も速くなってかなり効果が大きいです。詳しい人のために紹介しておくと、Karatsuba法という、加算を増やす代わりに乗算の回数を4回から3回に減らすという方法があります。32bit単位でやるとけっこう長い範囲になるので効果があるかなと思ったのですが、WebAssemblyの実装だと加算のほうが重くなってしまうので、このぐらいのものは使わないほうが速かったです。メインは32bitでやったほうがうまくいったということです。

unit128_tやunit1024_tが実装できる言語拡張「_Extlnt」

ここからはちょっと違う話をします。clang-11から_Extlntという機能が導入されています。これはuint128_tやuint1024_tが実装できる言語拡張で、typedef unsigned_Extlnt(256)とやるとunit256_tが作れます。しかも今までの整数のようにキャストして読み込んで、512bitにゼロ拡張して掛け算すると、これだけで256bitの乗算ができます。

今までunitしていたのはclangが生成してくれるという非常に夢のような世界が始まっています。こういう機能をC++にも入れようという提案があって、解説しているものを要約したのもあります。将来はもしかしたら入ってくるかもしれないです。

今のところ残念なところがいくつかあって、x64でベンチマークを取ってみました。clang-11-Ofastでやりました。mclは私が実装しているライブラリで、職人的にたぶん世界最速でadox、adcxを使っています。clangはmulxまでしか使わないです。なおかつレジスタスピルをやっているのでけっこう遅いです。square演算だと半分ぐらい変わってしまいます。

でも将来clangが進化したら、これぐらいになってくるのかなという気はします。WebAssemblyですが、コンパイルはできますがリンクはできない状況です。_multi3がないと言われます。これはclangを使っていてよく見ます。clang-8の頃は自分でこの_multi3を実装して、うまいこと動いていたのですが、clang-8の時に動いていたものをclang-11で使うと、function signature mismatchと出て動きませんでした。

時間がなくてこれ以上調べていないです。まあ、割と仕様がよく変わるので仕様はよくわからないです。昔は使おうとするとLLVMが落ちていたので、ここまで生なエラーにはなっていたのでだいぶ改善されています。

実際にC、C++でwasmを生成するには、emcc（Emscriten）かclangでやります。私は主にemccを使っています。理由はいくつかあって、標準ライブラリに対応していてmallocも使えます。使わないようにしているのですが、clangだとまだまだ生なコンパイラです。

関数exportする時のやり方がちょっと違ったり、名前に"_"が付く・付かないだったり。emccで便利なのは、SINGLE_FILEとやるとWebAssemblyのバイトコード、base64コードを指定して埋め込んだjsを1個にして作ってくれるのでWebPackなどで、使いやすいです。clangはLLVM IRを使えて便利ですが、ちょっとおかしいところが多いです。

まとめます。多倍長演算ではCarryの扱いが重要です。x64には便利な命令がいろいろ書かれていて、高速化に関与しています。wasmはCarryを扱う命令がないので、これは素直に記述する範囲でしかできません。あるいはCで記述して、十分高速なコードになります。それ以上速くできない感じです。clangの_Extlntに期待しています。

個人的にはemccがLLVM IRや_Extlntをサポートしたらclangに移行してみようかなと思います。発表は以上です。ありがとうございました。

司会者：ありがとうございました。では質疑に移ります。これはサイド的な質問ですが、「wasmで暗号処理するというのは、side channel攻撃に対する考慮はどれくらいすべき・しているものでしょうか？」いかがでしょうか？

光成：難しい質問ですね。スマートフォンとかでクライアントで使う時はside channelをほとんど気にしなくていいのかなという気もします。何か攻撃するツールが入っていたらやられるというのはありますが、そうなっていたらもうside channelではなくて、どのレイヤーでもヤバいことになっているので、あまりそこは気にしなくていいのかなと思います。

ただ先ほどの紹介のように、サーバーサイドでAssemblyを使う時はや多少は気にしていかないといけないかなと思います。私自身はそんなに気にしていないのですが、最初のコード生成の時に定数時間で計算するモードを追加したりは多少やています。遅くなるけれども、より安全にしたい時はそちらのモードを使って対策をしている人が多いと思います。そこは程度によるんですけどね。やればやるほど遅くなるので。

司会者：ありがとうございます。「modのpはどうしているのかが気になる」というツイートがありました。

光成：すみません。今回は足し算・掛け算の説明だけで、modは2、3倍しゃべらないといけないのでざっくり消してしまっています。別の学会でしゃべっている資料を公開しているので、資料に興味があればそちらをご覧になってください。

司会者：ありがとうございます。もう1つ「32bitごとの演算をSIMD proposalを使ってやる予定はありますか？」という質問があります。

光成：そうですね。wasmにもSIMDが入ってくるとかあるんですが、先ほど言ったようにツールがまだこなれていません。アルゴリズムのところで悩むならいいんですが、使い勝手のほうでリソースを食ってしまうのはあまり好きではないので、まだ様子見という感じです。

司会者：ありがとうございます。