IntelとAMDの間接分岐アーキテクチャ

ちょっと前にmrubyはダイレクトスレッデッドコードじゃなくてトークンスレッデッドコードだ、と書いた。じゃあ、ダイレクトスレッデッドコードを実装したらどうなるのか、ということで試していた。

そもそもダイレクトスレッデッドコードとは何かと言うと、短くまとめるとiseqの命令それぞれ1対1で対応する命令のアドレス列を生成して、それを使ってgotoする仕組みである。
現在のmrubyはiseqからOPを取得→マスク→optableを参照→gotoとなっているが、ダイレクトスレッデッド化するとiseqからアドレスを取得→gotoとなってNEXTルーチンが短くなる。結果として速くなる。はずだ。実際、手元のコードはNEXTルーチンのアセンブラ命令が7個→5個に減った。
のだが、なぜか実行速度は変わらなかった。

ダイレクトスレッデッドの欠点としては、
・iseqと同じサイズ(64bit環境では倍)のアドレス列を持つのでメモリを食う
・アドレス変換をするオーバーヘッドがある
・効率を上げるためにiseqにアドレスを持たせるとROM化できなくなる
で、利点は
・速い
となる。

まあ、その唯一の利点がまるで発揮されていない以上どうにもならない。ここのところ改善策が無駄足に終わるのが続いているので、mrubyからいったん離れて原因を探ってみる。
いまのところ怪しいのは間接分岐予測だ。IntelCPU用に最適化しているが、AMDだから動きが違う、のかもしれないので、まずはそこから調べてみよう。うちにIntelCPUのPCがあれば話は早いのだが。

会社のPCがIntelのCore2だったので小さいベンチを作って計測してきた。forループで10億回まわして、中に以下の処理を突っ込んだ3パターン。アセンブラでのループ内の命令数と、かかった時間もつけておく。
(a)無条件分岐1回(11命令、2.5秒)
(b)必ず同じところに飛ぶ間接分岐1回(16命令、3.5秒)
(c)2つの飛び先を交互に繰り返す間接分岐1回(16命令、10.5秒)

PCのCore2は2.83GHzだった。まあ、どんぶり勘定で3GHzとしておこう。1秒間に30億クロックとなる。上記(a)では2.5秒なので使ったクロックは75億クロック。これをループ数の10億で割ると7.5。1ループにつき7.5クロックかかった計算だ。命令数が11なので平均してクロックあたり1.47命令となる。最適化していないのでそんなもんか。
(b)では同様の計算でループあたり10.5クロック。クロックあたりの命令数は1.52となる。毎回同じ飛び先の間接分岐は予測がヒットするので速いということだ。
(c)は飛びぬけて時間がかかっていて、ループあたりのクロックが31.5となった。これが遅いということは、Intelの言うとおり間接分岐は前回の飛び先と同じであると予測していると考えられる。また、このデータからみた間接分岐の予測ミスのペナルティは約20クロックとなる。

次にうちのAMD AthlonII X2 235e(K10 Regor 2.7GHz)で同じことをためしてみよう。ソースは持ち帰れないしコンパイラも違うのでまったく同じではない。念のため。
K10アーキテクチャでは間接分岐専用のエントリが512個用意されていて、しかも履歴を参照するらしい。間接分岐が遅いどころか仕様的にはIntelよりも高性能である。
ベンチはせっかくうちで実験するのでmruby用メソッドとして実装してみる。でも面倒なのでkernel.cに突っ込んでしまおう。

//mrb_init_kernel()に追加
  mrb_define_method(mrb, krn, "bench1",                     mrb_bench1,                      ARGS_NONE());
  mrb_define_method(mrb, krn, "bench2",                     mrb_bench2,                      ARGS_NONE());
  mrb_define_method(mrb, krn, "bench3",                     mrb_bench3,                      ARGS_NONE());

ベンチのコードはちょっと長いが。

mrb_value mrb_bench1(mrb_state *mrb, mrb_value obj)
{
  int i = 0;

label1:
  goto label2;
label2:
  i++;
  if (i < 1000000000) goto label1;

  return mrb_nil_value();
}
mrb_value mrb_bench2(mrb_state *mrb, mrb_value obj)
{
  int i = 0;
  int a = 0;

label1:
  switch(a) {
  case 0:
    i++; a = 0;
    break;
  case 1:
    i++; a = 0;
    break;
  case 2:
    i++; a = 0;
    break;
  case 3:
    i++; a = 0;
    break;
  case 4:
    i++; a = 0;
    break;
  }

  if (i < 1000000000) goto label1;

  return mrb_nil_value();
}
mrb_value mrb_bench3(mrb_state *mrb, mrb_value obj)
{
  int i = 0;
  int a = 0;

label1:
  switch(a) {
  case 0:
    i++; a = 1;
    break;
  case 1:
    i++; a = 0;
    break;
  case 2:
    i++; a = 0;
    break;
  case 3:
    i++; a = 0;
    break;
  case 4:
    i++; a = 0;
    break;
  }

  if (i < 1000000000) goto label1;

  return mrb_nil_value();
}

bench1はGCCの最適化を切ってもgotoが消されてしまうので、しょうがないとしてそのままにしておいた。
間接分岐のテストはbench2と3だ。switch-caseでテーブルジャンプになるのは試した限りでは最低5個だったので、5個のcaseにしてある。それ未満だとifが並ぶ。bench2のほうはずっとcase0、bench3のほうはcase0と1を交互に呼ぶようになっている。よね？
ベンチ用Rubyコード。

from = Time.now
bench1
to = Time.now
p to-from

from = Time.now
bench2
to = Time.now
p to-from

from = Time.now
bench3
to = Time.now
p to-from

べたべたである。
結果。

D:\test>mruby_test test.rb
2.53125
4
3.984375

無条件分岐はgotoが消えているぶんとクロックが低いぶんで帳消しだ。
問題は間接分岐で、交互にとんだほうが速い。まあそれは誤差として、誤差で逆転できるほど交互に繰り返す間接分岐がK10では速いということになる。履歴を参照して繰り返しパターンを予測できるというのは本当らしい。
そうなってくると例えばNEXTルーチンの分散で遅くなる理由がナゾである。この不思議が解決しないとダイレクトスレッデッドコードを自慢できない。そのうち原因の仮説を思いついたらまた検証してみる。

p.s.ちなみに分岐予測などのアーキテクチャの情報は、検索してみたらこんなものがでてきた。英語だが。
http://www.scribd.com/doc/86649302/16/Branch-prediction-in-AMD-K8-and-K10
相当突っ込んだことが書いてあるので興味があるなら辞書を引きながらでも読んでみることをオススメしておこう。俺は英語がわからないので読める単語だけ拾って読んだ( ｰ`дｰ´)ｷﾘｯ