インタプリタ型言語を高速化する computed goto
先日Python 3.1a1 がリリースされました。 Python 3.0 は Python 2.6 に比べてパフォーマンスが悪かったのですが、Python3.1はPython2.6よりも速くなるかもしれません。
Python3.1のパフォーマンス向上は、主に次の2点が影響しています。
- ioモジュールがC言語で書き直された
- computed goto の採用 (--with-computed-gotos というconfigureオプションで有効)
computed goto という名前を聞き慣れなかったのですが、調べてみると Ruby 1.9 の VM (YARV) や、 Perl6 の VM として開発されとうとうリリースされた Parrot にも採用されている手法でした。今回は簡単に computed goto の紹介をしてみます。
とりあえず label as value
C言語の規格で規定されているgoto文は、ラベルに対して無条件ジャンプする構文です。このようにして使います。
goto label;
puts("foo"); // 表示されない.
label: //ここにジャンプする.
puts("bar");
ラベルはシンボル（名前）であって値ではないのですが、ラベルのアドレスを取得する label as value という拡張機能がgccにあります。
label as value を使うと、上記のコードは次のように書くことが出来ます。
void *jump_target = &&label;
goto *jump_target;
puts("foo");
label:
puts("bar");
ジャンプ先アドレスを変数に格納できるのがキモになっています。
computed goto を使ってswitch文を高速化
インタプリタ型言語では大抵、次のようなバイトコードに対応した処理を実行する部分(命令ディスパッチ)が実行時間の大半を占めます。
for (;;) {
code = *code_pc++;
switch (code) {
case CODE_ADD:
// 足し算処理.
break;
case CODE_SUB:
// 引き算処理.
break;
// ...
case CODE_END:
goto LOOP_END;
}
}
LOOP_END;
上記の実装では、バイトコードを1命令処理するのに次の2つの分岐を実行しなければなりません。
- switch-case による処理の振り分け
- 処理後にループ先頭に戻る
label as value があれば、switch文をジャンプテーブルへのgotoで置き換える事ができます。
static const void *JUMPTABLE[] = {&&CODE_ADD, &&CODE_SUB, ... , &&CODE_END};
code = *code_pc++;
goto *JUMPTABLE[code];
CODE_ADD:
//足し算処理.
code = *code_pc++;
goto *JUMPTABLE[code];
CODE_SUB:
// 引き算処理
code = *code_pc++;
goto *JUMPTABLE[code];
...
CODE_END:
これで、バイトコード一命令当たりのジャンプをひとつに減らす事ができました。このように、ジャンプテーブルを作って無条件ジャンプすることを computed goto というそうです。
この辺については、YARV開発者の笹田さんが YARV Maniacs 【第 3 回】 命令ディスパッチの高速化 という記事で詳しく説明されています。
どれくらい効果があるのか
Python 3.1a1 がリリースされるときに、 Python-dev ML に pybench で計測したベンチマーク結果が投稿されていました。
http://mail.python.org/pipermail/python-dev/attachments/20090308/3b6f20ff/attachment.txt
だいたい3割前後高速になるそうです。ただし、これはベンチマーク上の話であって、実際に利用される時にはインタプリタの速度が全体の実行時間に占める比重が下がるので、そこまで効果は無いそうです。 (同じスレッド上で、Djangoのテンプレートだと7-8%ほど速度が上がったという報告がありました)
まとめ
Python3.1をビルドするときには、忘れずに --with-computed-gotos を付けましょう！
