Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

September 14(Tue), 2010

[] [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命令列への変換はほぼ一瞬で終わります。

VM形式インタプリタのさらなる高速化

以下のページとか参考になるかもしれません。

ちなみに意図的に無視しましたが普通の実用的なプログラム言語の場合はソースコードを一旦構文木という木構造に変換します。その場合VM形式インタプリタではソースコード→構文木→VM命令列という変換を行ってから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などを参考にしてください。

x86/x64アーキテクチャなどの詳しい情報については

などを参考にしてどうにかしましょう。

更なる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アセンブラで機械語書く方が良かったりしないかなー、と思っています。色々なアーキテクチャに対応するのが難しいなんていうのはとりあえず一つのアーキテクチャに対応してから考えればいいんですよきっと。

*1:x86=ia32

*2:x64=x86_64=amd64!=ia64

MAEKAWAMAEKAWA 2015/05/12 13:41 参考になりました!
ありがとうございます。

最近のコメント