役に立たない if でコード性能を4倍に高める

 (purplesyringa.moe)
1 ポイント 投稿者 GN⁺ 3 시간 전 | 1件のコメント | WhatsAppで共有
  • ドメイン特化圧縮器の最適エンコーディング経路をたどるループに 条件分岐を1つ追加 し、合成ベンチマークの実行時間を320µsから80µsに短縮
  • 各反復でメモリアドレスが直前の反復の j に依存するため、単一の mov 命令であっても 命令レベル並列性 を活用できず、メモリアクセスのレイテンシに縛られる
  • next_j[i][j] が大半の場合で既存の j と同じだという性質を分岐予測に反映すると、CPU が反復間の依存を迂回し、複数の反復を 投機実行 できる
  • コンパイラが意味的には不要な if を削除できないように volatile キャストを使用。LLVM では [[unlikely]] や __builtin_expect(..., 0) でも機能するが、volatile のほうがより良いコードを生成し、GCC でも利用できる
  • 現実的な実験では、LLVM の最適でないコード生成が原因の可能性はあるものの 約2倍の性能向上 を得られ、j の予測が難しいならレイテンシ 1 サイクルの pshufb を代替として使える

圧縮器の最適経路をたどる

  • 入力文字列を複数のチャンクに分け、各チャンクごとに最小のエンコーディングを選ぶ必要がある
    • エンコーディングごとに圧縮が得意な文字が異なるため、チャンク境界をすぐには決めにくい
    • 前回の記事 のアルゴリズムは、この問題を格子上の 最短経路探索 に変換する
  • 各セルには、次に移動する最適なセルを記録する
    • 最初のセルから最後のセルまで参照をたどれば、最適なエンコーディング順序を得られる
  • next_j を埋める最初のループは、すでに SIMD で最適化されている
    • 実際のボトルネックは、次のような単純な経路走査ループである
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • 書き込みを除いた中核演算 j = next_j[i][j] は、単一の mov 命令にコンパイルされる

単一命令でも遅くなる依存関係

  • 現代の CPU は 命令レベル並列性 を利用し、複数の命令や異なる反復の処理を同時に実行する
    • 一般的なループで i < n_symbols の判定や i++ のコストが他の処理を妨げないのはこのためである
  • しかし、相互に 依存する命令 は同時に実行できない
    • 現在の反復のメモリアドレス next_j[i][j] を計算するには、直前の反復で得た j が必要になる
    • 次の反復は前の反復の結果が出るまで開始できず、データがキャッシュにあってもメモリアクセスのレイテンシの影響を受ける

分岐予測を値予測として使う

  • この圧縮器ではチャンク数は多くないと見込まれるため、next_j[i][j] が既存の j と同じである場合がほとんどである
  • CPU に j が維持されると直接アドレス予測させることはできないが、分岐予測 を使えば同じ効果を生み出せる
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • CPU が if 本体を実行しないと予測すると、j を更新する反復間の依存がないものとして複数の反復を投機実行する
  • 条件が実際には真なら 分岐予測ミスからの回復 が発生する
    • 誤った推測で行った書き込みを破棄する
    • 正しい j を使って実行を再開する
  • j がほとんど変わらない間、ループのボトルネックはレイテンシからスループットへと移る

コンパイラに if を削除させない方法

  • コンパイラの観点では、条件分岐を加えたコードと元のコードは意味的に同じである
    • j がメモリ上にあるなら不要な書き込みや読み取り専用メモリへの書き込みを避けられるが、ここでは レジスタ値 である
    • 共通部分式除去 (CSE) のような最適化で、条件や重複アクセスが除去されうる
  • 一般的なコンパイラヒントは分岐をなくすために使われるが、ここでは逆に分岐のないコードを 分岐つきコードのまま維持 する必要がある
  • 条件判定と代入のメモリアクセスが独立しているように見せるため、代入側に volatile キャストを適用する
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • 7月13日の追記確認では、ibookstein が見つけた方法 のように [[unlikely]] または __builtin_expect(..., 0) を使っても LLVM では同じ効果が得られる
  • volatile 方式はより良いコードを生成し、GCC でも動作 する

ベンチマークで確認した性能変化

  • 合成ベンチマークではループ実行時間が 320µs から 80µs に減少し、4倍高速化した
    • 1回あたりの実行時間差は小さいが、圧縮処理の中でループが何度も実行されるため、全体コストに積み上がる
  • より現実的な実験では約 2倍の性能向上 を記録した
    • LLVM が最適でないコードを生成した影響の可能性はあるが、それでも適用する価値がある水準だった

