なんだか分岐予測器で当てれそうなところを当ててくれなかったことがあったので、Intel CPUの分岐予測器はどんな時に分岐予測を当てることができるのかを調べてみました。

実際に調べてみると、ループのような単純な場合であっても非常に複雑怪奇な挙動を示すため、内部構造がどうなっているか全く推測できませんでした。

とりあえず、結果だけまとめておきます。

実験方法

単純なループを10億回くりかえすだけの以下のアセンブリコードを実行したときの分岐予測ミス回数を計測しました。

        .globl  main
main:
        xorl      %eax, %eax
L6:
        xorl      %edx, %edx
L7:
        incl      %edx
        cmpq      $__, %rdx
        jb        L7
        incl      %eax
        cmpl      $1000000000, %eax
        jb        L6
        ret

ループ回数は、以下のスクリプトで設定しました。

for i in $(seq 1 100); do
 sed s/__/$i/ main.s > m.s
 gcc m.s
 perf stat ./a.out
done

実験に使用したCPU

ここ10年くらいのXeonで実験することができました。

Xeon X5550（Neharem EP、2009年）
Xeon E5-2690（Sandy Bridge EP、2012年）
Xeon E5-2643 v3（Haswell EP、2014年）
Xeon E5-1620 v4（Broadwell EP、2016年）
Xeon Gold 5115（Skylake SP、2017年）
Xeon Gold 6126（Skylake SP、2017年）
Xeon platinum 8280（Canscadelake SP、2019年）

結果

Xeon X5550（Neharem EP、2009年）

ループが64周以下ならば、分岐予測ミスは発生しない。
ループが65周以上であれば、（おそらくループ脱出時に）分岐予測ミスが1回発生する。

分岐履歴長が63であることを示唆しているように思えます。

非常に素直な結果になりました。

Xeon E5-2690（Sandy Bridge EP、2012年）

ループが33周以下ならば、分岐予測ミスは発生しない。
ループが34周以上であれば、（おそらくループ脱出時に）分岐予測ミスが1回発生する。

分岐履歴長が32であることを示唆しているように思えます。

非常に素直な結果ですが、なぜ3年前のプロセッサよりも劣化しているのでしょうか。ループ以外の分岐予測の精度が上がったと信じたいです。

Xeon E5-2643 v3（Haswell EP、2014年）

ループが35周、40周、42周、44周、の場合にはループ一周につき1回以上の分岐予測ミスが発生する。
ループが53周、54周、55周、60周～74周、91周～94周の場合はループ一周につき1回未満だが0.1回以上の分岐予測ミスが発生する。
それ以外の場合でループが59周以下であれば、分岐予測ミスはほとんど発生しない。
ループが75周～90周の場合、ループ一周につき1.2回程度の分岐予測ミスが発生する。
ループが95周以上であれば、（おそらくループ脱出時に）分岐予測ミスが1回発生する。

わけの分からない結果になりました。

Xeon E5-1620 v4（Broadwell EP、2016年）

やるたびに結果が変わってよくわかりませんが、

ループが35周、40周、42周、44周の場合はループ一周につき1回程度の分岐予測ミスが発生しやすい
ループが40周以上だと当てられなくなる時と、60周以上だと当てられなくなる時がある

ループ35周、40周、42周、44周の時に当てられないという挙動が、Xeon E5-2643 v3（Haswell EP、2014年）と酷似しています。

Xeon Gold 5115（Skylake SP、2017年）と Xeon Gold 6126（Skylake SP、2017年）

やはりやるたびに結果が変わってよくわかりませんが、

ループが35周未満であれば、分岐予測ミスはほとんど発生しない
ループが35周のとき、分岐予測ミスが発生しやすい

やはり35周のところに何かがあるようです。

Xeon platinum 8280（Canscadelake SP、2019年）

ループが23周以下ならば、分岐予測ミスは発生しない。
ループが24周～28周の場合はループ一周につき1回未満だが0.05回以上の分岐予測ミスが発生する。
ループが29周以上であれば、（おそらくループ脱出時に）分岐予測ミスが1回発生する。

素直な結果に戻りましたが、7年前のプロセッサよりもさらに劣化しています。 "improved branch predictor" とはいったい何だったのでしょう……

まとめ

Intel CPU にはループ予測器はついていなさそう
ループ脱出の予測に関しては、Intel CPUはここ10年で全く進化していない（どころか当てられるループ周回数が減少している）
30周程度のループでも当てられないことがある

35周の時に当てられない現象は、分岐命令のアドレスなどを変えて再検証する必要あり

よーる

Intel CPU の分岐予測器を調べてみた（ループの場合だけ）