x86とGCCと分岐と私

mrubyのVMはoptableに命令と実際のアドレスの変換テーブルをおいて、gotoのときにそれを使って変換→ジャンプをしているのでダイレクトスレッデッドじゃなくてトークンスレッデッドじゃないのかと思う今日この頃。識者の意見求む。
今回はCPUのアーキテクチャに深く依存する分岐予測の話。長いしわかりにくい。他人への説明用ではなく自分用の整理と考えられたし。


1.分岐とは

アセンブラでいうJMP系、CALL系、RETを言う。プログラムカウンタを変更して任意の位置に実行位置を移動する。Cだと制御系の文(if、while、for、gotoなど)や関数呼び出しがそれらの命令に変換される。CPUのレベルでは条件無しのJMPも分岐と表現する。
CPUアーキテクチャ側から見ると分岐命令は大きくわけて4つ。
・無条件分岐
・条件分岐
・間接分岐
・リターン
である。

2.分岐予測とは

CPUはIntelで言うとPentiumからパイプライン処理が導入されて、先の命令を事前に予測しておくことが重要になった。これは、パイプラインが命令を細かく砕いてロード・演算・ストアなどのステージにわけて、全部のステージでそれぞれ違う命令を同時に動かして流れ作業的に実行するためだ。
条件分岐する際、条件を判定しおわった時点で既に先の命令の実行に取り掛かってしまっている。ifなどを実行するときにはCPUは分岐予測という機構を使ってどっちに分岐するかを予想して、恐らく次の命令はこれだろうと決め打ちして実行しているから、はずれるとパイプラインに入っている命令は無意味になって最初に戻ってやり直しになる。これを分岐予測ミスと言い、いまどきのCPUだと10サイクル以上のペナルティとなる。従って、分岐予測のヒット率はCPUの速度に決定的に影響する。プログラムを書く場合も、分岐予測が当たりやすいように書くことで性能を飛躍的に上げることができる。少なくとも理論的には。

3.予測の仕掛け

いまどきのCPUは高性能な分岐予測機構を持っているのでヒット率は90%を超えるらしい。
基本的には条件分岐の場合はその命令と分岐の履歴を持つブランチテーブルバッファ(BTB)にアドレスと結果を書き込み、次からそれを参照して予測する。履歴があるので繰り返しパターン(ずっと同じ側に分岐する、分岐する/しないを交互に繰り返すなど)は正確に予測して当ててくる。ゆえにランダムで50%で分岐するコードは50%ミスる。そういう場合は分岐じゃなくCMOVやSETCCといった命令を使うと効率が上がる、とIntelの最適化マニュアルに書いてあったが、おそらくそのような命令はCコンパイラは吐き出せない。
間接分岐は古いCPUでは予測すらできないが、いまどきのCPUでは前回1回分のジャンプ先をBTBに保存し、同じところに飛ぶだろうと予測する。
リターンはコールスタックというBTBとは別の領域で管理されCALLが実行されたアドレスの次に戻るように予測される。コールとリターンの関係を崩すようなコーディング(昔よくやってたアドレスをpushしてretとか)をするとコールスタックが使えなくなって遅くなる。
BTBのサイズは有限なので分岐命令が多いとなんらかのアルゴリズムで使わないものから捨てられる。従って、BTBに情報が無い場合にどう分岐するかを表すデフォルトの予測(静的予測という)は意外に重要である。

4.静的予測

BTBを使って予測するというレベルではだいたいどのCPUでもそのようになっている。条件分岐を当てるために履歴を参照するのは有効な手法らしい。
対してBTBに情報が無い場合の予測はCPUごとに違うことを覚悟したほうがいい。Intelの場合でもPentium4以前とそこより後では静的予測の手法が異なる。
Pentium4以前は戻るジャンプはループっぽいから分岐する、進むジャンプは分岐しない、と予測していた。新しいのは分岐予測機構がなにかしらのアルゴリズムで予測してくれるらしい。結局のところよくわからないのでPentium4にあわせて静的予測されると考えておけばよい、とIntelのマニュアルには書いてあった。もしかすると実は変わってないのかもしれない。
間接分岐の場合、BTBに情報が無いと飛び先に関するネタが全く無いので分岐しないと予測される。つまり次の命令にジャンプするという無駄命令なのではないかと考えるわけだ。これについてはそうするしか無いのでどのCPUでも変わらないかもしれないが、IntelマニュアルによるとUC2命令というのがあって、これを間接分岐の次に置いておくと静的予測時に次の命令を実行しなくなるのだそうな。間接分岐命令の直後にデータを配置していた場合なにを実行ようとして変なことになるかわからないから、そのような対策が用意されているのだろう。
ここまでがハードウェアまわりの前提知識。

5.スレッデッドコード

VMの実装は簡単なものならswitch-caseだが、凝ったものだとスレッデッドコードになる(mrubyVM)。もう一歩進むとダイレクトスレッデッドコード(Ruby1.9VM)。
詳しい話はるびま8号の「YARV Maniacs 【第 3 回】 命令ディスパッチの高速化」を参照すると大変わかりやすい。
http://jp.rubyist.net/magazine/?0008-YarvManiacs
面倒なのでこれを読んだとの前提で端折る。同じこと書いても意味が無い。

6.GCCのコード

