コグノスケ

ぼくの考えた最強の memset

目次です。

• ぼくの考えた最強の memset
• glibc の memset は強かった

NEON intrinsic を使って自分で memset を実装してみました。ざっくりした設計方針としては、

• NEON store (128bit) x 2 で 32バイトずつ書く
• 端数 25〜バイトは NEON store x 2
• 端数 16〜バイトは NEON store + uint64 store

相手は汎用実装ですし、Cortex-A72 に特化した実装なら楽勝だろう、などと考えて始めましたが、甘かった。glibc のフルアセンブラ版はかなり手ごわいです。

自作 memset の測定結果（Cortex-A72）

グラフの赤い線が、自作した memset の性能です。

最適化レベル O3 の simple memset にはほぼ全域で勝てますが、サイズが小さいときの musl は強い（サイズが小さい場合から判定しているから？）です。glibc のフルアセンブラもかなり強いです。測定によって勝ったり負けたりな程度です。

全然最強じゃなかった……

設計が甘すぎたことがわかったので、下記のように見直しました。

• 少ないバイト数の条件から判定
• NEON store (128bit) x 2 で 32バイトずつ書く
• 端数バイトは NEON store（分岐を減らした）

序盤で musl memset に負けていたのは、バイト数の条件判定の順序が良くなかった（大きいサイズから判定していた）ためなので、1番目で対策しています。2番目と 3番目の方針は良いとも悪いとも一概に言えませんが、RK3399 だとこれが一番性能が出ました。

自作 memset 改善後の測定結果（Cortex-A72）

設計意図通りに musl の序盤（特に高速な 1〜8バイト付近）と、glibc フルアセンブラの序盤（1〜32バイト）には勝てたものの、glibc フルアセンブラ版は中盤以降が強く、33バイト以降は全く勝てません。

私の作った memset は 32バイトまでは専用処理で、33バイトからループで処理するようになるので、33バイトから性能がかなり落ちます。

おそらく glibc フルアセンブラ版も同様に 16バイトから性能が落ちるので、ループ処理していると思うんですが、それ以降の巻き返しが凄くて、33バイト以降はまったく勝てないですね……。どうやってんだろうね、これ？

コンパイラが変な and とか sub を出力しているのを見つけたので、アセンブラでも実装してみましたが、性能はほぼ変わりませんでした。設計の根底が違うんでしょうね。

Cortex-A53 だと全く勝ち目無し

RK3328（Cortex-A53）で測ってみると、musl には勝てますが、glibc フルアセンブラ版には勝ち目無しで、ほぼ全域に渡ってボコボコにされます。

自作 memset 改善後の測定結果（Cortex-A53）

基本設計が「余計な write をしてでも、とにかく速く終われ」なので、write を正直に実行してしまうようなヘボいプロセッサになればなるほど勝ち目が薄いです。

memset に一番効く最適化

Cortex-A72 での memset は O2 に -ftree-vectorize と -fpeel-loops を足すと、O3 の性能とほぼイコールになることがわかりました。

gcc -O2 -ftree-vectorize -fpeel-loops -fno-builtin の測定結果（Cortex-A72）

元の処理が非常に単純なループ処理のためか、ループ系の最適化がメチャクチャ効くっぽいです。

何が効くのか？

GCC の GIMPLE を出力させ（-fdump-tree-all）眺めてみると、

オリジナル

1バイトごとにデータ処理するループが生成される。

ベクタライズ（161t.vect）

16バイトごとにデータ処理するループと、1バイトごとに残りデータを処理するループに分割される。

アンローリング（164t.cunroll, 169t.loopdone）

残りデータを処理するループが展開される。

こんな感じに見えます。正直言って、ループアンローリングなんて大したことないと思っていましたが、これほど効くとは思いませんでした。

メモ: 技術系の話は Facebook から転記しておくことにした。大幅に追記。

memset のベンチマーク（AArch64, Cortex-A53 編）

• memset のベンチマーク（x86_64, Ryzen 7 2700 編）
• memset のベンチマーク（AArch64, Cortex-A72 編）
• memset のベンチマーク（AArch64, Cortex-A53 編）

（参考）コード一式は GitHub に置きました（GitHub へのリンク）

AArch64 その 2 です。Cortex-A53 で memset をやってみました。環境は RK3328 Cotex-A53 1.4GHz です。メモリはおそらく LPDDR3-1600 です。

Cortex-A72 と似ている点としては、

• musl memset 関数が非常に優秀
• ベクトル化は性能向上に効くが、他も有効な要素がありそう

違う点としては、

• アセンブラ実装と musl memset 関数の差が開く
• O3 の最適化がかなり効く（※）
• glibc memset 関数の不安定さが減る

こんなところでしょうか。A72 の glibc memset 関数はグラフが上がったり下がったりグチャグチャしていましたが、A53 だと割と素直になっています。

gcc -O3 -fno-builtin の測定結果（Cortex-A53 編）

gcc -O2 -ftree-vectorize -fno-builtin の測定結果（Cortex-A53 編）

gcc -O2 -fno-builtin の測定結果（Cortex-A53 編）

（※）A72 では単純な memset 関数は musl memset 関数にほぼ勝てない（16〜22バイトのみ勝つ）が、A53 では割と良い勝負（16〜22、32〜38、48〜52バイトで勝つ）をしている。