CRubyは最適化のためにメソッド再定義をどのようにチェックするか

Ruby 2.4.1について書いている。書きかけだけど読みたいところが読めてしまって多分これ以上すぐには書かないので公開しておく。

CRubyのopt_*命令について

Rubyで1+1を実行すると、何が起きるか。
Rubyでは全ての演算子がメソッドになっているので、一見Integer#+メソッドの呼び出し(ここでは、YARVでsend系の命令が実行されること、という定義)が行なわれるように思うかもしれないが、ほとんどの場合ではそうではない。

$ ruby --dump=insns -e "1+1"
== disasm: #<ISeq:<main>@-e>============================================
0000 trace            1                                               (   1)
0002 putobject_OP_INT2FIX_O_1_C_
0003 putobject_OP_INT2FIX_O_1_C_
0004 opt_plus         <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache>
0007 leave

普通メソッド呼び出しの時はopt_send_without_blockが使われるが、1+1ではopt_plus命令が実行される。
Rubyではこのようによく使われる演算子にはopt_プレフィクスのついた特別な命令が定義されており、高速に実行される。

どれくらい効果があるのか

require 'benchmark/ips'

Integer.class_eval do
  alias :plus :+
end

klass = Class.new
klass.instance_eval("def self.opt_plus; #{(1..10000).to_a.join('+')}; end")
klass.instance_eval("def self.opt_send_without_block; (#{(1..10000).to_a.join(').plus(')}); end")

Benchmark.ips do |x|
  x.report('opt_plus') { klass.opt_plus }
  x.report('opt_send') { klass.opt_send_without_block }
  x.compare!
end

Calculating -------------------------------------
            opt_plus     29.606k (± 0.6%) i/s -    149.073k in   5.035478s
            opt_send      8.709k (± 0.6%) i/s -     44.044k in   5.057426s

Comparison:
            opt_plus:    29605.7 i/s
            opt_send:     8709.1 i/s - 3.40x  slower

まあ多分完璧なベンチマークではない(plus側にaliasによるオーバーヘッドはないのか？とか、別の場所も含めて+の方が呼び出し回数が多いからメソッドキャッシュとかで不利に働くのではないか？とか)が、3.4倍くらい速くなっているらしい。

実際のアプリケーションではそもそも他の処理の方がボトルネックになってこの差がマイクロベンチマーク以外で大きなインパクトを持つことはあまりない気がする(例えば1+1だけでベンチマークを取ると結果は1.17倍程度になり、ベンチマーク対象の処理の実行のオーバーヘッドが支配的になってしまう)が、よく使うメソッドであることは間違いないので3.4倍速いなら存在意義は十分にありそうに見える。

この最適化で問題は起きるか

Ruby 2.4.1での定義はこうなっている。
https://github.com/ruby/ruby/blob/v2_4_1/insns.def#L1363-L1414

/**
  @c optimize
  @e optimized X+Y.
  @j 最適化された X+Y。
 */
DEFINE_INSN
opt_plus
(CALL_INFO ci, CALL_CACHE cc)
(VALUE recv, VALUE obj)
(VALUE val)
{
    if (FIXNUM_2_P(recv, obj) &&
        BASIC_OP_UNREDEFINED_P(BOP_PLUS,INTEGER_REDEFINED_OP_FLAG)) {
        /* fixnum + fixnum */
#ifndef LONG_LONG_VALUE
        VALUE msb = (VALUE)1 << ((sizeof(VALUE) * CHAR_BIT) - 1);
        val = recv - 1 + obj;
        if ((~(recv ^ obj) & (recv ^ val)) & msb) {
            val = rb_int2big((SIGNED_VALUE)((val>>1) | (recv & msb)));
        }
#else
        val = LONG2NUM(FIX2LONG(recv) + FIX2LONG(obj));
#endif
    }
    else if (FLONUM_2_P(recv, obj) &&
             BASIC_OP_UNREDEFINED_P(BOP_PLUS, FLOAT_REDEFINED_OP_FLAG)) {
        val = DBL2NUM(RFLOAT_VALUE(recv) + RFLOAT_VALUE(obj));
    }
    else if (!SPECIAL_CONST_P(recv) && !SPECIAL_CONST_P(obj)) {
        if (RBASIC_CLASS(recv) == rb_cFloat && RBASIC_CLASS(obj) == rb_cFloat &&
            BASIC_OP_UNREDEFINED_P(BOP_PLUS, FLOAT_REDEFINED_OP_FLAG)) {
            val = DBL2NUM(RFLOAT_VALUE(recv) + RFLOAT_VALUE(obj));
        }
        else if (RBASIC_CLASS(recv) == rb_cString && RBASIC_CLASS(obj) == rb_cString &&
                 BASIC_OP_UNREDEFINED_P(BOP_PLUS, STRING_REDEFINED_OP_FLAG)) {
            val = rb_str_plus(recv, obj);
        }
        else if (RBASIC_CLASS(recv) == rb_cArray &&
                 BASIC_OP_UNREDEFINED_P(BOP_PLUS, ARRAY_REDEFINED_OP_FLAG)) {
            val = rb_ary_plus(recv, obj);
        }
        else {
            goto INSN_LABEL(normal_dispatch);
        }
    }
    else {
        INSN_LABEL(normal_dispatch):
        PUSH(recv);
        PUSH(obj);
        CALL_SIMPLE_METHOD(recv);
    }
}