mrubyのVMは上記YARVManiacsによるとスレッデッドコードなので、命令の実行コードごとに存在するgotoすなわち間接分岐それぞれがBTBに保存されて、同じ命令パターンだと速くなる。そして、いままでの説明を元に考えると、VMのCで書かれている命令の順番を実行されやすい順番に並べておけば静的予測も当たりやすくなって性能が上がる。はずだ。
ところがこれはそのようにならない。上記YARVManiacsの「嫌な落とし穴」というところにチラっと書かれている現象が原因だ。
GCCコンパイル時の最適化で同じコードをまとめる。これは実行コードが減って命令キャッシュ効率が上がるという効果があるので、確かに最適化としては正しい。
しかし、mrubyVMで言うところのNEXTマクロのコードもまとめられてしまうのだ。これがまとめられると間接分岐の予測のヒット率がガタ落ちになるし、静的予測を考慮して命令を並べても全く意味が無い。
x86用最適化をしているはずなのにその最大シェアを持つIntelCPUアーキテクチャの動きをGCCは考えていない。と言える。
ちなみにRuby1.9ではこの対策としてJMP命令をインラインアセンブラで生成している。

7.条件分岐と間接分岐を使い分ける

間接分岐はたかだか前回の履歴しか見ないが、条件分岐はもっと昔の履歴を持つ。これは32/64bitのアドレスを持つか、飛ぶ/飛ばないのbit情報を持つかの違いである。空間効率が違うのだ。
この差をうまいこと使うと予測ヒット率を向上させることができる。
例えば間接分岐の飛び先が5パターンぐらいあるとして、そのうち1パターンが50%だったとする。その50%になるパターンが何かしらの繰り返し法則がある場合に、そのパターンのみをif文で分けて固定で分岐させてやる。if文の条件分岐はBTBによりいい感じに予測され、残りの50%だった場合に間接分岐予測が行われる。
分岐は増えるが効率は上がる。Intelの最適化マニュアルに書いてある手法なので、つまりIntelオススメの間接分岐予測ミス対策だ。ただしこの方法で効率の上がる部分を見つけ出すのは難しいらしい。

8.実験してみる

いつものようにmrubyVMで実験してみよう。
命令パターンといってもよくわからない。ぱっと思いつくのはOP_SENDの前にOP_LOADNILが出てくることが多いということぐらいだが、OP_LOADNILの後にはOP_ADDとかOP_LTとかの演算子系命令が来ることも多いので、ダメかもしれない。ある程度イマイチなほうが面白いのでそれで試してみる。
まずVMのコードのOP_LOADNILの位置をOP_SENDの前に移動する。しかしそれだけではGCCに静的予測の幻想をぶち殺されてしまうので、上記Intelおぬぬめ手法を取り入れてみる。OP_LOADNILの後にはOP_SENDがたくさんくるはずだ。と考えるんだ。
こんな感じに。

    CASE(OP_LOADNIL) {
      int next_opcode;

      /* A B    R(A) := nil */
      int a = GETARG_A(i);

      SET_NIL_VALUE(regs[a]);

      //NEXT;

      mrb->arena_idx = ai; i=*++pc;
      next_opcode = GET_OPCODE(i);

      if (next_opcode != OP_SEND) {
        goto *optable[next_opcode];
      }
    }

    L_SEND:
    CASE(OP_SEND) {
// (後略)
//   :

次の命令がOP_SENDの場合にoptableの参照とgotoが省かれる。ただし、このコードだと間接予測まわりは元のままなのでもうちょっと改善の余地はあるかもしれない。なんか思いついたらまた試すことにする。
ベンチ用コードはいつものやつ。

from = Time.now
10000000.times do
end

to = Time.now
p to-from

命令列も参考に置いておこう。

irep 150 nregs=6 nlocals=4 pools=0 syms=3
000 OP_ENTER    0:0:0:0:0:0:1
001 OP_LOADI    R2      0
002 OP_MOVE     R4      R2
003 OP_LOADSELF R5
004 OP_LOADNIL  R6
005 OP_LT       R4      :<      1
006 OP_JMPNOT   R4      017
007 OP_MOVE     R4      R1
008 OP_MOVE     R5      R2
009 OP_LOADNIL  R6
010 OP_SEND     R4      :call   1
011 OP_MOVE     R4      R2
012 OP_LOADI    R5      1
013 OP_LOADNIL  R6
014 OP_ADD      R4      :+      1
015 OP_MOVE     R2      R4
016 OP_JMP              002
017 OP_LOADSELF R4
018 OP_RETURN   R4

見たところOP_LOADNIL→OP_SENDはループ中に1回しか出てこない。OP_SEND以外はOP_LTとOP_ADDが交互に来るのでこれはNEXTが専用コードになったとしてもばっちり予測ミス連発だ。ただし、OP_SENDをチェックする条件分岐は分岐する/しない/しないを繰り返すパターンとなる。予測ヒット時にgotoが省かれるという効率向上策の効果がわかる。
比較。

D:\test>mruby test.rb
2.484375

D:\test>mruby_test test.rb
2.328125

昨日のwhile最適化よりもずっと速くなった。これは面白い。
ただ、この効果は分岐予測機構があるCPUに限定される。組み込み向けCPUではそのようなものが無い場合もあるから、そういうのを考えると単純に分岐することでgotoが減るという効果(分岐処理は増える)を狙うことになるから、分岐する場合がほとんどじゃないと逆効果になりそうではある。
ちなみにIntel最適化マニュアルで勉強したがうちのCPUはAMDだ。