Let's start Scheme

2012-07-31

Racketが異様に速い

Sagittariusはfibを走らせる程度ならGaucheやYpsilonと同じくらいの速度で走るのだが、Racketはさらにその倍くらいの速度が出る。
正直、なにこれ?状態なのだが、ちょっとテストコードを書いてみてなんとなくどうやっているのかが分かった。(追いつけるという意味ではない)。
以下がテストコード。
#include 

SgObject fib(SgObject n)
{
  if (Sg_NumLt(n, SG_MAKE_INT(2)))
    return SG_MAKE_INT(1);
  return Sg_Add(fib(Sg_Sub(n, SG_MAKE_INT(1))),
  fib(Sg_Sub(n, SG_MAKE_INT(2))));
}

int main(int argc, char **argv)
{
  int n = atoi(argv[1]);
  GC_INIT();
  printf("%d\n", SG_INT_VALUE(fib(SG_MAKE_INT(n))));
  return 0;
}
Schemeじゃないじゃん!イメージとしては、SchemeのコードをCにしただけ。ちなみに、以下のコマンドで実際に動くバイナリが出る。(メモリアロケートしてないからGC_INIT()は要らないんだけど)
% gcc -O3 test.c -o fib `sagittarius-config -I` -DHAVE_CONFIG_H -lsagittarius `sagittarius-config -L` -lgc
-DHAVE_CONFIG_Hとかちょっとダサいが、まぁそれは置いておく。(0.3.3辺りからいけるはず、ただ明文化はあえてしてない)
これでできた実行ファイルを実行するとRacketより多少速く動いた。ということは、Racketはこれに+α程度の処理をくっつけた何かしらで動いているということなのだろう。バイトコード動かすVMだと思っていたのだが、違うのだろうか?

さて、ここからは考察。
JITを実装していて気づいたことがあって、
  1. VMオプコードのディスパッチは処理時間をそんなに悪化させていないということ
  2. FRAMEとRETインストラクションで起きる継続フレームのPUSHとPOPがやたら遅いということ
2番目は現状のVMを貫くならどうしようもなくて、やれそうなこととしては継続フレームのサイズを減らすことくらいなのだが(現状では6ワード)、正直現状では削れて1ワードかなぁといったところ。しかも、その1ワードはfibを走らせるだけなら使われることはない部分だったりする。
ものすごく気合を入れて頑張るなら、上記のプログラムは末尾再帰に置き換えることができるので、コンパイラがそんな雰囲気を感じたら、置き換えるようにするとかだろうか?そうすればFRAME命令はなくなるし、速度も改善されるが、そうするとプログラムが書いてある通りにコンパイルされてないよな?(やれるやれないは別にして)
(どうでもいいのだが、Racketでfibを末尾再帰で書いても速度が2倍弱程度しか改善されない。Sagittariusでは50倍くらい。いろいろ不思議な処理系だ)

No comments:

Post a Comment