ザッと分岐を読むと以下のような処理になっているように見える(中身はちゃんと確認してないので嘘かもしれない)。

• 両辺の値がFixnum(最下位ビットが1、整数即値)かつInteger#+が再定義されてなければ、LONG2NUM(FIX2LONG(recv) + FIX2LONG(obj))で計算する
• 両辺の値がFlonum(下位から2ビットが10、浮動小数点即値)かつFloat#+が再定義されてなければ、DBL2NUM(RFLOAT_VALUE(recv) + RFLOAT_VALUE(obj))で計算する
• 両辺の値が即値(下位から3ビットのうち1つ以上立っている、ポインターでない値: Fixnum, Flonum, Symbol), false, nilのいずれでもない場合
  • 両辺の値がFloatで、Float#+が再定義されていなければ、DBL2NUM(RFLOAT_VALUE(recv) + RFLOAT_VALUE(obj))で計算する
  • 両辺の値がStringで、String#+が再定義されていなければ、rb_str_plusの呼び出しで値を返す
  • 両辺の値がArrayで、Array#+が再定義されていなければ、rb_ary_plusの呼び出しで値を返す
  • それ以外の場合、普通にメソッド呼び出しを行う
• それ以外の場合、普通にメソッド呼び出しを行う

要するにInteger#+, Float#+, String#+, Array#+は呼び出す度に再定義されているかを確認されており、再定義されていない場合に限りメソッド呼び出しがバイパスされるのである。これで問題になることはまずなさそう。

BASIC_OP_UNREDEFINED_P はどのように実現されているか

これまでの内容は全て前置きであり個人的にはどうでもよく、Integer#+などが「再定義されているかを確認」するために使われているBASIC_OP_UNREDEFINED_Pがどうやって実現されているかに興味がある。それを知っていれば、何をやると再定義と見なされるのか正確に判断して避けることができ、またこの再定義をチェックするための機構によりオーバーヘッドが発生しパフォーマンスに悪影響が出うるプログラムがあるとしたら、そういうプログラムを自分が生み出すのを防ぐことができる。

とりあえず、Integer#+の再定義チェックを行うBASIC_OP_UNREDEFINED_P(BOP_PLUS,INTEGER_REDEFINED_OP_FLAG)がどういう挙動をするのか追っていく。

BASIC_OP_UNREDEFINED_Pの定義

#define BASIC_OP_UNREDEFINED_P(op, klass) (LIKELY((GET_VM()->redefined_flag[(op)]&(klass)) == 0))

LIKELY(x)は(__builtin_expect(!!(x), 1))という分岐予測系の奴だけど、挙動の確認には大分どうでもいいので外すと、

#define BASIC_OP_UNREDEFINED_P(op, klass) ((GET_VM()->redefined_flag[(op)]&(klass)) == 0)

次に、GET_VMは、いくつか追いかけながら適当に定義を抜粋してくると、

#define GET_VM() ruby_current_vm

extern rb_vm_t *ruby_current_vm;

typedef struct rb_vm_struct {
    VALUE self;

    rb_global_vm_lock_t gvl;
    rb_nativethread_lock_t    thread_destruct_lock;

    struct rb_thread_struct *main_thread;
    struct rb_thread_struct *running_thread;

    struct list_head living_threads;
    size_t living_thread_num;
    VALUE thgroup_default;

    unsigned int running: 1;
    unsigned int thread_abort_on_exception: 1;
    unsigned int thread_report_on_exception: 1;
    int trace_running;
    volatile int sleeper;

    /* object management */
    VALUE mark_object_ary;
    const VALUE special_exceptions[ruby_special_error_count];

    /* load */
    VALUE top_self;
    VALUE load_path;
    VALUE load_path_snapshot;
    VALUE load_path_check_cache;
    VALUE expanded_load_path;
    VALUE loaded_features;
    VALUE loaded_features_snapshot;
    struct st_table *loaded_features_index;
    struct st_table *loading_table;

    /* signal */
    struct {
        VALUE cmd;
        int safe;
    } trap_list[RUBY_NSIG];

    /* hook */
    rb_hook_list_t event_hooks;

    /* relation table of ensure - rollback for callcc */
    struct st_table *ensure_rollback_table;

    /* postponed_job */
    struct rb_postponed_job_struct *postponed_job_buffer;
    int postponed_job_index;

    int src_encoding_index;

    VALUE verbose, debug, orig_progname, progname;
    VALUE coverages;

    VALUE defined_module_hash;

    struct rb_objspace *objspace;

    rb_at_exit_list *at_exit;

    VALUE *defined_strings;
    st_table *frozen_strings;

    /* params */
    struct { /* size in byte */
        size_t thread_vm_stack_size;
        size_t thread_machine_stack_size;
        size_t fiber_vm_stack_size;
        size_t fiber_machine_stack_size;
    } default_params;

    short redefined_flag[BOP_LAST_];
} rb_vm_t;

