Happy Fun 分岐予測器を侮ってはいけない (2023)

 (mattkeeter.com)
1 ポイント 投稿者 GN⁺ 2024-07-05 | 1件のコメント | WhatsAppで共有
  • AArch64アセンブリでループ内の分岐を1つ減らそうとした最適化が、かえって 4倍遅くなり、原因は bl/ret の呼び出し・復帰ペアを非対称に使って分岐予測器を混乱させたことにあった
  • 元のコードはループごとに bl foo と b loop の2回分岐するが、修正版コードは1回の bl loop で x30 を固定し、複数の ret が同じアドレスに戻るようにして 分岐数を減らそうとした
  • M1 Maxで1024個の float 配列を加算した結果、通常の bl/ret コードは969nsだったが、1回の bl と複数の ret 構成は3.85µsに遅くなり、ret を br x30 に変えると913nsまで回復した
  • Instrumentsの性能カウンタでは、10億要素の合計で非対称な bl/ret 構成の復帰分岐予測ミスが約 93% に達しており、FETCH_RESTART、MAP_DISPATCH_BUBBLE、MAP_REWIND も大きく増加していたことが示された
  • より高速な実装は foo のインライン化、Rustの iter().sum()、NEON SIMDと手動ループアンローリングへと続き、最終的なSIMD版は94nsまで短縮されたが、浮動小数点加算の順序が変わるため 結果が異なる可能性がある

AArch64ループで起きた逆効果

  • 例の関数は float 配列を走査し、各値を foo に渡して、foo が累積値 g を更新する構造である
  • 単純なAArch64変換は次の流れを持つ
    • ループ開始時に n == 0 かどうかを確認する
    • ldr s1, [x0], #4 で値を読む
    • bl foo でサブルーチンを呼び出す
    • foo の ret が bl の次の命令に戻る
    • b loop で再びループ先頭へ移動する
  • foo は親関数と同じスタックフレームとレジスタを使う naked function に近い形で、s1 を読み s0 に加算する

bl と ret の役割

  • bl は branch and link 命令で、指定したラベルへジャンプしつつ、次の命令アドレスをリンクレジスタ lr または x30 に保存する
  • ret はリンクレジスタに入っているアドレスへジャンプする
  • 元の構造では bl foo と ret が互いに対応しており、ret は常にその bl の次の命令へ戻る

失敗した「分岐を1つ減らす」最適化

  • 修正後の構造は foo を変えずに、ループ内の分岐を1つ減らそうとした
    • 関数冒頭で bl loop を呼び出して x30 に loop 開始アドレスを入れる
    • ループ終了条件を確認したあと、別の分岐なしで foo のコードへ落ちる
    • foo の ret は x30 に入っている loop に戻る
  • この構造ではループ本体で x30 が変わらないため、繰り返される ret は常に同じアドレスへ復帰する
  • 単純な foo は次のように float を足す1行のコードである
foo:
    fadd s0, s0, s1
    ret
  • この場合、関数全体は入力 float 配列の合計を計算する

ベンチマーク結果と分岐予測の問題

  • criterion を使ってM1 Max CPUで1024要素配列をベンチマークした
    • 通常の bl/ret: 969ns
    • 1回の bl、複数の ret: 3.85µs
  • 分岐を1つ減らしたコードのほうが、2つの分岐を使う元のコードより約 4倍遅い
  • CliffとDanは、bl/ret ペアが対応していないため 分岐予測器 が混乱したのだと見ている
  • ARM文書 によれば、RET はプロセッサに関数復帰であることを認識させ、より正確な分岐予測を可能にする
    • BR LR も機能的には同じことができる
    • しかし RET は、プロセッサが関数復帰として認識できる別個の命令である
    • 分岐予測が当たれば、パイプラインに正しい命令が入り、メモリから命令を待つ時間を避けられる

Return Address Stack と br x30 の実験

  • 分岐予測器は内部的に関数復帰アドレススタックを維持している可能性がある
    • bl 実行時に復帰アドレスをスタックへpushする
    • ret を見ると、直近の bl の復帰アドレスに戻ると仮定する
    • そのアドレスを基準に先読みと投機実行を始め、その後スタックからpopする
  • この方式は bl/ret が正しく対応しているときにはうまく機能する
  • 同じアドレスを複数の ret が繰り返し使うと予測が失敗し、無駄な先読み、誤った投機実行、パイプライン停止やflushが起こりうる
  • Danの提案どおり ret を br x30 に変えると、性能低下は消えた
    • 通常の bl/ret: 969ns
    • 1回の bl、複数の ret: 3.85µs
    • 1回の bl、複数の br x30: 913ns
  • br x30 版はループごとに分岐を1回しか行わないため、元のコードよりわずかに速い

