WebAssembly SIMD を pixelmatch に適用した #

ついに Safari にWebAssembly SIMDが来るとのことで試してみた。
対象はpixelmatchあたりが手頃そうなのでこれを対象とする。

Safari as the last browser finally supports WebAssembly SIMD 🎉 pic.twitter.com/HVX3gZTrRi

— CryZe (@CryZe107) December 23, 2022

目次

モチベーション #

• RustからWebAssembly SIMDをどう使うのか学びたい
• WebAssembly SIMDによるパフォーマンスの変化を観測したい

またreg-viz/reg-cliがpixelmatchに依存しており、reg-viz/reg-cliをRust,wasm製にしたいという活動の一環でもある。

成果物 #

https://github.com/bokuweb/pixelmatch-rs/pixelmatch-simd-wasm

前提 #

• x86と記載されているものはMacBook Pro (13-inch, 2019) 2.8 GHz クアッドコアIntel Core i7を使用したものとする
• armと記載されているものはMacBook Air（M2、2022）Apple M2を使用したものとする
• Node.jsはv19.4.0を使用したものとする
• Chromeはv109を、Firefoxは110をSafariはTechnologyPreviewの16.4を使用したものとする

pixelmatch とは #

pixelmatchはピクセルレベルで画像の差分を取るライブラリでオリジナルはmapbox/pixelmatch、今回はこれをRustに porting したものを対象とする。

Example Outputを見ると、どういうものかは分かりやすい。

SIMD への変更 #

どのような変更となるか一例をあげておく。

fn rgb2y(r: f32, g: f32, b: f32) -> f32 {
    r * 0.29889531 + g * 0.58662247 + b * 0.11448223
}

たとえば上記のような任意のピクセルの各色に定数を乗算する既存関数は以下のように書き換えることができる。

const V_Y: v128 = f32x4(0.29889531, 0.58662247, 0.11448223, 1.0); 

fn rgb2y(px: v128) -> f32 {
    let v = f32x4_mul(px, V_Y); 
    sum(v)
}

ただし、事前にv128に変換する必要があり今回は以下のように前段で詰替えを行っている。

let p = f32x4(
    img1[pos] as f32,
    img1[pos + 1] as f32,
    img1[pos + 2] as f32,
    img1[pos + 3] as f32,
);

この要領でv128を使えそうな箇所を書き換えていった。

機械語の確認 #

書き換えたはいいが、SSE/AVX/NEONがちゃんと使用されているか見ておく必要がある。
命令の詳細はわからないが、今回はひとまずそれらが使用されていそうか確認した。

確認は以下で行える。(最初はd8を使用していたが、nodeのほうが楽なことに気づきこちらを使用している)

node --print-wasm-code --experimental-wasm-simd --no-liftoff simd.js

またhelpには見当たらなかった（気がした）が--no-liftoffをつけることによりturbofanでの結果を出力するようにしている。これがないとcompilerがliftoffになってしまう。

x86 #

前述したrgb2y相当な箇所を探してみたら以下を見つけた。
3f162ce4が0.58662247に相当、3e9908ceが0.29889531に相当するのでvmovq xmm1,r10, vpinsrq xmm1,xmm1,r10,0x1などでxmm1にV_Yを移し、vmulps xmm0,xmm0,xmm1で乗算をしているように見える。

調べてみるとfloat32 ベクトルを乗算します。対応するインテル® AVX 命令は VMULPS です。とあるので確かにAVX命令が使用されていそうなことが確認できた。

0x30f2b684e0cc    ac  c4e37921c110   vinsertps xmm0,xmm0,xmm1,0x10
0x30f2b684e0d2    b2  49bace08993ee42c163f REX.W movq r10,0x3f162ce43e9908ce
0x30f2b684e0dc    bc  c4c1f96eca     vmovq xmm1,r10
0x30f2b684e0e1    c1  49baa975ea3d00000000 REX.W movq r10,0x3dea75a9
0x30f2b684e0eb    cb  c4c3f122ca01   vpinsrq xmm1,xmm1,r10,0x1
0x30f2b684e0f1    d1  c4e37921c220   vinsertps xmm0,xmm0,xmm2,0x20
0x30f2b684e0f7    d7  c5f859c1       vmulps xmm0,xmm0,xmm1
0x30f2b684e0fb    db  c5fa16c8       vmovshdup xmm1,xmm0
0x30f2b684e0ff    df  c5f828d0       vmovaps xmm2,xmm0
0x30f2b684e103    e3  c5f258ca       vaddss xmm1,xmm1,xmm2
0x30f2b684e107    e7  c5f812c0       vmovhlps xmm0,xmm0,xmm0
0x30f2b684e10b    eb  c5f258c0       vaddss xmm0,xmm1,xmm0
0x30f2b684e10f    ef  41bacdcccc3d   movl r10,0x3dcccccd

