現代CPUにおけるコード最適化の課題
現代のCPUは、複数の命令を並行して実行する「命令レベル並列性（Instruction-Level Parallelism, ILP）」により高い性能を実現しています。しかし、命令間に依存関係がある場合、この並列性が阻害されてしまうことがあります。特に、ループ処理において前のイテレーションの結果が次のイテレーションに影響を与える「データ依存性」は、CPUのパイプラインを停滞させ、性能のボトルネックとなりがちです。
今回話題になっている記事では、ドメイン固有のコンプレッサーにおけるエンコーディング選択の最適化が例に挙げられています。エンコーディングのチャンクを決定する際に、next_j[i][j]という配列アクセスがループの各イテレーションでjの値を更新するため、jが前のイテレーションに依存してしまう構造でした。
各イテレーションのループは、前のイテレーションが終了するまで開始できない。なぜなら
jがループ全体でスレッド化されているため、メモリアクセスのレイテンシによって制限される。
これは、たとえキャッシュが効いていたとしても無視できない遅延となることが指摘されています。普段、私たちがC++やPythonでコードを書くとき、特定の処理がなぜ遅いのか、深く掘り下げてCPUレベルの動作まで考えることは稀ですが、このような低レベルな部分が全体の性能に大きく影響するというのは興味深いですね。
「無駄なif文」が性能を劇的に改善するメカニズム
本来、データ依存性を解消するためには、ループアンローリングやデータ並列化といった手法が考えられます。しかし、今回のケースでは「if (j != next_j[i][j])」という一見すると無意味な条件分岐を追加することで、性能が大幅に向上したと報告されています。元のコードは以下の通りです。
// 最適化前
uint8_t j = 0;
for (int i = 0; i < n_symbols; i++) {
j = next_j[i][j];
encoding[i] = j;
}
これを以下のように変更しました。
// 最適化後
uint8_t j = 0;
for (int i = 0; i < n_symbols; i++) {
if (j != next_j[i][j]) {
j = next_j[i][j];
}
encoding[i] = j;
}
この変更がなぜ効果的なのでしょうか？ 秘密はCPUの「分岐予測」にあります。
CPUは条件分岐が発生した際に、次にどちらのパスに進むかを推測し、予測に基づいた処理を先行して実行します。もし予測が外れると「分岐予測ミス」となり、これまでの処理を破棄して正しいパスからやり直すため、ペナルティが発生します。
しかし、このケースでは逆転の発想が用いられています。jの値が頻繁に変わらないという前提のもと、CPUがif文のボディ（j = next_j[i][j]）が実行されない可能性が高いと予測すると、CPUはループのイテレーション間に依存性がないと判断し、投機的に次のイテレーションの処理を開始します。実際にjの値が変わった際には分岐予測ミスが発生しますが、めったに変わらないという前提であれば、そのオーバーヘッドは全体の性能向上を上回るのです。
| 項目 | 最適化前（ifなし） |
最適化後（ifあり） |
|---|---|---|
| CPUの認識 | 各イテレーションがjに依存 |
ifブロックは実行されないと予測し、依存性なしと認識 |
| 実行モード | レイテンシ律速 | スループット律速（分岐予測が当たる場合） |
| 性能 | 低下する可能性 | 向上する可能性 |
CPUが
ifボディを実行しないと予測すれば、異なるイテレーション間の依存性を見なくなる。
コンパイラと開発者のジレンマ
この最適化手法の面白い点は、コンパイラにとってこのif文は「無駄」であり、通常であればコンパイラの最適化パス（特にCommon Subexpression Elimination, CSE）によって削除されてしまう可能性があるという点です。開発者はCPUの低レベルな動作を知り尽くした上で、あえてコンパイラの常識に反するコードを書く必要がありました。
通常の最適化では、分岐のあるコードを分岐なしのコードに変換する（Branchless Programming）ことが性能向上に寄与すると言われます。しかし、ここでは逆の「分岐なしのコードを分岐ありのコードに変換する」というアプローチが成功しています。これは、CPUのアーキテクチャや予測機能がどれほど複雑で奥深いかを示しているのではないでしょうか。
私も普段はPythonやTypeScriptで開発しているので、このようなCPUレベルの最適化に直接関わることは少ないですが、C/C++でパフォーマンスが求められるライブラリなどを書く際には、こういった知識が非常に重要になると感じます。特に、個人プロダクトでローカルLLMを動かすようなケースでは、推論速度に直結するため、こういったマイクロ最適化が効いてくる場面もあるかもしれませんね。
実際に試す際の注意点
このような最適化は、特定のCPUアーキテクチャやアプリケーションのアクセスパターンに強く依存します。常に効果があるとは限らず、むしろ逆効果になる可能性もあります。
実際に採用する際には、必ずプロファイリングを行い、性能向上をデータで確認することが不可欠です。また、コンパイラのバージョンや最適化フラグによっても挙動が変わる可能性があるため、注意が必要です。
