- 小さなCループであってもコンパイラ出力が常に最善とは限らず、x86_64アセンブリを手で調整した結果、条件分岐を削除した版はclang出力より6.73倍高速になった
- 対象の関数は文字列中で
's' を +1、'p' を -1、'\0' を終了として扱い、clang 16の出力はこの流れを3つの条件分岐に分けていた
- 分岐順序の変更、基本ブロックの再配置、算術によるジャンプ置換を経て、実行時間は3.23秒から2.87秒まで短縮され、この段階でGCC 12と同じ速度に達した
- 最速版は
cmove により文字ごとの加算値として 0、1、-1 のいずれかを選び、常に add を実行することで 0.48秒、1.94GiB/sのスループットを記録した
- ベンチマークはAMD Ryzen 5 5625UとLinux 6.1.33上で、ランダムな
'p'/'s' 文字100万個のリストを1000回処理して行い、複数回の実行のうち最良の結果を採用した
実験対象の関数とコンパイラ出力
- 対象の関数は文字列ポインタを1つずつ進めながら、文字に応じて整数
res を更新する
's': res += 1'p': res -= 1'\0': res を返す- それ以外の文字: 変化なし
- 関数が小さいため、gccやclangがかなりうまく、あるいは最適に最適化できるかもしれないという期待から出発している
- clangが生成した初期アセンブリは、4つのケースを3つの条件分岐（
je, je, jne）に分けていた
res = 0 で開始- 文字を読み込み、まず
'\0' かどうかを検査
- その後で
'p'、's' を比較
- 初期のclang結果
- 実行時間: 3.23秒
- スループット: 295.26MiB/s
- GCCはやや多くのコードを生成していたが、わずかに高速だった
まれな終了条件より頻出文字を先に検査
- ループが終了するのはヌル終端文字
'\0' に遭遇したときだけであり、この関数ではヌル終端文字は多くても1回しか現れない
- clangの出力は
'\0' を最初に検査しており、各 'p' と 's' 文字ごとに終了条件から確認する構造になっていた
- 最初の手動変更では比較順を入れ替え、
'p' と 's' を先に検査した
- 結果
- 実行時間: 3.10秒
- 高速化: 1.04倍
- スループット: 307.64MiB/s
基本ブロックの再配置とジャンプ削減
- 頻出する2つのケースである
'p' と 's' はどちらもループ先頭へ戻るジャンプを行うため、片方のブロックをループの上に配置すれば分岐を減らせる
's' ブロックをループの直前に置くと、's' の処理後は追加ジャンプなしでループへ流れ込める- その代わり、関数開始時には
's' ブロックを飛ばしてループへ1回ジャンプする必要がある
- 関数開始時のジャンプは1回だけ発生する
's' 文字は何度も現れ得るため、受け入れ可能なトレードオフとして扱える
- 結果
- 実行時間: 2.98秒
- 全体の高速化: 1.08倍
- スループット: 320.02MiB/s
算術で無条件ジャンプを1つ削除
p: ブロックからループへ戻る無条件 jmp をなくすために、算術を利用した- 1回の減算は
sub eax, 2 の後に inc eax を行っても同じ効果になるため、'p' の処理後に 's' ブロックへ流れるようにした
- この方法でもう1つの分岐命令を削除した
- 結果
- 実行時間: 2.87秒
- 全体の高速化: 1.12倍
- スループット: 332.29MiB/s
- この時点の性能はGCC 12が生成したコードと同等だった
- GCC 12のコードも2.87秒で実行された
- 手書き版は13命令
- GCC出力は19命令
- GCCのコードはループをアンロールし、caseブロックをある程度再利用しているように見える
条件分岐を cmove に置き換える
- 条件分岐がボトルネックなら、分岐予測器に頼らず条件分岐そのものを取り除ける
- 最速版は
cmove、つまり等値条件付きムーブを使う
- 動作規則は単純
- 既定値は0
- 現在の文字が
's' なら1
- 現在の文字が
'p' なら-1
- 各反復で選ばれた値を常に
res に加算する
- この方法は制御フローグラフから多くの矢印を取り除く
- 結果
- 実行時間: 0.48秒
- 全体の高速化: 6.73倍
- スループット: 1.94GiB/s
- 手書きのコンパクトなCループ用アセンブリでは、コンパイラが自動化していない最適化によって6倍台の高速化が可能だった
レジスタ節約の試みと失敗した追加実験
- x86_64の
sete を使って、1バイトレジスタを条件に応じて0または1に設定する版も試した
- この版では
r8d の使用をなくせるが、cmov だけを使った版より遅かった
- 結果
- 実行時間: 0.51秒
- 全体の高速化: 6.33倍
- スループット: 1.83GiB/s
- レジスタ使用数を減らしたり、32ビット演算の代わりに8ビット演算を使ったりしても、速くなるわけではなかった
- 追加の試みも性能を下げた
- 最良版のループアンロール: 遅くなった
- ループ先頭を16バイト境界にアライン: 遅くなった
- GNU assemblerでラベルの前に
.align <bytes> を入れると nop を挿入できる
ベンチマーク環境とコード
- コード一覧は GitHub にある
- ベンチマーク環境
- OS: Linux 6.1.33
- CPU: AMD Ryzen 5 5625U with Radeon Graphics
- CPU family 25、6コア、コアあたり2スレッド、1ソケット
- clang: 16.0.1
- gcc: 12.2.0
- C版は
-march=native でコンパイルし、特定CPU向けのコードを生成できるようにした
- ベンチマークはランダムな
'p' と 's' からなる100万文字のリストを対象にしている
- 各関数版はこのリストを1000回処理する
- 各版は複数回実行し、その中で最良の結果を選んだ
- 続編として part two に続いている
1件のコメント
Hacker Newsでの反応
正しい結論は 手書きのアセンブリはCより6倍速い ではなく、ジャンプは条件付き算術よりずっと遅くなりうる のほうに近い
Cでも
switchを使わずifを1つか2つ使って処理すれば、簡単に同じ効果を出せる。sなら増加、pなら減少、\0なら終了という形にC関数を書き換えると 5.5倍速くなり、例の実行では 3.58秒から 0.65秒に短縮された他の人たちが言っているように、入力を調整したうえでアルゴリズムをベクトル化することもできる。これは教育用の演習として見ていて、十分な理由もなくアセンブリに降りていくことが起きないよう心から願う
Linus も以前、予測可能な分岐では
cmovは有用ではないと長々と書いていた: https://yarchive.net/comp/linux/cmov.htmlgcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0ではloneとltwoがどちらも約 3.58秒だったswitchを複数のifに置き換えるのが常に速いのか気になる。どの程度のケース数からswitchのほうが速くなるのかも気になるし、一貫しているなら コンパイラ最適化 に入るべきだと思う元のコードはコンパイラフレンドリーに書かれているとは言いがたい。
result += *s == 's'; result -= *s == 'p';のように書けば、コンパイラは適切な 分岐なしのsete/cmovコード を生成し、記事の最適化アセンブリとほぼ同じ速度になるただしループアンローリングやベクトル化はしない。文字列サイズを別途渡して
sizeを分かったうえで回せば、コンパイラはループの大きさを把握できるのでアンロールし、可能なら AVX-512 命令も使う。大きな入力ではずっと速いが、自分でベンチマークするのは面倒だ。文字列長を追跡しないCプログラマなら好きにすればいいが、本当にそうすべきではないと思う: https://godbolt.org/z/rde51zMd8その版は 3.88GiB/s を達成している。あえてベクトル化までは進めず、問題のスコープを小さく保ちながら記事のアセンブリのコツやテクニックを見せたかった。後で入力文字列をパディングしてアルゴリズムをベクトル化する記事を書く余地もある
/* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */{.overflowChecks:off.}を有効にしてinputを走査し、's' == cなら増加、'p' == cなら減少させる方式だApple M1 では約 5倍の高速化 になり、オーバーフロー検査を有効にしたままだと基本のC版に対して約2倍までしか速くならなかった。SIMD最適化を誘発するよいパターンを知っておくのは、いつだって有益だ
最適化の専門家に近い立場からすると、この問題はまったく別の解き方をすると思う。自分のマシンでは初期のC版は毎秒 389MB で、記事のアセンブリが同じ 6.2倍の向上を出すなら毎秒 2.4GB ほどになる
長いバッファでは、このC++版は自分のマシンで 毎秒 24GB を超える: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
アセンブリなしの AVX2 intrinsic ベースで、元の版より61倍速い
ymmレジスタにカウンタを維持する代わりに、movemaskとpopcntを使ってプロローグをベクトル化できそうだまだテストしていないコードなのでベンチマークは必要だが、
s、p、\0のマスクを作り、tzcnt、bzhiで文字列終端までのビットを数える形でアプローチできそうに見えるstd::experimental::simdでも可能なのか知りたい: https://en.cppreference.com/w/cpp/experimental/simdこのコードは SIMD が本当によく合いそうだ。プロトタイプを明示的な長さを受け取る形に変えられるなら、16バイトずつ読んで処理するのは簡単だ
比較結果をそのまま足し引きすればいいし、関数の先頭で
strlen()を呼んで明示的な長さを得るだけでも、おそらく十分価値がある手早く RISC-V ベクトル化実装 を作ってみた。
rvvで文字列を読み、\0の位置を見つけてから、sとpの個数をvcpopで数える方式だMangopi MQ Pro（C906、
rv64gc+rvv 0.7.1、128ビットベクトル長）では、switchは 0.19 Bytes/Cycle、テーブルC実装は 0.17 Bytes/Cycle、rvvは 1.57 Bytes/Cycle で、約 30KiB 以降は 1.35 まで下がる。ポインタをページ境界に揃え、vlがページサイズを超えないようにすれば 2/1.7 Bytes/Cycle まで可能だrvvにはこの機能があり、そうでないとヌルバイトが確保済みメモリの末尾直前にある場合に失敗する可能性があるこれはx86アーキテクチャ特有の性質のように思える。分岐しないコストが非常に安いため、相対的に分岐が高コストに見える: https://wordsandbuttons.online/challenge_your_performance_in...
ただし、他のプロセッサではそうとは限らない: https://wordsandbuttons.online/using_logical_operators_for_l...
より大きな問いは、一般にCがなぜ必要なのかということだ。特定のハードウェアで最もうまく動くよう手作業で調整するのなら、Cは間違った道具であり、必要なのはアセンブリとまともなマクロシステムだ。Cの本来の目標は、システムレベルのコードをあるプラットフォームから別のプラットフォームへ移しやすくすることであり、その過程で効率の損失が出るのは想定内だった。ヒンディー語の詩をウルドゥー語に翻訳する代わりにエスペラントで書き、望む言語へ自動翻訳するようなものだ。優れた詩を2編得られるわけではないが、質の低い翻訳を2つ素早く得られる。それがCの役割だ
FDO/PGOでビルドすれば、分岐やブロック再配置は確かに行える。FDOなしでは、コンパイラは各分岐がどれくらいの頻度で選ばれるか分からないからだ。場合によってはFDOが
cmovを有効にすることもあるただし、
cmovが通常のtest/jumpより効果的かどうかは、分岐がどれだけ予測可能かに大きく左右される。通常、分岐が非常に予測しづらいときにcmovのほうがうまく動く。cmovで6倍速くなったのなら、テスト入力はほぼすべてsとpからなるランダム文字列だったのだろうと推測する。間違いではないが、データの明示されていない特性をベンチマーク向けに活用しているので、記事はやや誤解を招きそうに見えるランダムに
's'または'p'を選び、文字は's'、'p'、終端ヌル以外は現れない。この入力特性が分かっていれば、result += (1 | *s++) - 'r';のような過度に賢い最適化すら可能だ。あまりにトリッキーなコードだが、データ特性の活用という要点は完璧に示している'\0'に遭遇した時点で関数が返るので、最大でも1回しか現れないが、他の文字は複数回現れうる。この情報は、PGOがなくてもコンパイラが利用できる情報のように見えるもちろんPGOは役立つし、私のマシンでは2.80秒が出て、
Rearranging blocksセクション末尾のコードより良かった。入力はBenchmarking setupで説明されており、リポジトリにもある: https://github.com/414owen/blog-code/blob/master/01-six-time...記事末尾でリンクされている続編の第2部では、Cコードを可能な限り高速化して、この文章中のすべてのアセンブリを上回っている。アセンブリを書くのが必ずしも良い考えだと言いたいわけではなく、最適化やコンパイラ出力の読み解きが面白い挑戦であり、良い学習機会だと思っている
記事と続編よりも速くできたように思う。ただし、文字列が
's'と'p'だけで構成される場合に特化しているという代償はあるベンチマークも
's'と'p'だけからなる文字列しかテストしていないので、公平ではあると思う。要点は、次の文字がsならresを1増やしたいが、res += c - 'r'ではsでは1になる一方でpでは-2になってしまい失敗するということだ。ところが、'p' - 'r'を符号なし整数として見るとアンダーフローしてキャリーフラグが立ち、x64のadcは2つのレジスタとキャリーフラグを一緒に加算する。つまり、2つのcmp, cmovを1つのsub, adcに置き換えられる。この版は続編記事のC版より1.08倍、既存のx64-7より1.66倍速かった。もちろん、SWAR/SIMDを使えばさらに改善できる02-the-same-speed-as-c/loop-5.x64.sのやや単純なアセンブリが、自分の手元で最速の版だと明記しておくべきだったかもしれない私のマシンでは
loop-5.x64.sが0.244秒、上の実装は0.422秒になる。なぜこんな差が出るのか正確には分からないし、見た感じでは上の実装のほうが速そうに思える。だから、実際に動かすハードウェア上で常にベンチマークすべきだ'p' * lenを引いてから、('s' - 'p')で割ればsの個数を求められる。pの個数はlen - s_countだ最初の合計も容易にベクトル化できる。ミスがなければ動くはずで、唯一の問題は累積和のオーバーフローの可能性だ。自分でベンチマークする気力はない。修正:
sを見たときに減少する部分を見落としていたので、最終結果はp_count - s_countになるstrlen()はかなり高速に実装されているはずで、バッファサイズが分かっていれば、コンパイラが内部ループを自動ベクトル化できる実際、
len = strlen(buf)の後にforループで(buf[i] == 's') - (buf[i] == 'p')を加えるコードは自動ベクトル化される: https://gcc.godbolt.org/z/qYfadPYoq以前、SBCL向けにCommon Lisp UTF-8デコーダを書いたことがある。すでに組み込みデコーダがあったので練習用だった
明白で簡単な最適化を除けば、ほぼすべての性能向上は、コンパイラが分岐の代わりに
cmov*命令を生成するようコードを構造化したことから来ていたUTF-8デコーダは通常、ほとんどすべてASCIIの入力で多く実行される。どんな入力でベンチマークしたのか気になる