まあ、名前の通りRubyのVMの状態を保持する構造体に見える。1プロセスに1つしか持てなさそう。

で、BASIC_OP_UNREDEFINED_P(BOP_PLUS,INTEGER_REDEFINED_OP_FLAG)を展開してみると、

(ruby_current_vm->redefined_flag[BOP_PLUS] & INTEGER_REDEFINED_OP_FLAG) == 0

という感じになる。

BOP_PLUSとは

enum ruby_basic_operators {
    BOP_PLUS,
    BOP_MINUS,
    BOP_MULT,
    BOP_DIV,
    BOP_MOD,
    BOP_EQ,
    BOP_EQQ,
    BOP_LT,
    BOP_LE,
    BOP_LTLT,
    BOP_AREF,
    BOP_ASET,
    BOP_LENGTH,
    BOP_SIZE,
    BOP_EMPTY_P,
    BOP_SUCC,
    BOP_GT,
    BOP_GE,
    BOP_NOT,
    BOP_NEQ,
    BOP_MATCH,
    BOP_FREEZE,
    BOP_MAX,
    BOP_MIN,

    BOP_LAST_
};

というenum。Ruby 2.4.1では24個ある。redifined_flagはshort redefined_flag[BOP_LAST_];という定義であり、short型(16ビット)の値を24個持っていることになる。

INTEGER_REDEFINED_OP_FLAGとは

こういう定義がある。

#define INTEGER_REDEFINED_OP_FLAG (1 << 0)
#define FLOAT_REDEFINED_OP_FLAG  (1 << 1)
#define STRING_REDEFINED_OP_FLAG (1 << 2)
#define ARRAY_REDEFINED_OP_FLAG  (1 << 3)
#define HASH_REDEFINED_OP_FLAG   (1 << 4)
/* #define BIGNUM_REDEFINED_OP_FLAG (1 << 5) */
#define SYMBOL_REDEFINED_OP_FLAG (1 << 6)
#define TIME_REDEFINED_OP_FLAG   (1 << 7)
#define REGEXP_REDEFINED_OP_FLAG (1 << 8)
#define NIL_REDEFINED_OP_FLAG    (1 << 9)
#define TRUE_REDEFINED_OP_FLAG   (1 << 10)
#define FALSE_REDEFINED_OP_FLAG  (1 << 11)

16ビットのうち、各ビットがここに書いてある型のためのフラグになっている。コメントアウトされているBignumさんを除くと16個中10個既に使っているようだ。

このフラグとの互換性を意図しているであろうshort型の値が24個あるわけで、(定義された演算子の数) 24 x (再定義を検出するクラスの数) 10 個 = 240個 のメソッド再定義を管理していることになる。

(ruby_current_vm->redefined_flag[BOP_PLUS] & INTEGER_REDEFINED_OP_FLAG) == 0 から察するに、redefined_flagの0000000000000001の場所のビットが立っていたら再定義されていると判定されそうに見える。

redefined_flagはどこで更新されるか

まあruby_current_vm->redefined_flagで再定義が管理されていることはもうわかっているので、それがいつ更新されるか見ていく。

…と思ったけど、実はC拡張とかからメソッドの再定義を検出できるか？というところを知りたかっただけなのでもう目的を達してしまった。ruby_current_vmはRUBY_SYMBOL_EXPORT_BEGINとRUBY_SYMBOL_EXPORT_ENDに囲われておらず、シンボルが外部に公開されていないのでC拡張から参照することはできないため、無理である。

必要になった時に以下のあたりを読むかもしれない

vm_init_redefined_flag

add_opt_methodまわりを読むとよさそう

rb_vm_check_redefinition_opt_method

結構呼んでるところがあるので真面目に追いかけると割とダルそう