OpenCV tracに投げたPythonバインディングAPI cv.KMeans2の修正パッチが取り込まれた。
https://code.ros.org/trac/opencv/ticket/414
で投げたOpenCV Pythonバインディングのcv.KMeans2の修正パッチが取り込まれました。
https://code.ros.org/trac/opencv/changeset/4140
パッチが割とそのまま取り込まれてるのでけっこう嬉しい。以前OpenCVは「Pythonバインディングを公式サポートしてます！」と言ってるけどイマイチちゃんと動いてなかった。 - hogeなlogで投げたパッチはパッチというか「こういう原因で動かないんですけど」と説明するレベルのいい加減なパッチだったので。
北京色々
id:MKnkgwがMSRA (Microsoft Research Asia)にインターンに行っているのでちょっと北京に行ってきました。「まあどうとでもなるだろ」と思ってほぼ全く調べずに行ったんですけどまあどうにかなりました。
- Air China 羽田13:50発の飛行機が機材トラブルで飛ばない。結局北京から日本に飛んできた飛行機を使って22:30発。
- 飛行機が遅れてチェックインできる時刻に着かないので現地のMKnkgwにホテルのチェックインをしておいてもらう。予約をとったHISに頼んでホテルのバウチャーをMKnkgwにメールで送って貰った。
- ミールチケット貰ったりしてフラフラ。ふと思いつきでANAラウンジ（Air ChinaもANAもスターアライアンス加盟航空会社）に行って「Air Chinaの飛行機飛ばなくて待機してるんですけど」と言ったら入れたので寛ぐ。WiFiもPCもあるしご飯もあるしソファはやわらかいしシャワーもあってなんで漫画が無いんだろうと不思議な場所。
- 日本円から中国元に替えてもらうとき、おそらく「100元紙幣でいいですか」とか聞いてくるけど「細かくしてください」と言うべき。100元紙幣はでかいので使いにくい。
- 北京着が26時ぐらい。だだっ広い北京国際空港の明かりが落ちていて物悲しい。
- Arrival Cardを書いてなかったのでちょっと手間取る。書く場所に置いてあっただろうボールペンは当然のように無くなっていたので隣にいた老夫婦にシャープペンを借りる。ありがとうございました。
- SIMとかの自動レンタル機らしきものがあったけど深夜だったせいか在庫なしみたい。知らないけどSIMフリーの携帯とか持ってる人は利用するといいんじゃないでしょうか。
-
- 写真撮り忘れましたがコンセントもあります。あんまり多くないですけど空港内の床をくまなく見て回るとたまにある。店の中の席とかには結構あります。
- 荷物受け取りの半券無くして「あーめんどいなー」と思ってたら深夜のせいか荷物のチェックがなかった。
- 電車も無いしタクシーで中関村まで。
- タクシー乗り場に向かって歩いていると「俺のタクシー乗ってけよ！」みたいなおっさんがいたからついていったら普通の自家用車ぽい車で「空港から街まで行くのに340元くらいだ」とか言ってたので「高いよ100元だ」「ちょっと待ってくれこれけっこう安いよたくさん乗れるし」「いや一人だし」「わかった、200元なら」「いや100元」「そうだあんた煙草吸うか？」「吸わない」「おー、じゃあ150元」などといったやり取りを経て降りた。どう考えても俗に言う白タク、ぼったくりタクシー。そのまま交渉を続ければ正規のタクシーよりは安くできるのかもしれないけど怪しいし。声をかけてくるタクシー運転手についていってはいけない。
- 「タクシー乗り場」にいかにもタクシー然とした車が並んでいるのでそこから乗る。日本のタクシーと違ってまず行き先を伝えてから乗る。いきなり乗ろうとしちゃダメ。
- なんとか滞在ホテルに到着。
あとは色々遊んだりしました。楽しかったです。
ニコニコ動画にfacebookの「いいね！」をつけるユーザスクリプト (Greasemonkey)
id:amachangの主催したフェイスブック同時オン会とかでfacebook、というか「いいね！」おもしれーなーと思ったのでつけてみました。Google ChromeとFirefox（Greasemonkey)で動作を確認。
スクリーンショットについて
濡れるｯ！ - ニコニコ動画 短くて軽い動画なのでテストに便利です。
2010/10/17 5:00 ログインしなくても使えるように
ログインしてなくても「いいね！」できるようにしました。
[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アセンブラで機械語書く方が良かったりしないかなー、と思っています。色々なアーキテクチャに対応するのが難しいなんていうのはとりあえず一つのアーキテクチャに対応してから考えればいいんですよきっと。
LLVMをCMakeを使ってビルドする。あとexampleのbrainfuck実装を動かしてみる。
Building LLVM with CMake — LLVM 7 documentationを読めばできると思います。
~ $ wget http://llvm.org/releases/2.7/llvm-2.7.tgz ~ $ tar zxf llvm-2.7.tgz ~ $ cd llvm-2.7 ~/llvm-2.7 $ mkdir build ~/llvm-2.7 $ cd build ~/llvm-2.7 $ cmake .. -i Windows版のCMakeはかっちょいいGUI版があるけど、ないので-iで。なんか色々聞かれる。 Variable Name: CMAKE_INSTALL_PREFIX Description: Install path prefix, prepended onto install directories. Current Value: /usr/local New Value (Enter to keep current value): /home/hogelog/local Variable Name: LLVM_BUILD_EXAMPLES Description: Build LLVM example programs. Current Value: OFF New Value (Enter to keep current value): BrainF Variable Name: LLVM_TARGETS_TO_BUILD Description: Semicolon-separated list of targets to build, or "all". Current Value: Alpha;ARM;Blackfin;CBackend;CellSPU;CppBackend;Mips;MBlaze;MSIL;MSP430;PIC16;PowerPC;Sparc;SystemZ;X86;XCore New Value (Enter to keep current value): CBackend;CppBackend;X86 だけ設定、他デフォルトのまま。 ... ~/llvm-2.7/build $ make -j 5 5並列ビルド。数字は適当。 ... ~/llvm-2.7/build $ make install
llvmの色々な物がインストールされる。BrainFことbrainfuckをビルドして試してみる。
~/llvm-2.7/build $ make BrainF ~/llvm-2.7/build $ cp bin/BrainF ~/local/bin ~/llvm-2.7/build $ cd /tmp /tmp $ wget http://esoteric.sange.fi/brainfuck/utils/mandelbrot/mandelbrot.b /tmp $ ./bin/BrainF mandelbrot.b /tmp $ ./bin/lli mandelbrot.b.bc 下の画像。
で、速いの？
/tmp $ time lli mandelbrot.b.bc >/dev/null real 0m7.974s user 0m7.960s sys 0m0.012s /tmp $ opt -O3 mandelbrot.b.bc -o mandelbrot.b.opt.bc /tmp $ time lli mandelbrot.b.opt.bc >/dev/null real 0m11.357s user 0m11.337s sys 0m0.020s
おいどうしたんだ、最適化したら遅くなったぞ！
自分でxbyak使って書いてみたbf-jitと比較してみる。
/tmp $ time bf-jit <mandelbrot.b >/dev/null size of x86-code: 22442 real 0m3.887s user 0m3.888s sys 0m0.000s
おいどうしたんだLLVM！
このように！ LLVMを使って言語処理系を実装すると、今どきの言語処理系にはあってて当然くらいのノリで求められるけど実装が大変なJITや最適化が可能になりました！ すべての言語処理系はLLVMに帰結する時代だ！！！
自作bf-jitは「どうせbrainfuckで書くプログラムなんてそんな長くならねえし最初に全部機械語まで落としこんでいいだろ」という前提で書いてあったり、そもそもbrainfuckという言語で書かれたプログラムは一般的なプログラムの性質に合わないところが多く、そういう一般的なプログラムが高速に動くようなLLVMの最適化がbrainfuckでうまく動かなくてもそんなに不思議は無いと思います。しかし世の中にあふれるスクリプト言語のような人達は、LLVMにおける最適化にうまく一致するような性質を抱いているのか、そしてLLVMにうまくはまるようにその言語のLLVMフロントエンドを実装することというのはその言語で動くようなJITコンパイラを1から書くことと比べ本当に楽なのだろうか、そんな辺りが疑問です。luajitというLua言語の処理系がllvm-luaというllvmを利用した処理系を凌駕する性能を示しているのは、たまたまそっちを実装している人の腕が良かったからなのか、なんなのか。誰かよく調べて考えて、ブログの記事か何かにまとめておいてください。