Instruments性能カウンタ

  • Instrumentsで最初の2つのプログラムの性能カウンタを確認した
  • 測定は10億要素の配列を合計している間に行われた
  • 非対称な bl/ret では、復帰分岐予測ミスが約 93% 発生していた
カウンタ 通常の bl/ret 1回の bl、複数の ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928,644,975
FETCH_RESTART 61,121 987,765,276
MAP_DISPATCH_BUBBLE 1,155,632 7,350,085,139
MAP_REWIND 6,412,734 2,789,499,545
  • Appleはこれらのカウンタを完全には文書化していない
  • 他のカウンタは、悪い分岐予測の downstream effect だと推定される
    • FETCH_RESTART: 誤った先読みの可能性
    • MAP_DISPATCH_BUBBLE: パイプライン停止 に関連している可能性
    • MAP_REWIND: 巻き戻しが必要な誤った投機実行の可能性

さらに速くする方法

  • 例は教育用コードであり、foo がサブルーチンである理由も「できるだけ速いコード」ではなく、説明用の構造に近い
  • foo の内容をビルド時点で把握しており、最大ジャンプ距離より短いなら、bl と ret を完全に除去して インライン化 できる
    • 969nsから911nsへ、約6%高速化した
  • Rustで単に f.iter().sum() を使うと833nsまで下がる
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMDと手動ループアンローリング

  • 手動のAArch64 SIMD実装は3つのループで構成される
    • loop: 残りの値の個数が4の倍数になるまで、s0 に個別の値を加える
    • simd: 4つの値を一度にベクトルレジスタ v1 に加算し、残りの値の個数が8の倍数になるまで繰り返す
    • simd2: simd を2倍にアンロールし、反復ごとに8つの値を処理して v1 と v2 に加算する
  • 関数終了時に v1 と v2 の値を s0 に加算して返す
  • タイプpunningは、float* である x0 を double* のように扱い、128ビット、つまり float 4個を d3 と d4 で読む方式である
    • mov v3.d[1], v4.d[0] で d4 の64ビットを v3 の上位64ビットへ移す
    • fadd v1.4s, v1.4s, v3.4s では .4s 接尾辞によって4つの float として扱う
  • このSIMD実装は94nsで実行され、以前の最速だったRust版833nsより約 8.8倍速い

全体の性能まとめと注意点

実装 時間
通常の bl/ret 969ns
1回の bl、複数の ret 3.85µs
1回の bl、複数の br x30 913ns
b を使う普通のループ 911ns
Rustへの書き換え 833ns
SIMD + 手動ループアンローリング 94ns
  • SIMDコードは浮動小数点加算の順序を変える
  • 浮動小数点加算は結合法則が成り立たないため、SIMD版は直列コードと 同じ結果にならない可能性がある
  • コンパイラが合計処理にSIMD命令を生成しなかった理由も、このためである可能性がある
  • すべてのコードは GitHub で公開されている
  • ARM64マシンで cargo bench を実行すればベンチマークを再現できる

関連記事

