いかにしてRubyを高速化するか？ コミッター・卜部昌平が挑んだ「Deoptimization Ruby」の軌跡
Rubyの高速化に取り組む卜部昌平さんが、その着想やデザイン、実装について解説します。
Ruby1.8.5、1.8.6、1.8.7のリリースマネージャを務め、現在は株式会社マネーフォワードでフルタイムのRubyコミッター職として働く卜部昌平（うらべ・しょうへい／@shyouhei）さんは、deoptimizationと呼ばれるアプローチを用いてRubyの高速化に取り組んでいます。
本稿ではその足跡から、いかなる思想のもとでデザインや実装を行っているかを、卜部さん本人が解説します。
- Deoptimizationの着想に至るまで
- デザインとは、やらないことを決めること
- 「最適化が間違っていたら、戻す」をどう実装するか？
- インストラクションを消し、跡地をnopで埋める
- 「メソッド呼び出しが省略可能であること」を判定するために
- 省略可能な呼び出され方を増やす
- 大き過ぎる問題ではなく、実現できる規模の問題に取り組む
Deoptimizationの着想に至るまで
言語を高速化するときに、どんな手段によって高速化すればいいのか。
当然、無駄を省くことは王道ではある。しかしながら、Rubyのように二十余年にもわたって開発が続いているプログラムで、本当に無駄な処理というものは少ない。それもそのはずで、本来処理とは必要に迫られて行われるものである。無駄かもしれないが念のため二回代入します、みたいな話は通常あまり存在しないか、過去にあったとしてもすでに削られていることがほとんどだろう。
にもかかわらず、一見同じと思われるような処理を書いても、例えばJavaScriptとJavaでは実行速度が異なるといった事態は起こる。これは何なのかというと、無駄があるというよりも、処理の特殊化が足りていないという話でうまく説明ができることが多い。この処理では絶対に変数に文字列は来ないからこの分岐は不要とか、そういった条件が処理系からうまく判定できないという話である。
そこで、最適な挙動をするために必要なだけの情報をプログラムが与えれば良いのだ、という発想もあり得て、例えばC++だとpartial template specializationなどは、そういう文脈で作られた機能だと理解している。これはこれで有効なのだが、プログラム側の書き直しが不可避であるため、既存コードの高速化という用途ではなかなか採用しづらい。今すでに動いているプログラムを、その挙動を変えないままで高速化したい場合、どうすればいいのか。
これを実現するには、うまく条件が判定できないところを、「うまくなくてもともかく判定する、間違っていてもしょうがない」という倒し方にする。そういうことも選択肢となる。時々ダメでも、だいたい動けば御の字だ。もちろん、ダメなときにダメなままで動かすのはNGだから、間違っていたら検知してフォールバックしていくことになる。フォールバックは無駄な処理だからオーバーヘッドになるが、だいたい動いていればだいたいは速く動くし、まあそれでよし、ということにする。
提案手法の基本的な考え方はこれだ。Deoptimizationと呼ばれていて、Ruby固有の話ではないし、特にJVMにおいては、かなり古くから適用されているテクニックである。それをRubyに適用するにあたって、さらにいくつかのポイントが生じている。
デザインとは、やらないことを決めること
まず、決定すべきデザインチョイスとして「何をやらないか」が非常に重要である。
デザインとは「やらないことを決めること」であると言っても過言ではない。処理系の高速化を考え始めると「高速に動くRubyをコンパイルするために、専用のCコンパイラを書こう」とか、いくらでも作業を水増しすることが可能で、このCコンパイラを自作することに妥当性を見出すことも不可能ではないが、しかしながら実現までの難易度が上昇するのは間違いない。
たいていの場合、海のものとも山のものともつかないアイディアに突っ込める工数なんて自分一人が関の山なわけで、ともかく最小の手数で動くところまで持っていかないと、話がそもそも始まらない。そこで今回は、以下のような「割り切り」を行った。
- 処理系の書き直しのようなことはやらない
- 既存のコードをできるだけ削らない
追加だけで済ませる - 新しい依存を増やさない
例えば、新しいライブラリに依存しない
新しいCPUでしか動かないというようなことをしない - JITとかやらない
既存の処理系のVMで完結させる - （VMの）プログラムカウンタを変更しない
最後の項だけ若干解説すると、最適化をすることは「プログラムの意味を変えないまま、形を変える」という行為なわけだけど、そうすると普通はプログラムのサイズが変わる。例えば、プログラム中に無駄なパスを発見してdead code eliminationすると当然縮むが、最適化の内容によっては伸びることも十分に考えられる。しかしながら、実行途中でプログラムが伸びたり縮んだりするのはなかなか強烈だ。きちんと辻褄が合うように考慮漏れをなくさないと容易に破綻するので、これを避けるのが堅実だと判断した。
プログラムカウンタをいじらないということは、できる最適化にかなり制限を加える。もちろん、JITしないこともまた、高速化に対しては悪影響だろう。このように、今回の「割り切り」は、ある意味で効果に疑問符がつく面がある。
しかし、そこを怖がって八方美人のデザインをやろうとするのは、破綻が約束された道である。残念な結果が出ることと、結果がまったく出ないのでは、残念な結果が出た方が、比べ物にならないほどマシだ。
「最適化が間違っていたら、戻す」をどう実装するか？
そういうわけで具体的な実装に取り掛かるのだが、大きく分けて以下の調査検討項目がある。
- VMにどのようなデータ構造があり、
それをどのように変更するか？ - 処理の最適化をどのように行い、
そしてどのように最適化を戻すか？ - 最適化が間違っていたことを、どう判定するか？
大きな流れとしては、データ構造が先だ。処理だけを見てデータ構造を確認しないのは、目隠しで高速道路をドライブするような行為であり、データ構造だけを見て処理を確認しないのは、地図を見ただけでドライブしないような行為である。もちろん、どちらを欠いても目的地には到達しないが、ドライブした後に地図を見るのはナンセンスだ。ものには順番というものがある。
そこで、RubyVMがどのようにプログラムを保持しているかを見ることになる。これは、RubyプログラムからRubyVM::InstructionSequenceというクラスで見えているので、この定数がどこで定義されているかをフックに、ソースコードを読んでいけば理解できる。
枝葉が多いので途中は省略するが、結論を言うとstruct iseq_constant_bodyの中に、動的に確保した配列として保存されている。
struct rb_iseq_constant_body { /* … */ unsigned int iseq_size; const VALUE *iseq_encoded; /* … */ };
github.com/ruby/ruby/blob/v2_5_0/vm_core.h#L299
今回は上記の通り、プログラムカウンタ等をいじらないので、見るべきはここだけだ。
もし、それも変更を許すなら、プログラムカウンタがどのように保存されているかも発見しないといけない。これはスタック上に保存されているから、スタックフレームの仕組みを理解する必要がある。それから、例外が起きたときのために表引きを行う部分があって、内部的にcatch tableと呼ばれているが、そこにもプログラムカウンタが関与しているから確認しよう。最後に、最近のrubyでは実行トレースのためにプログラムカウンタと行番号の対応を保存していて、これもよしなにいじる必要があるだろう。
今回はその辺りをザックリと省略して、いきなりこの配列を破壊的に変更すれば良いという方針なので、思い切りシンプルだ。ただ破壊してしまうと元に戻すのが困難だから、初期状態をどこかに保存しておく必要がある。
diff --git a/deoptimize.h b/deoptimize.h new file mode 100644 index 0000000000..02fe6c289f --- /dev/null +++ b/deoptimize.h @@ -0,0 +1,5 @@ +struct iseq_to_deoptimize { + const rb_serial_t created_at; ///< creation timestamp + const uintptr_t *restrict ptr; ///< deoptimized raw body + const unsigned int nelems; ///< ptr's size, in words +}; diff --git a/vm_core.h b/vm_core.h index 94b5bce87d..75396cbe06 100644 --- a/vm_core.h +++ b/vm_core.h @@ -284,6 +286,7 @@ struct rb_iseq_constant_body { unsigned int iseq_size; const VALUE *iseq_encoded; /* encoded iseq (insn addr and operands) */ + const struct iseq_to_deoptimize *deoptimize; /** * parameter information
初期状態は固定なので、最初に一回作ればいい。変更されることはないから、constがいっぱい書いてある。
一方、最適化しない場合にも、のべつまくなしに作成するのは空間効率が無駄なので、必要になるまで作成を遅延しておく。
diff --git a/deoptimize.c b/deoptimize.c new file mode 100644 index 0000000000..7ea39522fd --- /dev/null +++ b/deoptimize.c @@ -0,0 +1,53 @@ +typedef struct iseq_to_deoptimize target_t; +typedef struct rb_iseq_constant_body body_t; + +void +iseq_prepare_to_deoptimize( + const rb_iseq_t *restrict i, + rb_serial_t t) +{ + body_t *restrict b = i->body; + + if (b->deoptimize) { + return; + } + else { + const VALUE *restrict x = b->iseq_encoded; + unsigned int n = b->iseq_size; + size_t s = sizeof(VALUE) * n; + void *restrict y = ruby_xmalloc(s); + target_t *restrict d = ruby_xmalloc(sizeof(*d)); + target_t buf = (typeof(buf)) { + .created_at = t, + .ptr = y, + .nelems = n, + }; + b->deoptimize = d; + memcpy(d, &buf, sizeof(buf)); + memcpy(y, x, s); + } +} + +void +iseq_to_deoptimize_free(const target_t *i) +{ + if (UNLIKELY(! i)) { + return; + } + else { + ruby_xfree((void *)i->ptr); + ruby_xfree((void *)i); + } +} + +void +iseq_deoptimize(const rb_iseq_t *restrict i) +{ + rb_serial_t const t = rb_vm_global_timestamp(); + body_t *b = i->body; + const target_t *d = b->deoptimize; + const uintptr_t *orig = d->ptr; + + memcpy((void *)b->iseq_encoded, orig, b->iseq_size * sizeof(VALUE)); + memcpy((void *)&d->created_at, &t, sizeof(t)); +} diff --git a/deoptimize.h b/deoptimize.h new file mode 100644 index 0000000000..02fe6c289f --- /dev/null +++ b/deoptimize.h @@ -0,0 +1,12 @@ +void +iseq_deoptimize_if_needed( + const rb_iseq_t *restrict i, + rb_serial_t t) +{ + if (! i->body->deoptimize) { + return; /* not yet */ + } + if (t != i->body->deoptimize->created_at) { + iseq_deoptimize(i); + } +}
さて、すでに前後してコードには出現しているが、このように保存した初期状態を復元するには、上記のようにmemcpy()でべったりと書き戻すだけである。なので、処理は簡単だが、これをいつ行えばよいかを判定する必要がある。
そのため新たに導入したのが、rb_vm_global_timestamp()だ。この値は整数で、VMの「状態」が変わるたびに変更していくことにする。値が従前と同じであれば「状態」が変わっていないので、安心して最適化できる。値が変わっていれば、何かの「状態」が変わったということなので、前提条件の変化があり得るため、最適化済みのプログラムの最適化をキャンセルする必要がある。
以上が「最適化が間違っていたら、戻す」の核心なわけだけれども、最適化が間違っているかどうかの判定は、一回の整数比較でしか行っていない。このようにすると、本当は戻す必要がないにもかかわらず、最適化無効と判定してしまうケースが増える。これもまたトレードオフで、最適化が有効かどうかのチェックがすごく重いようでは、オーバーヘッドばかりかかって本末転倒である。どこまで精密に判定すべきかは、かなり難しい問題であるわりに、ロジックの問題なので、パラメーターでチューニングという話にもならず、デザインでがんばるしかないと感じる。
そういうわけで「状態」が変化する場所で、フックしてこのタイムスタンプを更新するわけだが、ここでいう「状態」とは何か？ということが問題になる。これは「最適化をキャンセルする必要がある状況とは何か？」から逆算して考えることができ、
- 新しいクラスやモジュールが作成された
- 新しいメソッドが定義された
- 既存のクラスが既存のモジュールをincludeした
といった変更がそれに該当する。
diff --git a/vm_insnhelper.h b/vm_insnhelper.h index 69eaaacf2e..41f63dd9e4 100644 --- a/vm_insnhelper.h +++ b/vm_insnhelper.h @@ -185,6 +186,14 @@ enum vm_regan_acttype { #define GET_GLOBAL_CONSTANT_STATE() (ruby_vm_global_constant_state) #define INC_GLOBAL_CONSTANT_STATE() (++ruby_vm_global_constant_state) +#if RUBY_ATOMIC_GENERIC_MACRO +# define INC_GLOBAL_TIMESTAMP() ATOMIC_INC(ruby_vm_global_timestamp) +#elif defined(HAVE_LONG_LONG) && (SIZEOF_SIZE_T == SIZEOF_LONG_LONG) +# define INC_GLOBAL_TIMESTAMP() ATOMIC_SIZE_INC(ruby_vm_global_timestamp) +#else +# define INC_GLOBAL_TIMESTAMP() (++ruby_vm_global_timestamp) +#endif + static VALUE make_no_method_exception(VALUE exc, VALUE format, VALUE obj, int argc, const VALUE *argv, int priv); diff --git a/vm.c b/vm.c index c3e7bb3258..a45e61266a 100644 --- a/vm.c +++ b/vm.c @@ -196,7 +199,8 @@ static VALUE vm_invoke_proc(rb_thread_t *th, rb_proc_t *proc, VALUE self, int argc, const VALUE *argv, const rb_block_t *blockptr); -static rb_serial_t ruby_vm_global_method_state = 1; +static rb_serial_t ruby_vm_global_timestamp = 1; +rb_serial_t ruby_vm_global_method_state = 1; static rb_serial_t ruby_vm_global_constant_state = 1; static rb_serial_t ruby_vm_class_serial = 1; @@ -213,6 +217,7 @@ static rb_serial_t ruby_vm_class_serial = 1; rb_serial_t rb_next_class_serial(void) { + INC_GLOBAL_TIMESTAMP(); return NEXT_CLASS_SERIAL(); } @@ -273,6 +278,12 @@ ruby_th_dtrace_setup(rb_thread_t *th, VALUE klass, ID id, return FALSE; } +rb_serial_t +rb_vm_global_timestamp() +{ + return ruby_vm_global_timestamp; +} + /* * call-seq: * RubyVM.stat -> Hash diff --git a/vm_method.c b/vm_method.c index 69f98c4421..c771a5faff 100644 --- a/vm_method.c +++ b/vm_method.c @@ -89,6 +89,7 @@ rb_clear_cache(void) void rb_clear_constant_cache(void) { + INC_GLOBAL_TIMESTAMP(); INC_GLOBAL_CONSTANT_STATE(); } @@ -100,6 +101,8 @@ rb_clear_method_cache_by_class(VALUE klass) RUBY_DTRACE_HOOK(METHOD_CACHE_CLEAR, (global ? "global" : rb_class2name(klass))); + INC_GLOBAL_TIMESTAMP(); + if (global) { INC_GLOBAL_METHOD_STATE(); }
おおむね以上が、提案しているdeoptimizationの実装の骨子だ（枝葉はもうちょっとある、Makefileとか）。ここまで掲載したdiffを読めばお分かりのように、既存部分をほとんど書き換えず、追記だけで実現されている。
もちろん、追記とはすなわちオーバーヘッドなので、ここまでの処理だけを追加しただけでは、実行は高速化されない。むしろ、ちょっと遅くなる。そこで、その分のオーバーヘッドを補って余りあるだけの高速化が達成できるかが、次のポイントになってくる。
インストラクションを消し、跡地をnopで埋める
さて上記の通り、今回の割り切りの中では、できる最適化に制限がある。この制限下で一体どういう高速化ができるかを考えると、おおむね以下のようなパターンであろうと思われる。
- 現在実行中のインストラクションを消したり、
その前後のインストラクションと一緒に短くしたりできる - 消した後はnopで埋める
- 連続したnopを後ろに動かす（前に動かすのはNG）
最後はどういう話かというと、例えば「X nop Y nop」というシーケンスが出現していたときに、今PCがYにあって、Yの処理自体は終わったとすると、「X Y nop nop」に変換するのは可能だということである。しかし「X nop nop Y」に変換してしまうと、もう一回Yに突入するからNGだ。
このようにして、処理を縮めた跡地にnopを埋めつつ、埋め草のnopをどんどん後ろにずらしていくことで、次には「X Y」のパターンが最適化できるようになるかもしれない。
実際、まず簡単にインストラクションを消すことができるのは、定数参照だ。Rubyの定数は案外複雑なロジックで解決されているのだが、毎度それを実施すると大変つらいので、すでにインストラクションの中にキャッシュする機構がある。
zsh % ruby --dump=insns -e 'RubyVM::INstructionSequence' == disasm: #<ISeq:<main>@-e>============================================ 0000 trace 256 ( 8) 0002 trace 1 ( 9) 0004 getinlinecache 13, <is:0> 0007 getconstant :RubyVM 0009 getconstant :InstructionSequence 0011 setinlinecache <is:0> 0013 trace 512 ( 10) 0015 leave ( 9) zsh %
この出力は、左から番地、インストラクション、オペランドと並んでいる。これをこう変換する
--- /dev/shm/1wqj345 2016-08-17 14:23:36.000000000 +0900 +++ /dev/shm/978zae 2016-08-17 14:23:36.000000000 +0900 @@ -20,9 +20,13 @@ local table (size: 2, argc: 0 [opts: 0, |------------------------------------------------------------------------ 0000 trace 256 ( 8) 0002 trace 1 ( 9) -0004 getinlinecache 13, <is:0> -0007 getconstant :RubyVM -0009 getconstant :InstructionSequence -0011 setinlinecache <is:0> +0004 putobject RubyVM::InstructionSequence +0006 nop +0007 nop +0008 nop +0009 nop +0010 nop +0011 nop +0012 nop 0013 trace 512 ( 10) 0015 leave ( 9)
このsetinlinecacheで、すでにgetconstantの結果がキャッシュされているので、それを取り出してputobjectにしておく。元に比べてインストラクションが減っているので、余った部分はnopで埋めていく。
diff --git a/insns.def b/insns.def index c9d7204b42..c978d9be3c 100644 --- a/insns.def +++ b/insns.def @@ -1253,6 +1332,10 @@ getinlinecache { if (ic->ic_serial == GET_GLOBAL_CONSTANT_STATE() && (ic->ic_cref == NULL || ic->ic_cref == rb_vm_get_cref(GET_EP()))) { + const rb_iseq_t *i = GET_ISEQ(); + const VALUE *p = GET_PC(); + + iseq_const_fold(i, p, OPN_OF_CURRENT_INSN + 1, dst, ic->ic_value.value); val = ic->ic_value.value; JUMP(dst); } diff --git a/optimize.h b/optimize.h new file mode 100644 index 0000000000..c5bb764ed4 --- /dev/null +++ b/optimize.h @@ -0,0 +1,30 @@ +/** + * Folds a constant to a direct access. This converts + * + * +--- PC + * v + * +-----+-----+-----+-----+-----+-----+-----+-----+ + * | GIC | m | x | GET | y | SIC | z | ... | + * +-----+-----+-----+-----+-----+-----+-----+-----+ + * \------ n ------/ \--------- m ---------/ + * GIC: getinlinecache + * GET: getconst + * SIC: setinlinecache + * + * into: + * +--- PC + * v + * +-----+-----+-----+-----+-----+-----+-----+-----+ + * | PUT | val | nop | nop | nop | nop | nop | ... | + * +-----+-----+-----+-----+-----+-----+-----+-----+ + * PUT: putobject + * + * @param [out] i target iseq struct to squash. + * @param [in] p PC + * @param [in] n length to wipe before PC + * @param [in] m length to wipe after PC + */ +void iseq_const_fold(const struct rb_iseq_struct *restrict i, const VALUE *pc, int n, long m, VALUE konst) + __attribute__((hot)) + __attribute__((nonnull)) + __attribute__((leaf)); diff --git a/optimize.c b/optimize.c new file mode 100644 index 0000000000..fc0d959386 --- /dev/null +++ b/optimize.c @@ -0,0 +1,70 @@ +/** + * Initializes memory pattern. Never called explicitly. + */ +static void construct_pattern(void) + __attribute__((constructor)) + __attribute__((used)) + __attribute__((noinline)); + +static VALUE wipeout_pattern[8]; /* maybe 5+2==7 should suffice? */ +static VALUE nop; +static VALUE putobject; + +void +construct_pattern(void) +{ +#define LABEL_PTR(insn) addrs[BIN(insn)] + const void **addrs = rb_vm_get_insns_address_table(); + const typeof(wipeout_pattern) p = { + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + (VALUE)LABEL_PTR(nop), + }; + + memcpy((void *)wipeout_pattern, p, sizeof(p)); + nop = (VALUE)LABEL_PTR(nop); + putobject = (VALUE)LABEL_PTR(putobject); +#undef LABEL_PTR +} + +extern rb_serial_t rb_vm_global_timestamp(); + +void +iseq_squash(const rb_iseq_t *iseq, VALUE *pc, int n) +{ + const int m = sizeof(wipeout_pattern) / sizeof(VALUE); /* == 8 */ + + iseq_prepare_to_deoptimize(iseq, rb_vm_global_timestamp()); + while (UNLIKELY(n > m)) { + MEMCPY(pc, wipeout_pattern, VALUE, m); + pc += m; + n -= m; + } + MEMCPY(pc, wipeout_pattern, VALUE, n); + ISEQ_RESET_ORIGINAL_ISEQ(iseq); + FL_SET(iseq, ISEQ_NEEDS_ANALYZE); +} + +void +iseq_const_fold( + const rb_iseq_t *restrict i, + const VALUE *pc, + int n, + long m, + VALUE konst) +{ + VALUE *buf = (VALUE *)&pc[-n]; + int len = n + m; + + iseq_squash(i, buf, len); + buf[0] = putobject; + buf[1] = konst; + if (! SPECIAL_CONST_P(konst)) { + rb_ary_push(ISEQ_OPTIMIZED_VALUES(i), konst); + } +}
今まで以上に長いので実装は省略するが、同様の仕組みで1 + 2のようなコードも最適化可能である。それと組み合わせればFile::CREAT | File::EXCLとかいった式が畳み込めるようになる。
--- /dev/shm/xj79gt 2016-08-17 17:09:31.000000000 +0900 +++ /dev/shm/1gaaeo 2016-08-17 17:09:31.000000000 +0900 @@ -20,8 +20,10 @@ local table (size: 2, argc: 0 [opts: 0, |------------------------------------------------------------------------ 0000 trace 256 ( 7) 0002 trace 1 ( 8) -0004 putobject_OP_INT2FIX_O_1_C_ -0005 putobject 2 -0007 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> +0004 putobject 3 +0006 nop +0007 nop +0008 nop +0009 nop 0010 trace 512 ( 9) 0012 leave ( 8)
「メソッド呼び出しが省略可能であること」を判定するために
次に、別の最適化として、メソッド呼び出しの省略を考える。「省略」なので、これまでと同様にnopで埋めていけばよく、省略すること自体は可能とすぐ分かる。問題はどちらかというと、メソッド呼び出しであれば何でもかんでも省略していいというわけではないという点にある。例えば、DBの読み書きのようなメソッド呼び出しはあからさまに省略してはいけない。
そこで、このメソッドは副作用がない（ので省略可能である）、というマークをつけていくことを考える。しかしながら、これは静的に定まるものではない。Rubyの特徴としてメソッド呼び出しは動的、つまり実際に呼ぶまで、何が呼ばれるか分からないという話がある。動作の途中で、あるメソッド名を解決して得られるメソッド実体がじゃんじゃん変わるというのはあり得る話ではある。
普通、あるメソッドは中で他のメソッドを呼んでいる、という場合がほとんどで、中で呼んでいるメソッドに副作用があれば呼んでいる方のメソッドも省略可能にならない。要は、毎度呼ぶメソッドが変わるような場合だと、省略可能性が判定不能ということになる。
ただ、今回はそういう再定義が行われた場合には最適化を全部キャンセルするという前提だから、一回これと決まったら次回も同じメソッドが呼ばれるという仮定をおいて良い。したがって
- あるメソッドを実際に実行していきながら
- 実行中に中で呼ぶ別のメソッドが副作用を持つかを検証していって
- すべてのメソッド呼び出しが解決できたら
そのメソッド自身が副作用を持つかも分かる
という流れで、メソッドの副作用の有無を判定できそうである。
また、メソッドに副作用がなかったといっても、メソッド呼び出しが省略可能かは、その呼ばれ方にも依存する。例えば、f(g(x))となっていた場合、gの呼び出しが省略できるかは、fの呼び出しが省略できるかにも関係している。したがって、メソッド呼び出しが省略可能かどうかを判定するのは、呼び出し側でそれぞれにやる必要がある。
以上の流れを実装すると、diffが少々大きくて600行強ほどになるのだがそれはさておき、メソッド呼び出しが省略可能になる。
--- /dev/shm/165rrgd 2016-08-17 10:44:10.000000000 +0900 +++ /dev/shm/jd0rcj 2016-08-17 10:44:10.000000000 +0900 @@ -23,8 +23,10 @@ local table (size: 2, argc: 0 [opts: 0, 0004 putself 0005 putself 0006 opt_send_without_block <callinfo!mid:g, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache> -0009 opt_send_without_block <callinfo!mid:f, argc:1, FCALL|ARGS_SIMPLE>, <callcache> -0012 adjuststack 1 +0009 adjuststack 2 +0011 nop +0012 nop +0013 nop 0014 trace 1 ( 16) 0016 putnil 0017 trace 512 ( 17)
上記の例ではf(g())を最適化してg()だけにしている。
省略可能な呼び出され方を増やす
上記の通りで、メソッド呼び出しが省略可能かどうかは、その呼び出され方に依存するという面がある。したがって、省略できる呼び出され方を増やすのには意味がある。
そこで次に、変数へ代入しているものを省略できないか？を考える。例えば、y = f(x)でfそのものは副作用がないという場合を考えると、yが使われているかどうかで、fの呼び出しが省略可能かが決まる。
そこで、使われていない変数への代入が省略できれば良いのではないかという仮説が出てくる。これも省略なので、nopで埋めること自体はさほど苦もないが、メソッド呼び出しと同様に、どこまで消していいかの判定が難しい。
変数が使われていないかどうかの判定、というのはコンパイラ最適化の教科書に載っているようなアルゴリズム（liveness analysis）であり、そこそこ大変である。今回、我々は上記のように、プログラムを実行している途中でおもむろに「これは省略可能か？」と判定したいわけだけれども、そこで都度CFG（制御フローグラフ）を作って、UD Chain（使用定義チェイン）を構築して、とやっていくと結構なオーバーヘッドが生じる（今この記事を書いている最中にふと、これも何か変わったらキャンセルする前提ならば最初に一回だけやればいいという気もしてきたが、ともかくこの当時には都度やるのは大変だと判断した）。
そこで今回は、より簡単な判定で済むように、代入しただけで一回も使われてない変数に限定する。これであれば、代入の瞬間にスコープの最後までスキャンして、スコープ長に対してO(n)で判定可能だから、まずまず軽い。Rubyの場合、ブロックという機構があるので「スコープの最後までスキャン」というのは、ブロックつきメソッド呼び出しの中までチェックにいく必要があり、再帰的な要素はやや残るが、まあ200行くらいの変更で可能である。
--- /dev/shm/ea2lud 2016-08-19 10:40:28.000000000 +0900 +++ /dev/shm/1v4irx0 2016-08-19 10:40:28.000000000 +0900 @@ -17,8 +17,10 @@ local table (size: 3, argc: 1 [opts: 0, [ 3] i<Arg> [ 2] x 0000 trace 256 ( 4) 0002 trace 1 ( 5) -0004 putobject :foo -0006 setlocal_OP__WC__0 2 +0004 nop +0005 nop +0006 nop +0007 nop 0008 trace 1 ( 6) 0010 putnil 0011 trace 512 ( 7)
大き過ぎる問題ではなく、実現できる規模の問題に取り組む
というわけで、高速化のための仕組みと、その上で実装した最適化を解説してきた。全体像は次の場所にある。
Deoptimization Engine by shyouhei · Pull Request #1419 · ruby/ruby
変更を確認すると、ほとんど追記のみで行われていることに気付くだろう。
既存のプロダクトを改良するときに、得てして既存の問題部分を改修しようという意識になりがちである。しかしながら、個人的な経験から言うと、それよりも重要なのは、きちんと最後まで実装を終えられる規模の作業にとどめる、ということである。
既存のプロダクトの改良という文脈では、容易に実現可能なアイディアはすでにあらかた実現されていることもあるだろう。とはいえそれは、すべてのアイディアが実現済みであることを意味するわけではなく、難しいものは残っているのである。そこで、残っている難しいものをいかにして解決していくかということになるわけだが、難しいものは難しいので、いかにして簡単な方に倒すかがポイントになってくるわけだ。
特に高速化というものは、バグ修正などとは性質が違い、動けばいいというものではない。最低限ちゃんと動くという前提があって、その上でどのくらい速くなったかという議論があるので、ともかくちゃんと動くところまで持っていく手間は、少なければ少ないほど良い。
気宇壮大な改修計画を立てたものの、作業量が膨大で計画倒れになる、というのはありがちな話だが、今回提案しているのはその逆だ。この内容は「プログラミング言語を高速化しました」と聞いて専門家が思い浮かべる高速化と比べると、ずっとずっと限定的である。アプリケーションによってはほとんど無意味、と評する向きもあるだろう（そういう専門家の意見は傾聴に値すると思う）。この提案は、少なくともそういう評価ができるところまで作ってある、ということに意義があると思っている。
今回たまたま高速化できた例を解説しているわけだが、やってみたけど全然ダメだったというアイディアも多々ある。いかに早期に失敗して次のアイディアに向かうかが重要だと感じる。以前どこかで「一発当たって次がない例は多いが、一発目から当たる例はない」というような文章を読み、本当にそうだと思ったことがある。
もし、これを読んでいるみなさんが言語開発や既存プロジェクトの改修に立ち向かうときは、ぜひ大き過ぎる問題に取り組んで心折れてしまわないようにしてほしい。
卜部昌平（
株式会社マネーフォワードのフルタイムRubyコミッター。プログラミング言語Rubyコミッター、日本Rubyの会監事。大学院在学中の2008年ごろからRuby開発に携わる。大学院修了後は趣味としてRuby開発を続けるかたわらプログラマーとして数社に勤務。その後2015年よりマネーフォワードにてフルタイムでRuby開発に携わり現職。監訳にオライリー『プログラミング言語Ruby』。
企画：中薗昴
