エンジニアHub > 記事一覧 > いかにしてRubyを高速化するか？ コミッター・卜部昌平が挑んだ「Deoptimization Ruby」の軌跡

いかにしてRubyを高速化するか？ コミッター・卜部昌平が挑んだ「Deoptimization Ruby」の軌跡

Rubyの高速化に取り組む卜部昌平さんが、その着想やデザイン、実装について解説します。

いかにしてRubyを高速化するか？ コミッター・卜部昌平が挑んだ「Deoptimization Ruby」の軌跡

Ruby1.8.5、1.8.6、1.8.7のリリースマネージャを務め、現在は株式会社マネーフォワードでフルタイムのRubyコミッター職として働く卜部昌平（うらべ・しょうへい／@shyouhei）さんは、deoptimizationと呼ばれるアプローチを用いてRubyの高速化に取り組んでいます。

本稿ではその足跡から、いかなる思想のもとでデザインや実装を行っているかを、卜部さん本人が解説します。

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で埋める

エンジニアHubに会員登録すると
続きをお読みいただけます（無料）。
GitHubで登録 メールアドレスで登録
登録ボタンを押すと、利用規約とプライバシーポリシーに同意したことになります。
ログインはこちら
登録のメリット
  • すべての過去記事を読める
  • 過去のウェビナー動画を
    視聴できる
  • 企業やエージェントから
    スカウトが届く