博士

やっほー、ロボ子！今日も元気じゃな？

ロボ子

はい、博士！今日もITニュース、楽しみにしています。

博士

今日はね、LLVMと分岐予測の話をするぞ。LLVMはRustとかZigとかHaskellのコンパイラで使われてる、ターゲットに依存しない最適化基盤のことじゃ。

ロボ子

なるほど。LLVMはコンパイラを作る上で重要な役割を果たしているんですね。

博士

そうそう！で、今日は特に分岐予測が大事って話じゃ。Jeff Deanによると、プログラマが知っとくべきレイテンシの一つに、分岐予測ミスがあるらしいぞ。2012年時点で約5nsのコストがかかってたみたいじゃ。

ロボ子

5ナノ秒ですか。一瞬に感じますが、最適化においては無視できない時間ですね。

博士

じゃろ？CPUの中にはプログラムカウンタ(PC)っていう、次に実行する命令のアドレスを記録するレジスタがあるんじゃ。最新のCPUは命令パイプラインっていうのを使ってて、命令を並行して処理してるんじゃ。

ロボ子

命令パイプライン、効率的な処理に不可欠な技術ですね。

博士

そこで登場するのが分岐予測！CPUが条件分岐命令に出会った時、どっちに進むか予測して、予測に基づいて命令を実行するんじゃ。

ロボ子

もし予測が当たれば良いですが、外れた場合はどうなるんですか？

博士

予測が当たればパイプラインはフルスピード！でも外れると、CPUは投機的に実行した命令を全部捨てて、正しい場所からやり直さなきゃいけない。これが大きなペナルティになるんじゃ。

ロボ子

それは痛いですね。分岐予測の精度が重要になるわけですね。

博士

そういうことじゃ！例えば、ソートされたデータ（安いものから高いものへ）を処理する場合、CPUの予測はめっちゃ正確になるんじゃ。でも、ランダムなデータだと、CPUはしょっちゅう間違った推測をして、命令を破棄することになる。

ロボ子

ソートされたデータとランダムなデータで、そんなに差が出るんですね。

博士

分岐予測がないと、分岐条件の結果を待つ間、パイプラインが止まって、ハードウェアユニットが暇になっちゃう。もったいない！

ロボ子

確かに、それは避けたいですね。

博士

最近のCPUだと、パイプラインの深さが14ステージ、周波数が3GHzくらいじゃ。分岐予測ミスのペナルティは15-22サイクル、分岐解決時間はレジスタ比較で2-3サイクルくらいじゃ。

ロボ子

CPUのスペック、細かいですね！

博士

分岐予測の精度は、最近のCPUだと約90-97%！規則的なパターン（ループとかソートされたデータ）だと95-97%、普通のアプリケーションだと90-95%くらいじゃ。

ロボ子

かなり高い精度ですね！

博士

分岐予測を有効にすると、実行時間が56%も節約できるらしいぞ！

ロボ子

それはすごい！

博士

対策としては、できるだけソートされたデータを処理したり、似たような操作をまとめてバッチ処理したり、パフォーマンスが重要な場所ではランダムな条件付きロジックを避けるのが良いぞ。

ロボ子

なるほど、データ構造やアルゴリズムの工夫で、分岐予測を助けることができるんですね。

博士

そういうことじゃ！ロボ子も賢くなってきたのう。ところでロボ子、CPUが分岐予測を外しまくるとどうなるか知ってるか？

ロボ子

えーと、性能が落ちる、以外に何かありますか？

博士

CPUがスネて、言うことを聞かなくなるんじゃ！…って、冗談じゃ！

ロボ子

もー、博士ったら！