- Neatの
related_post_genベンチマーク順位の上昇は、高水準の最適化ではなく、配列を24バイト構造体としてではなく3つのポインタ引数として渡す小さなABI変更によるもの
- Neatの配列は参照カウントのため、先頭・末尾ポインタに加えて配列オブジェクト基底ポインタが必要であり、D配列の16バイトとは異なってSystem V AMD64 ABIのメモリ渡し経路に入る
- 16バイトを超える特定のaggregateは、呼び出し時に値をスタックへコピーしたうえでポインタで渡されるため、レジスタ渡しの利点を失い、スタックシャッフルのコストが大きくなる
- 例のベンチマークでは、
struct Vector { double x, y, z; }を構造体のまま渡すと10億回実行で12.3秒、各フィールドを個別引数で渡すと5.3秒まで短縮された
- C APIはC ABIに従う必要があるが、言語ランタイム内部の配列・タプル・sumtypeのような型については、16バイトを超える場合にフィールド分割渡しをベンチマークする価値がある
Neatで明らかになったボトルネック
- Neat は related_post_gen ベンチマークで順位を数段上げた
- 性能向上は新しい高水準最適化パスではなく、配列の渡し方を変えた結果だった
- 変更前: 3つのポインタを含む構造体引数
- 変更後: 3つのポインタをそれぞれ引数として渡す
- NeatはDと比べて予想以上に遅く、プロファイラでは関数呼び出しのためにスタックの大きな領域を移動する動作が見えていた
- ボトルネックは計算そのものより、呼び出し時のスタック再配置コストに近かった
Neatの配列が24バイトになる理由
- D配列と違って、Neatは参照カウントを使う
- Neatの配列は次の3つのポインタを含む
- 先頭ポインタ
- 末尾ポインタ
- 参照カウントが格納された配列オブジェクト基底ポインタ
- 3つのポインタは24バイトなので、2ポインタの16バイト配列とはAMD64の引数渡し規則で別の経路を通る
- D配列が速く、Neat配列が遅かった理由は、24バイトになって16バイト境界を超えたためだった
System V AMD64 ABIの16バイト境界
- SystemV AMD64 ABI specification は、特定のaggregateのサイズが2つのeightbyteを超える場合、その引数全体をメモリで渡すと規定している
- 構造体をメモリで渡すには、呼び出し側で次の作業が必要になる
- スタックに構造体サイズ分の領域を確保する
- その領域を渡す値で埋める
- 関数にはその構造体位置へのポインタを渡す
- この場合、値は必ずスタック上になければならず、LLVMの最適化余地は小さくなる
- 値はレジスタからスタックへコピーされる必要があり、スタックのどの部分が使用中で、どこを再利用できるかも追跡しなければならない
- このスタック再利用の追跡でLLVMはあまり良くない挙動を見せた
3つのdoubleベクトルベンチマーク
- ベンチマークでは
struct Vector { TYPE x, y, z; }; という形の3フィールドベクトルを使う
TYPE は double として定義されている- 2つの関数は同じ加算を行うが、引数の渡し方が異なる
vector_add_struct(struct Vector left, struct Vector right) は大きな構造体を引数に取るvector_add_fields(...) は left_x, left_y, left_z, right_x, right_y, right_z を個別引数として受け取る
mode と実行回数はコマンドライン引数で受け取り、最適化器が計算全体を定数畳み込みできないようにしているimpl.c はインライン化を避けるため別コンパイルする
clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000
- 結果は、構造体渡しで12.3秒、フィールド個別渡しで5.3秒だった
アセンブリに見える違い
- 構造体渡し版では、多くの命令がスタックシャッフルに使われている
- フィールド版は、パラメータが関数に入る時点で既にSSEレジスタに載っている点で有利
- 構造体渡し版では毎回スタックから値をロードしなければならない
- System V ABIは値をできるだけレジスタで渡すことを目的としているが、このケースでは16バイト超の構造体のため、その利点が消えてしまう
- AMD64で使えるレジスタ数を考えると、16バイト超の型でも値渡しは有用だったはずだとしている
cdeclに近づく状況
- フィールドをスタックに書いてポインタを渡す方式は、結果的にすべてをスタックで渡していた昔のx86
cdecl ABIに近くなる
cdecl は遅いことで知られており、それを高速化するためにさまざまな呼び出し規約が生まれた- AMD64 System V ABIが、構造体サイズのせいでこのケースでは昔のスタック渡し方式のように振る舞ってしまう点が問題だ
インライン化とLTOの例外
- 実際のコードでは、この種の関数がすべてインライン化されることもある
gcc でLTOを有効にすると、両バージョンの性能差は消えるclang では同じ結果にならない- すべての関数がインライン化できる、あるいはインライン化されるべきというわけではない
言語実装者とAPI最適化への助言
- C APIを呼ぶときはC ABIに従わなければならない
- しかし、非C言語の内部にある高水準型は、バックエンドには構造体のように見えても、必ずしも1つの構造体として表現する必要はない
- 言語実装者は、配列・タプル・sumtypeなどをどう渡すかを自分で決められる
- Neatでは、16バイトを超えるこうした型を個別フィールドとして渡す選択をし、ベンチマークで効果が出た
- AMD64で言語実装を行う、あるいはAPIを細かく最適化するなら、16バイト超の構造体を手動で分割する方法が有効かどうかをベンチマークすべきだ
- とくに内部ループでは、性能差が予想以上に大きい可能性がある
追記: double構造体とSSE
- 疑問は、
double は仕様上SSEクラスなのに、なぜ構造体がSSEレジスタで渡されないのかという点
- 答えは、理由は分からないが、実際にはそのように渡されないということだ
1件のコメント
Hacker Newsのコメント
ここでの問題は SysV amd64 ABI だ。言語内部のABIにSysVを使う必要はない。SysV Cの呼び出し側に公開されないのであれば、好きな呼び出し規約を使える
https://llvm.org/docs/LangRef.html#calling-conventions
気になる人向けに、neatlangの関連変更はこちら: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
単にLLVMの呼び出し規約の出力を変えるより、はるかに複雑に見える。おそらく作者は、これらの型をCプログラムに 決定的な呼び出し規約 として公開したかったのだろう
慣習に盲従せず、その状況で最も筋の通る方法を選べばよい
特にABIはさらに古いCPUとの互換性寄りになっていることが多く、新しいCPUなら拡張レジスタのような機能を使って、構造体サイズを減らさずに改善できる余地があるかもしれない。特定のハードウェアや世代に合わせたソフトウェアは一部のマシンで使えなくなるので、そこまで魅力的ではないだろうが、自分のシステムのハードウェア機能に合わせてコードを極限まで最適化したいとき、そういう出力を出せるコンパイラがあると面白そうだ
引数受け渡しのコスト は十分に理解されていないことが多いので、こういう記事はありがたい。Googleのようなところでも24バイトのオブジェクトを値渡しすることは珍しくなく、そのコストはあらゆる関数に広く薄く散らばるため、プロファイラには現れにくい
ただし、こうしたつまずきどころも露出している: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
思いつく唯一の例外は string_view くらいだ
運が悪ければキャッシュミスになり、24バイトのオブジェクトを主メモリから取ってくるのに100ナノ秒ほど待つかもしれない。同じオブジェクトを直接渡すならスタック上にあるので、キャッシュに乗っている可能性が高い
x64に最初に移行したとき、グラフィックスの vec3オブジェクト（float 3つ）が sizeof()=12 ではなく16バイトに膨らむのが心配で、グラフィックスエンジンをかなりベンチマークした
案の定というべきか、8バイト読み取りアラインメントのおかげで、12バイトより16バイトのほうが速かった。内部でもGPUでもそうだった。だから vec3 はひっそり vec4 になり、別途 vec4 も引き続き存在している。いつものことだが、局所的なベンチマークではなく 全体像のベンチマーク をすべきだ
16バイトなら、多くのアクセスが 3x4バイト ではなく、アラインされた 2x8バイト または 1x16バイト になるというのは理解できる。だが別のアクセスではそうならないかもしれないし、キャッシュ圧迫の増加 という問題もある
常識的に言えば、レジスタに渡される値は推測実行のおかげで先にロードできるので、スタックへの書き込みより速く、スタック操作はヒープ確保より速い
だからグローバル変数だらけの汚いスパゲティコードはものすごく速く、エレガントな再帰関数やタプル/構造体/リストの引数は信じられないほど遅い。前者のほうが 密なアセンブリループ に最適化しやすい
エレガントなコードが O(n) で、スパゲティコードが O(n^2) なら差を実感することになる。保守性も考慮すべきだ。ある意味では、コンパイラは私たちのエレガントな解法をスパゲティコードに変えるために存在している
グローバルオブジェクトはコンパイラ最適化の妨げにもなる
参考までに、MSVCでは構造体がスタックで渡される前の しきい値サイズは8バイト だ。これはABIの詳細なので、移植性のあるコードで依存すべきではない
ただし、頻繁に呼ばれない関数ならそこまで気にする必要はない。例のように頻繁に呼ばれる小さな関数なら、LTOのような方法でコンパイラがコードをインライン化できるようにすればよい。そうすれば、引数をレジスタで渡すことよりはるかに有用な最適化の道が開ける
こういう記事は「厄介ごとになるのに十分な知識」に分類される。指示どおり別個にコンパイルして、コンパイラにABIで呼び出し可能な関数を作らせるよう強制しても、LTOでこの問題を元に戻してしまうことがある
このプログラムをLTOでビルドすると、LTOなしのプログラムのどのモードよりも、両モードで劇的に高速になる。性能が重要なプログラムなら、まずプロファイリングし、ボトルネックを極限まで最適化してから、構造体を引数に分解するようなことをコミットすべきだ
ほぼすべてのコンパイラ生成コードに当てはまる。Valgrindなら測定できるかもしれないが、サンプリングプロファイラではたぶん無理で、散在するコード生成の問題を強調してくれるツールもない
Windowsの既定のcdecl呼び出し規約では、8バイトを超える構造体はレジスタで渡されない [1]
[1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...
amd64でSysV amd64 ABIを使う場合でも、16バイトを超える構造体を値で渡したり返したりすること自体は十分可能だ。単に遅いだけだ
それでも、コードをより明快にするために値渡しに価値がある場合は多い。もちろんこのケースはそうではないが、loegが指摘したように、自分の言語の内部ではC++コンパイラ、Go、OCaml、SBCLのように独自ABIを使えばよい
提示された例では、呼び出し元に影響を与えずに、パラメータ型を
struct Vectorからconst struct Vector &に変えて参照渡しにすれば修正できるポインタまわりのバグがあった多くのC++コードで、わざわざポインタを使っていたが、参照渡しで十分で、しかもそのほうが簡単かつ安全に書けたケースをたくさん見てきた
ABIが値をポインタで渡すよう指示するため、ポインタを得るにはどこかに保存しなければならず、
const-refで明示した場合と同じことが起きる。構造体の値を個別の引数に変えれば、引数をレジスタで渡せるallocaが20個も30個もあるコードだった。すべての関数が、呼び出しに渡される各パラメータごとに個別のallocaで始まっていたLLVMがこういうものはうまく整理してくれると、ずっとある程度は思っていたのだが、実際にはそうではなかった
説明されている利点は、レジスタからスタックへのシリアライズをまったく回避することだが、参照渡しではそれは避けられないように見える
C++を許容するなら、コピーを減らすためのムーブ引数など、さらに多くの選択肢が生まれる
C++では昔からの経験則として、プリミティブ型以外のものは、値で渡す明確な理由がない限り参照で渡し、本当に必要ならポインタで渡すべきだと言われてきた
これはABIのためでもあり、コピーコンストラクタやムーブコンストラクタを避けるためでもある。退屈な低レベルの詳細ではあるが、C++で最高の性能を求めるなら気にすべき部分だ。はっきり言えば、これは単なる性能最適化であり、構造体を渡すコードも正しく動作するが、ただそれほど速くないだけだ