x86での分岐処理の高速化 (__builtin_expect)

asm

if/then/else hint? (http://gcc.gnu.org/ml/gcc/2004-01/msg00496.html)

というgccのMLに投稿された質問より。質問者いわく、

 if (<condition>)
    <fastpath>;
 else
    <slowpath>;

というコードがあり、conditionは滅多に偽にならないんだそうだ。そういうときに、吐き出すオブジェクトコードを少しでも効率的なものにできるか？というのが質問の趣旨。


回答として２通りの手法が示されており、それぞれ

  1. __builtin_expect()で分岐方向のヒントをソースコード中で静的に与える方法
  2. -fprofile-arcs したバイナリで出力したプロファイル結果(.daファイル)を利用して -fbranch-probabilities で分岐頻度のフィードバックを行う方法

である。


Pentium4を仮定した場合、どちらの方法がよりよいコードを生成するか調べてみた(gcc-3.4.1)。すると、結局のところ gcc -O2 -S した結果に優劣は見られず、同一のコードが吐かれた。どちらも、

testl %eax, %eax    # if文
jne .L4

の2行目がjnになったりする程度*1、「なるべくジャンプが起きない」方向に調整が行われるだけである。


「インテルPentium4プロセッサおよびインテルXeonプロセッサ最適化 - リファレンスマニュアル」という、インテル提供のドキュメントがあるのだが、その２章で紹介されている「分岐ヒント」命令は特に挿入されないようだ。


コードが、

  • __builtin_expect()で与えたヒントが本当である
  • __builtin_expect()を使った箇所以外の分岐は特にボトルネックにならない

の２点を満たすのなら、-fprofile-arcs を使うまでもないように思える*2


…しかし、そもそも、最近のPentiumにはBTB*3があるから、__builtin_expectすら特に使う必要もないかもしれない。むしろ、-O1 以上でデフォルトオンになる下記オプション:

-fguess-branch-probability
Guess branch probabilities using a randomized model.

このオプションを叩き切って最適化を弱めてしまいたいほどである（笑）。上記オプションが有効だと、ソースコードを変更しなくてもコンパイルするたびに違ったオブジェクトファイルが吐かれることがあるそうで。

*1:詳細は http://www.issei.org/diary/_20030224/d200101a.html#05-1-2 を参照いただくのがいいかと

*2:一応、-fprofile-arcsの出力を使った場合に有利な点がひとつだけある。.daファイルがあると -freorder-functions (これは-O2以上で自動設定) が効くので、よく呼ばれる/呼ばれない関数がそれぞれ text.hot/text.unlikely セクションに分離され、よりいっそうの高速化が期待できるかもしれない点だ..

*3:branch target buffer, 分岐履歴のキャッシュ