ビットマスクベースの表現という代替案

  • このアルゴリズムでは next_j[i][j] は 2 つの値のどちらかしか取らない
    • 大半は現在の j
    • もう一方は j に無関係で、i にのみ依存する値である
  • 8 要素配列である next_j[i] を、代替値と ビットマスク の組に置き換えられる
    • この表現では if が意味的に必要なので、volatile の回避策を使う必要がない
    • ただし x86 では可変位置のビットを検査する演算が比較より遅い可能性があり、全体性能がかえって低下するおそれがある

j を予測できないとき

  • 値予測で連結リスト走査を高速化する記事 でも、同じ方法で性能を高める手法が扱われている
  • j の予測が難しいなら、ベクタインデックス演算である pshufb を使える
    • pshufb のレイテンシは 1 サイクルなので、投機実行なしでこれ以上短くするのは難しい
    • ベクタ演算によって、可能な各開始 j の経路を並列に計算できる
    • 作業を複数スレッドに分割し、結果をマージする方式も可能である

関連記事

1件のコメント

 
GN⁺ 3 시간 전
Lobste.rsのコメント

  • C++20の [[unlikely]] 属性を if 文に付ければ、clangがそのコードを削除できないようにするには十分そうです: https://clang.godbolt.org/z/r4xYWfPfe
    ほかのコンパイラでは確認していません

    • 再確認したところLLVMでは実際に動作しており、おそらく最初は効果のないGCCで誤って試していたようです
      ただし [[unlikely]] はコードを高速パスの外へ移動させるため、LLVMは以下のようにやや非効率なコードを生成します 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      次の形のほうが妥当に見えます 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      また、メモリから値を何度も読み出さないよう最適化する一方で、ホットループに命令を1つ追加することもあります。そのため volatile を使う手法は依然として有用ですが、元のコードもそのまま動作し得ると分かったのはうれしい点です

  • この手法は別のところでは 値投機（value speculation） と呼ばれています: https://mazzo.li/posts/value-speculation.html

    • この方法を再発明した後で、アリーナに格納された連結リストにも適用できそうだと最初に思ったのですが、リンク先の記事がまさにその内容を扱っていたので、自分の記事にもリンクを追加しました

  • これから2〜3年後には、開発者はLLMの出力にますます無関心になっていくでしょうが、こういう種類のブログ記事にも引き続き関心を持つのか気になります

    • 今でも関心を持つ人は非常に少なく、プログラミング全体で見ればニッチな知識です
      それでも関心のある人にとっては、今も非常に有用で良い記事です
    • Godboltはとても人気があります。コードを読まない習慣を批判されると、LLMに夢中な開発者たちは「アセンブリまで見るのか？」を大した反論であるかのように持ち出しますが、実際にはアセンブリを確認していますし、今後もそうするでしょう
      細部は重要ではないと考える開発者は、良い開発者にはなりにくいです。優れた土木技術者が大規模プロジェクトのボルトやナットにまで気を配るように、優れた開発者も小さな細部まで掘り下げるべきです。全体は細部から成り立っているので、自分が作る成果物を重視するなら避けて通れません
    • 今と根本的には変わらないと思います。現在でもほとんどの人は、人間が書いたコードのコンパイラ出力に関心がありません
      AIが書いたコードのコンパイラ出力を見る人はさらに減るかもしれませんが、基本的な構図は変わらないと思います
    • 変わるのは、関心があるかどうかというより最適化の優先順位の組み替えに近いでしょう
      10年前にBashスクリプトが少し遅いからといって、命令レベル並列性やCPUの分岐予測から考え始めることはなかったはずです。コンパイルと最適化が可能な言語で書かれた性能上の中核部分があり、その中に細かく調べるべきホットパスがあり、さらにその中にベクトル化や最新CPUの挙動差を確認する価値のあるホットループが1つか2つ存在する、ということはあり得ます
      LLMを使っていても、性能上もっともホットな箇所は例外的に直接レビューする価値があります。成果物の低い品質を意識的に受け入れる、あるいはLLMで70%を作って残り30%を手で直すやり方が85:15まで改善されることはあっても、この記事は依然として上位1%レベルの細部領域を扱っていることになります
    • C++を書かないので、そういう意味では今も直接の関心対象ではありませんが、それでも興味深く読めましたし、2〜3年後もこうした内容は引き続き面白いと思います