1件のコメント

 
GN⁺ 2024-07-05
Hacker Newsの意見

  • 最後の最適化コードは、32ビット浮動小数点数 1024個の配列の合計を94nsで終える
    その94nsのあいだに、旧友の1MHz 6502は、プログラムの最初の命令の最初の1バイトを取りに行けとメモリチップへ信号を送るかどうか、ようやく考え始める程度だったはず
    ただしこのコードは、全面的にキャッシュ内で実行されることを前提にしている。そうでなければ、記事に出てくる強力なM1 Maxですら最初のメモリフェッチ待ちで止まっていただろう。DRAMは遅い

    • いまやL1キャッシュの総容量が、6502がアドレス指定できた全メモリと同じくらい大きくなったのは幸運なことだ。本当に驚くべき時代に生きている

  • Raymond Chenがほぼ20年前に同じ話題を扱っていた: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Intelのx86/64アーキテクチャ命令リファレンスの紙版、いわゆる分厚い青い本を持っていて、データシートや文書を丹念に読む立場からすると、「直感的にはXのはずだがYが起きる」という話を聞くたびにいつも慎重になる
      シリコンの半導体としての性質やドーピングについての基本的な理解を別にすれば、ここには直感的なことはほとんどない。ダイの回路図や配線、経路を見たのでなければ、エンジニアやデータシートが明示的にそう言わない限り、AがBより速いだろうと期待する理由はほとんどない。特にARMではなおさらだと思う
    • Raymond Chenの記事は素晴らしく、この記事を解釈するうえで良い文脈を与えてくれる
      今回の記事が付け加えているのは、retを別のbr命令に置き換える単純な補正だ。これで組が再び「対称」になり、分岐予測器を壊さずに少しだけ速いコードを得られる
    • Raymond Chenは本当に宝のような人だ。Microsoftが彼にブログを書き続けられる裁量を与えていることに感謝しているし、そこから本当に多くを学んでいる
    • 最近のx86プロセッサでは、もう事実ではないようだ: https://news.ycombinator.com/item?id=40767676

  • もちろん何でもあり得るし、配列の総和を求める普通のループは、実際にはコンピュータに要素を1つずつ累積しろと指示する形になっている
    しかし、たとえばSIMDで4つの累積値を並列に作って最後に足し合わせるのが、要素を1つずつ足すより間違っているとまでは言いにくい
    浮動小数点の総和には本質的に誤差範囲があると考えるべきで、その範囲内の答えは有効であるべきだ。入力の浮動小数点数について特別に分かっていることがあるなら、言語はその意図を明示的に表現する手段を与えるべきだと思う。もっとも基本的なループがデフォルトである以上、デフォルトで最高の性能を出すのが筋だと思う

    • 数のリストを足し合わせるという単純な作業にも、意外なほど多くの総和アルゴリズムがある
      ループで1つずつ足す素朴な方法は obvious だが、累積誤差の総量についてより良い上限を与える、もっと洗練された方法があり、Kahan加算はそのよく知られた例だ: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      ストリーミングデータなら1つずつ足すしかないかもしれないが、固定サイズのバッファをN個使えるなら、新しい数が入るたびにどの部分集合を部分和にするか、それを累積和にどう足すか、その選択で証明可能な誤差改善があるかといった問題が生じる
    • 浮動小数点値の大きさの差が大きいと深刻な問題になる
      たとえば [1e50, -1e50, 1e3, 1e3] を (((1e50 + -1e50) + 1e3) + 1e3) と計算すれば 2e3 だが、((1e50 + 1e3) + (-1e50 + 1e3)) と計算すると 0 になる
      小さい値をたくさん大きい値1つに足す場合も似ていて、(((1e3 + 1e3) + 1e3) ... + 1e50) と (((1e50 + 1e3) + 1e3) ... + 1e3) はかなり違う
    • 「そうあるべきだ」という話は多いが、実際にはほとんどそうならない。元の式が提供している情報は算術演算の順序だけだ
      ビルドのたびに算術結果が安定しないと、完全に悪夢になる。同じ入力でソフトウェアを再ビルドして実行したときに、異なる結果が出てはいけない
      昔のIntel特有の事例も経験したことがあるが、FPUは内部では80ビットレジスタを使い、メモリには64ビットを書き出すため、レジスタの充填や退避のタイミングが変わると丸めのタイミングも変わり、結果も変わった。プログラム開始時にグローバルなFPUフラグを設定して、各演算ごとに丸めを強制することはできる
    • 浮動小数点値をソートすると誤差は減る。だから複数のアキュムレータを使うと精度が下がり得ると思う。ソート済みデータも珍しくない
      常に正しい答えは存在するし、コンパイラは少なくともデフォルトでは誤った変更をしてはいけないと思う。ただし、プログラマが意図をより明確に表現する方法はいつでも歓迎だ
    • 多くのコードは、特定の命令セットアーキテクチャの中では浮動小数点演算が決定的であることに依存している
      浮動小数点ループへのSIMD適用はデフォルトにもできただろうが、既存コードを多数壊し、出力がしばしば非決定的に変わるため、プログラマが明示的に選ぶべき機能になっている
      しかも多くのプログラマはこうした事実を知らないかもしれず、float Sum(float[] values) が別の値を返し始めても、その原因がベクトル化だと知る術がないかもしれない。だから、たとえば .NET 標準ライブラリは integers.Sum() にはSIMDを使うが、floats.Sum() には使わない

  • 「ループ終了を確認した後、分岐せずにそのまま foo 関数の中へ落ちる」という一文だけ読んで、「ああ、それが問題か」と思った。
    派手な分岐予測器ヒューリスティクスの深い話かと思ったら、結局は基本的なヒューリスティクス違反だった。
    対応しない call/ret 命令を使えば大きな速度向上が得られる、などと考えるべきではない。分岐予測器がリターンアドレスのシャドースタックを維持するのは何十年も前からある方式だ

    • 分岐予測器の動作をよく知っているのは良いことだが、多くの人はそうではなく、そうした人たちにとっては新しく、もしかすると有用な情報かもしれない。この文章があなた向けではなかっただけで、それでも問題ない
    • セキュリティ機能としてアーキテクチャレベルのシャドーコールスタックを備えるシステムでは、プログラム実行をさらに根本的に壊し、つまりクラッシュを引き起こす可能性がある
    • 一方で RISC の設計目標は、たいてい他の要素を犠牲にしてでもコンパイル済みコードの性能を高めることにある。
      そのため、この種の危険は文書化されるべきだが、設計者はアセンブリを直接書く人が文書を読んだと想定できるはずだ。
      他方で Sophie Wilson はもともと ARM 向け BBC BASIC 実装を書いていたが、その当時は分岐予測器がなかった。32ビットなので規則は違うにせよ、アーキテクチャ上の前提が変わるとき、AArch64 がコードをどう遅くするのかは気になる
    • それでも、実際にこうした最適化や他の最適化をどう達成したかも示しており、有益な文章だった

  • 古典的な SNL ネタの「Do not taunt happy fun ball」のことだ: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • happy fun 分岐予測器から煙が出始めたら、直ちに避難しなければならない
    • 「Happy Fun Ball はサウジアラビアの我が軍兵士たちに配送され、イラク上空の戦闘機からも投下されています」という文句を見ると、「いったい今は何年なんだ!?」という気分になる
    • いまでも 16 州では合法: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • 2023年の記事だという点を見落としてはいけない。いまではすでに少し古く、Rust 1.78 以降はコンパイラがより積極的なループ展開と多少の SIMD を使う: https://godbolt.org/z/zhbobW7rr
    元記事は「アセンブリを見るとループ展開をしている」として https://godbolt.org/z/Kv77abW6c をリンクしていたが、これは変化し続ける「Rust Nightly」を使っていた。現在はさらにループ展開が増えている。
    ループ展開は Rust 1.59 から始まっていた: https://godbolt.org/z/5PTnWrWf7
    GitHub 上のコードでは Rust 1.67.0-nightly、2022-11-27 版を使っていた

    • リンクを Rust 1.67 を明示的に選ぶよう更新した
    • 元記事が見ていたと思われる Rust 1.67.0 はこのような結果を出す: https://godbolt.org/z/4Y61d9seh
      同じハードウェアで最新 nightly の Rust 1.81 の積極的なループ展開を使ってベンチマークを自分でも回してみたが差はなく、1.5年前と同じ速度だった

  • 2023年の記事。当時の議論: https://news.ycombinator.com/item?id=34520498

    • 展開すると「Do not taunt happy fun branch predictor」の 2023年1月の議論で、コメントは 171 件あった: https://news.ycombinator.com/item?id=34520498
      1年ほど経ってから再投稿されるのは問題なく、過去スレッドへのリンクはさらに興味のある読者向けだ

  • ARM/ARM64 アセンブリにそこまで詳しくないので、x0 がどう増えるのか少し混乱した。
    const float f = *data++; は ldr s1, [x0], #4 になるが、この命令は値を読み込みつつ同時に x0 を 4 増やしているように見える。
    負の値も使えるので逆方向の走査もできそうだ。かなり面白い。x86_64 には、読み込みとインクリメントを同時に行う単一命令はないように思える

    • lods と stos は、それぞれ rsi または rdi を対象に、読み書きとインクリメントを一緒に行う。2つのメモリアドレス間をコピーしながらインクリメントする movs もある。
      通常は rcx 回繰り返す rep とともに使われる。たとえば 10 バイトの memset は、mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb の形で書ける。
      w, d, q 接尾辞を使うと、それぞれ 2、4、8 バイトずつ進む

  • 文章は良かったが、表をざっと見て比較しにくい形で µs と ns の単位を行き来していたのは残念だった

    • 文章の途中で C から Rust に切り替わったのも少し戸惑った

  • コードを最適化する前に、もっと単純な方法を先に試していなかったのは意外だ。
    アセンブリを書き直せばループ末尾では分岐が 1 つだけで済み、X1 についても比較用の減算とデクリメントを別々に行う代わりに、1 回の ALU 演算で処理できる。
    さらに言えば、foo を単にインライン化し、対応しない BL/RET トリックなしで RET 命令自体も省ける。実際にベンチマークしていないので、どれほど速くなるかは分からない

    • 誤字がある。cbnz と書いた行は cbz であるべきだ。CBZ はレジスタが 0 ならラベルへ分岐し、CBNZ は 0 でないなら分岐する