arm #

該当しそうなのは以下だろうか。3e9908ceらしきものがあるし、その後fmul v0.4s, v0.4s, v1.4sされているので間違ってはいなさそうだ。

vmulのような命令が出てくるのかと想像していたが、どうもこれによるとprefixは削除されたらしくオペランドがv0.4s, v0.4s, v1.4sことからもNEONが使用されているようなことが確認できた。

0x1d92955dd25c    9c  d28119d0       movz x16, #0x8ce
0x1d92955dd260    a0  f2a7d330       movk x16, #0x3e99, lsl #16
0x1d92955dd264    a4  f2c59c90       movk x16, #0x2ce4, lsl #32
0x1d92955dd268    a8  f2e7e2d0       movk x16, #0x3f16, lsl #48
0x1d92955dd26c    ac  4e080e01       dup v1.2d, x16
0x1d92955dd270    b0  d28eb530       movz x16, #0x75a9
0x1d92955dd274    b4  f2a7bd50       movk x16, #0x3dea, lsl #16
0x1d92955dd278    b8  4e181e01       mov v1.d[1], x16
0x1d92955dd27c    bc  6e140440       mov v0.s[2], v2.s[0]
0x1d92955dd280    c0  6e21dc00       fmul v0.4s, v0.4s, v1.4s
0x1d92955dd284    c4  5e0c0401       mov s1, v0.s[1]
0x1d92955dd288    c8  5e040402       mov s2, v0.s[0]
0x1d92955dd28c    cc  1e212841       fadd s1, s2, s1
0x1d92955dd290    d0  5e140400       mov s0, v0.s[2]
0x1d92955dd294    d4  1e212800       fadd s0, s0, s1

ベンチマーク #

以下にはbanchmarkjsを使用して取得した平均値を記載している。
差分生成にかかった時間なので小さいほど高速だといえる。

画像は以下のようなケースを用意した。(diffはimg1,img2をpixelmatchにかけた場合に得られる結果)

	img1	img2	diff
ケース 1 800x578
ケース 2 7488x5242
ケース 3 10000x8000

ケース 1 #

x86 #

arm #

ケース 2 #

x86 #

arm #

ケース 3 #

x86 #

arm #

• Safari/JavaScriptにおいて異常な値が観測されたが本筋ではないので Chart からは除外した

所感 #

すくなくとも手持ちのx86とarmでは傾向に差異が見られた。x86ではJavaScriptが最速となるケースが多く、armではWebAssembly(SIMD無し)が最速となるケースが多く見られたように思う。

共通して言えるのはWebAssembly SIMDによる高速化は上記のケースではあまり観測されなかった点だ。WebAssembly SIMDが最速となったのはいずれもケース 3 で、x86ではChrome、armではNode.js,Chrome,Safariにおいて最速となった。

これはケース 3 では他のケースより計算量が格段に多くなっている点が影響していそうだと考えた。というのもpixelmatchはまず色差を計算し、それがしきい値を超えた場合にantialiasの計算を行う。つまり差分が多ければ多いほど計算量は数倍に膨れ上がるためだ。(単純に画像サイズが大きいというのもあるが)

ケース 4 #

ケース 4 としてサイズが800x578の真っ白の画像と真っ黒の画像で(とりあえずChrome,Node.jsのみ)計測してみた。

これは画像サイズが小さくともantialias計算が多く行われるケースにおいてはSIMDのほうが高速になるのではないか？という推測からである。

x86 #

arm #

armにおいてはSIMDを使用することで20%程度高速化していることが分かる。

すなわちpixelmatchが想定しているようなユースケースにおいて行われている程度の計算では速度差がでにくいのだろうと推測される。機械語を見るにv128に詰め替えるにもオーバーヘッドがあるだろうし、v128に詰め変えたたあと、ちょろっと乗算をして値を取り出すような処理ではSIMDのメリットはでにくいのかもしれない。

ただx86については予想に反して変わらずSIMDのほうが遅かった。

そこで、更に追加計測として9112×12854の真っ白の画像と真っ黒の画像で差分をった。 これはケース 3 ではx86でもSIMDのほうが高速なケースがあったため、画像の大きさも速度比に影響のある変数であるのではないかと推測したためである。

結果としては以下のように20%ほど高速化した。つまりx86においてもSIMDにより高速化するケースはたしかに存在しそうだが、armの場合とはまた違ったパラメータがありそうに感じた。

なので現時点においてSIMDによる高速化が期待されるケースはありそうだが、少なくともpixelmatchが想定するユースケースでは多くの場合でSIMD化は高速化の面では優位に働かない。という話になりそうだ。

この辺は最適化によって状況も変わっていくだろうし、また適用できそうなケースを見つけたらSIMDを使って遊んでみることにする。

以上。