[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。
スクリプト言語処理系を高速化したくてしたくてたまらない少年少女に届け。表題の通りスクリプト言語処理系の高速化について書きます。対象言語はBrainf*ckにします。Brainf*ckというのは
Brainf*ck
Brainfuck - Wikipedia
というような言語です。要は処理系を実装するのが簡単なおもちゃ言語。おもちゃ言語ゆえに他のどんな実用的スクリプト言語処理系にも出てくるような基本的な処理だけでできているので、Brainf*ck処理系の高速化で有用なテクニックは他の処理系でもうんたらかんたら。
じゃあまず叩き台になるような処理系を書いてみましょう。言語はC++です。JavaだのPythonだので高速な処理系を記述するテクニックやらなんやらというのもありますけども、まずはごく簡単にCPUやらメモリといったものと仲の良い言語で記述することで理解を深めましょう。本当はC言語の方がシンプルでわかりやすいかもしれないのですけれども、C言語だと処理系に使う色々な部品も自作しなきゃいけないのでC++で、でもCしか知らない人でも読めるようにC++的な書き方はあまりしないようにします。
説明に使うソースコードはgithubにおいておきます。
http://github.com/hogelog/bfprocessor
叩き台となる単純なインタプリタ
ソースコードを標準入力から読み込み、文字列を辿りながら実行するタイプの処理系を用意しました。
#include <stdio.h> #include <string> #define MEMSIZE 30000 void parse(std::string& codes, FILE *input) { int ch; while ((ch=getc(input)) != EOF) { switch (ch) { case '+': case '-': case '>': case '<': case ',': case '.': case '[': case ']': codes.push_back(ch); break; } } } void execute(std::string& codes, int membuf[MEMSIZE]) { int *mem = membuf; int depth = 0; for (size_t pc=0;pc<codes.size();++pc) { switch(codes[pc]) { case '+': ++*mem; break; case '-': --*mem; break; case '>': ++mem; break; case '<': --mem; break; case ',': *mem = getchar(); break; case '.': putchar(*mem); break; case '[': if (*mem == 0) { depth = 1; while (depth != 0) { switch(codes[++pc]) { case '[': ++depth; break; case ']': --depth; break; } } break; } break; case ']': depth = -1; while (depth != 0) { switch(codes[--pc]) { case '[': ++depth; break; case ']': --depth; break; } } --pc; break; } } } int main() { static int membuf[MEMSIZE]; std::string codes; parse(codes, stdin); execute(codes, membuf); return 0; }
execute関数の中にBrainf*ck言語の定義のままの処理を書いただけです。割とでかいプログラムhttp://esoteric.sange.fi/brainfuck/utils/mandelbrot/mandelbrot.bを実行させてみます。
$ g++ -Wall -W -O2 -o bf bf.cpp $ time ./bf <sample/mandelbrot.b >/dev/null ./bf < sample/mandelbrot.b > /dev/null 223.99s user 0.00s system 100% cpu 3:43.97 total
224秒くらいかかりました。載せてるCPUはIntel(R) Pentium(R) D CPU 2.80GHzとかそんなアレらしいです。
VM形式のインタプリタ
VM形式のインタプリタとは（Brainf*ckで書かれた）ソースプログラムを仮想的な機械（Virtual Machine）命令の列に変換してから実行するインタプリタのことです。なんのこっちゃ。例えばVM形式のインタプリタを実装することで大幅な高速化を実現したruby1.9では内部的に以下のようなVM命令列に変換してから実行しています。
$ ruby1.9.1 --dump=insns -e'p 1+10' == disasm: <RubyVM::InstructionSequence:<main>@-e>====================== 0000 trace 1 ( 1) 0002 putnil 0003 putobject 1 0005 putobject 10 0007 opt_plus 0008 send :p, 1, nil, 8, <ic> 0014 leave
高速な処理系を持つとして知られているLuaの場合も内部のVM命令列を覗き見ることができます。
$ cat tmp.lua
print(1+10)
$ luac -l tmp.lua
main <tmp.lua:0,0> (4 instructions, 16 bytes at 0x9d23d10)
0+ params, 2 slots, 0 upvalues, 0 locals, 2 constants, 0 functions
1 [1] GETGLOBAL 0 -1 ; print
2 [1] LOADK 1 -2 ; 11
3 [1] CALL 0 2 1
4 [1] RETURN 0 1こういったVM形式のインタプリタにするためには、まずどういったVM命令を定義するかということも考える必要があります。特に思いつかなかったらJavaVMやらRubyVMとかなんとかかんとか既存のVMは色々あるので参考にするのも良いでしょう。というか参考にした方が良いです。
詳しい説明などはRubyist Magazine - YARV Maniacs 【第 2 回】 VM ってなんだろうなどを参考にどうぞ。
でBrainf*ckとかVM命令列にすることを考えます。といってもBrainf*ckはそもそも単機能な命令しかありませんし、そのまま対応するVM命令を定義するような感じでいきましょう。
#include <stdio.h> #include <vector> #include <stack> #define MEMSIZE 30000 struct Instruction { char op; int jmp; }; void parse(std::vector<Instruction> &codes, FILE *input) { int ch = 0; std::stack<int> pcstack; Instruction code; while ((ch=getc(input)) != EOF) { code.op = ch; switch (ch) { case '+': case '-': case '>': case '<': case ',': case '.': codes.push_back(code); break; case '[': pcstack.push(codes.size()); codes.push_back(code); break; case ']': int begin = pcstack.top(); pcstack.pop(); codes[begin].jmp = codes.size(); code.jmp = begin - 1; codes.push_back(code); break; } } code.op = '\0'; codes.push_back(code); } void execute(std::vector<Instruction> &codes, int membuf[MEMSIZE]) { int *mem = membuf; for (size_t pc=0;;++pc) { Instruction code = codes[pc]; switch(code.op) { case '+': ++*mem; break; case '-': --*mem; break; case '>': ++mem; break; case '<': --mem; break; case ',': *mem = getchar(); break; case '.': putchar(*mem); break; case '[': if (*mem == 0) { pc = code.jmp; } break; case ']': pc = code.jmp; break; case '\0': return; } } } int main() { static int membuf[MEMSIZE]; std::vector<Instruction> codes; parse(codes, stdin); execute(codes, membuf); return 0; }
Brainf*ckの命令とVM命令が1対1で対応してるのであまり変わっていません。違いは
- [と]の変換時に命令にジャンプ先情報が付加されている
- 命令列(codes)の最後に'\0'という命令が加えられ、execute中のfor文のpc<codes.size()が消えている
といったところです。
$ g++ -Wall -W -O2 -o bf-vm bf-vm.cpp $ time ./bf-vm <sample/mandelbrot.b >/dev/null ./bf-vm < sample/mandelbrot.b > /dev/null 69.13s user 0.00s system 100% cpu 1:09.12 total
224秒から69秒という3倍以上の高速化が実現できました。嬉しい！
ソースコードから一旦VM命令列に変換してから実行するのは余計な処理が増えて時間がよりかかってしまうように思えるかもしれませんが、ここではそうなっていません。これ以外のほとんどの場合もそうはなりません。普通のプログラムには何度も繰り返されるループ処理というものが存在し、それらの処理時間が総実行時間のほとんどを占めるからです。それぞれ計測してみるとわかりますがVM命令列への変換はほぼ一瞬で終わります。
JITコンパイラ
そんなんじゃ足りない、インタプリタでも機械語を吐くコンパイラと同じぐらいの速度で実行したい！ というわけで実行時に機械語にコンパイルして実行しちゃえばいいじゃんということになりました。
「でもJITコンパイラって言われてもどう実装すればいいのか謎だなー」と私も長らく疑問に思っていましたが、現在はJITアセンブラと呼ばれる便利なライブラリがいくつかあります。
- Xbyak x86*1/x64*2アセンブラ。ヘッダインクルードのみで使えるC++ライブラリ
- AsmJit x86/x64アセンブラ。ビルドが必要なC++ライブラリ
- jitasm x86/x64アセンブラ。ヘッダインクルードのみで使えるC++ライブラリ（名前がAsmJitと似てますけど別物です）
- GNU lightning 多数のアーキテクチャをサポート。仮想的なアセンブリを書くことで目的のCPUアーキテクチャの機械語を出力できる
- DynASM x86/x64アセンブラ。LuaプログラムによるプリプロセスでC言語ヘッダを出力
- CCG PowerPC/Sparc/Pentium向けJITアセンブラ。プリプロセスが必要。古そうなのでちょっと不安が残る。
- Dyninst JITアセンブラというかなんかもっと高機能で複雑な感じ。よくわからん。
ここではXbyakを用いてx86環境で動くBrainf*ckのJITコンパイラ形式のインタプリタを書いてみました。
#include <stdio.h> #include <stack> #define MEMSIZE 30000 #define CODESIZE 50000 #include "xbyak/xbyak.h" char* toLabel(char ch, int num) { static char labelbuf[BUFSIZ]; snprintf(labelbuf, sizeof(labelbuf), "%c%d", ch, num); return labelbuf; } void parse(Xbyak::CodeGenerator &gen, FILE *input, int membuf[MEMSIZE]) { gen.push(gen.ebx); Xbyak::Reg32 memreg = gen.ebx; Xbyak::Reg32 eax = gen.eax; Xbyak::Address mem = gen.dword[memreg]; gen.mov(memreg, (int) membuf); std::stack<int> labelStack; int labelNum = 0; int ch; while((ch=getc(input)) != EOF) { switch (ch) { case '+': gen.inc(mem); break; case '-': gen.dec(mem); break; case '>': gen.add(memreg, 4); break; case '<': gen.add(memreg, -4); break; case ',': gen.call((void*) getchar); gen.mov(mem, gen.eax); break; case '.': gen.push(mem); gen.call((void*) putchar); gen.pop(gen.eax); break; case '[': gen.L(toLabel('L', labelNum)); gen.mov(gen.eax, mem); gen.test(gen.eax, gen.eax); gen.jz(toLabel('R', labelNum), Xbyak::CodeGenerator::T_NEAR); labelStack.push(labelNum); ++labelNum; break; case ']': int beginNum = labelStack.top(); labelStack.pop(); gen.jmp(toLabel('L', beginNum), Xbyak::CodeGenerator::T_NEAR); gen.L(toLabel('R', beginNum)); break; } } gen.pop(gen.ebx); gen.ret(); } void execute(Xbyak::CodeGenerator &gen) { void (*codes)() = (void (*)()) gen.getCode(); codes(); } int main() { static int membuf[MEMSIZE]; Xbyak::CodeGenerator gen(CODESIZE); parse(gen, stdin, membuf); execute(gen); return 0; }
Brainf*ckの各命令についてそれぞれx86の機械語を出力し、ソースプログラムを一つのx86機械語命令列に変換し、実行するプログラムです。工夫も何もなくそのまま書きました。たいして長くなってもいませんね。なんだーJITコンパイラとか簡単ですねー
$ g++ -Wall -W -O2 -fno-operator-names bf-jit.cpp -o bf-jit $ time ./bf-jit <sample/mandelbrot.b >/dev/null ./bf-jit < sample/mandelbrot.b > /dev/null 5.26s user 0.00s system 99% cpu 5.259 total
69秒が5秒ということで13倍以上の高速化です。
Xbyakの使い方については以下のページ、xbyakのアーカイブに含まれるsampleなどを参考にしてください。
- introduction to x86-asmなどウェブ上の記事やら書籍やら
- Page UnavailableのIA-32 インテル〓 アーキテクチャー・ソフトウェア・デベロッパーズ・マニュアル
- gcc, vcの出力
などを参考にしてどうにかしましょう。
更なるJITコンパイラテクニック
ここでは「どうせbrainfuckで書くプログラムなんてそんな長くならない」という仮定でソースコードを全部一気に機械語に変換してますけど、実用プログラミング言語の実用プロダクトだとそんなことはないので実行するときに繰り返し処理する部分だけJITしたりなんだりと色々技術があるようです。詳しくは色々なJITコンパイラのソースコードを読んだり記事を読んだり論文を読んだりすると良いと思います！
おもいっきり省きましたが、処理系にJITコンパイラ機能を組み込む方法は大きく二分できます。ちまちま書くか、でかいものに組み込むか。ちまちま書くほうが楽だし割と面白いからここではそうしました。でかいものに組み込むというのは最近流行りのLLVMとかそういうのですね。組み込む対象のでかいものとしては
- PyPy RPythonというPythonのサブセットで処理系を実装することで、PyPy上で動く処理系ができます。もちろんJITもある。
- LLVM あんま知らないしさほど調べてない。AOTコンパイラインフラストラクチャとしてはなんか結構温まっきてるのかもしれない。Rubiniusやらlua-llvmやら使ってみてる人はたくさんいるぽい。
- NekoVM スクリプト言語処理系向けのVMとして設計されたVM。現在実装されてる言語はhaXeとnekoだけ。FAQで言語処理系VMとして使われる他のソフトウェアについて色々検討してて面白い。JITはx86だけっぽい。面白そう。小さいVMだし。
- Perl6のVMとして有名なParrot ……は現在JITをリライトしようとしてる、と。色々なJIT化手法を検討してあってちょっと面白い。
- nanojit 最近のFlashプレーヤのVM、TamarinのJITライブラリ。Mozilla Firefoxでも使われている。
- libjit GNUな.Net CLR環境であるDotGNUのJITライブラリ。
- JavaVMはJRubyとかJythonとかScalaとか色々ありますね。
- .Net CLRはIronRubyとかIronPythonとか色々あるらしいです。
Shootoutベンチマークなんかを見るとLuaJITが動的なスクリプト言語の実行環境なのにやたら速いです。この処理系はDynASMを使って自分でx86/x64のアセンブリをガリガリ書いてる処理系です。あと他の割と上にあるスクリプト言語処理系のRacket、V8といった処理系もやっぱりそんな感じで内部にアセンブラみたいなものを備え、自前で色々書いてる感じです。
「用意されたインフラにほげ言語を乗っけるだけで、簡単に高機能で高速な処理系になる！」というのは夢としては非常に楽しいのですけれども、こういう結果を見ると今のところやっぱりまだ自分でちまちまJITアセンブラで機械語書く方が良かったりしないかなー、と思っています。色々なアーキテクチャに対応するのが難しいなんていうのはとりあえず一つのアーキテクチャに対応してから考えればいいんですよきっと。
