読者です 読者をやめる 読者になる 読者になる

割り切れてるかの確認を高速化しようとして、コンパイラに負けた話

Ruby

今日見ていきたいのはtime.cquo(VALUE x, VALUE y)です。akrさんのRuby における 2038年問題の解決で述べられているとおり、RubyのTimeは内部表現にRationalを使えるようになっているので、その辺を司る部品ですね。

static VALUE
quo(VALUE x, VALUE y)
{
    VALUE ret;
    if (FIXNUM_P(x) && FIXNUM_P(y)) {
        long a, b, c;
        a = FIX2LONG(x);
        b = FIX2LONG(y);
        if (b == 0) rb_num_zerodiv();
        c = a / b;
        if (c * b == a) {
            return LONG2NUM(c);
        }
    }
    ret = rb_funcall(x, id_quo, 1, y);
    if (RB_TYPE_P(ret, T_RATIONAL) &&
        RRATIONAL(ret)->den == INT2FIX(1)) {
        ret = RRATIONAL(ret)->num;
    }
    return ret;
}

x64アセンブラも見てみましょう。今日はOS Xで開発しているのでotool -tvV miniruby|lessで見ています。また、quo()は全てインライン化されていたので、ここではtime_subsecの逆アセンブル結果を見ていきます。

static VALUE
time_subsec(VALUE time)
{
    struct time_object *tobj;

    GetTimeval(time, tobj);
    return quo(w2v(wmod(tobj->timew, WINT2FIXWV(TIME_SCALE))), INT2FIX(TIME_SCALE));
}
_time_subsec: # original
0000000100147f10        pushq   %rbp
0000000100147f11        movq    %rsp, %rbp
0000000100147f14        pushq   %r14
0000000100147f16        pushq   %rbx
0000000100147f17        subq    $0x10, %rsp
0000000100147f1b        movq    %rdi, %rbx
0000000100147f1e        leaq    _time_data_type(%rip), %rsi
0000000100147f25        callq   _rb_check_typeddata
0000000100147f2a        movb    0x30(%rax), %cl
0000000100147f2d        andb    $0x7, %cl
0000000100147f30        movzbl  %cl, %ecx
0000000100147f33        cmpl    $0x3, %ecx
0000000100147f36        je      0x100147ff7
0000000100147f3c        movq    (%rax), %rdi
0000000100147f3f        leaq    -0x18(%rbp), %rdx
0000000100147f43        leaq    -0x20(%rbp), %rcx
0000000100147f47        movl    $0x77359401, %esi       ## imm = 0x77359401
0000000100147f4c        callq   _wdivmod
0000000100147f51        movq    -0x20(%rbp), %rdi
0000000100147f55        testb   $0x1, %dil
0000000100147f59        je      0x100147fa1
0000000100147f5b        movq    %rdi, %rcx
0000000100147f5e        sarq    %rcx0000000100147f61        movabsq $0x112e0be826d694b3, %rdx ## imm = 0x112E0BE826D694B3
0000000100147f6b        movq    %rcx, %rax
0000000100147f6e        imulq   %rdx
0000000100147f71        movq    %rdx, %rax
0000000100147f74        shrq    $0x3f, %rax
0000000100147f78        sarq    $0x1a, %rdx
0000000100147f7c        addq    %rax, %rdx
0000000100147f7f        imulq   $0x3b9aca00, %rdx, %rax ## imm = 0x3B9ACA00
0000000100147f86        cmpq    %rcx, %rax
0000000100147f89        jne     0x100147fa1
0000000100147f8b        movabsq $0x4000000000000000, %rax ## imm = 0x4000000000000000
0000000100147f95        addq    %rdx, %rax
0000000100147f98        js      0x100147fe7
0000000100147f9a        leaq    0x1(%rdx,%rdx), %rax
0000000100147f9f        jmp     0x100147fde
0000000100147fa1        movq    _id_quo(%rip), %rsi
0000000100147fa8        movl    $0x1, %edx
0000000100147fad        movl    $0x77359401, %ecx       ## imm = 0x77359401
0000000100147fb2        xorl    %eax, %eax
0000000100147fb4        callq   _rb_funcall
0000000100147fb9        testb   $0x7, %al
0000000100147fbb        jne     0x100147fde
0000000100147fbd        movq    %rax, %rcx
0000000100147fc0        andq    $-0x9, %rcx
0000000100147fc4        je      0x100147fde
0000000100147fc6        movq    (%rax), %rcx
0000000100147fc9        andq    $0x1f, %rcx
0000000100147fcd        cmpq    $0xf, %rcx
0000000100147fd1        jne     0x100147fde
0000000100147fd3        cmpq    $0x3, 0x18(%rax)
0000000100147fd8        jne     0x100147fde
0000000100147fda        movq    0x10(%rax), %rax
0000000100147fde        addq    $0x10, %rsp
0000000100147fe2        popq    %rbx
0000000100147fe3        popq    %r14
0000000100147fe5        popq    %rbp
0000000100147fe6        retq
0000000100147fe7        movq    %rdx, %rdi
0000000100147fea        addq    $0x10, %rsp
0000000100147fee        popq    %rbx
0000000100147fef        popq    %r14
0000000100147ff1        popq    %rbp
0000000100147ff2        jmp     _rb_int2big
0000000100147ff7        leaq    _rb_eTypeError(%rip), %rax
0000000100147ffe        movq    (%rax), %r14
0000000100148001        movq    %rbx, %rdi
0000000100148004        callq   _rb_obj_class
0000000100148009        movq    %rax, %rcx
000000010014800c        leaq    0x8228e(%rip), %rsi     ## literal pool for: "uninitialized %li\013"
0000000100148013        xorl    %eax, %eax
0000000100148015        movq    %r14, %rdi
0000000100148018        movq    %rcx, %rdx
000000010014801b        callq   _rb_raise

とりあえず、その前にこのLONG2NUMですが、このquoって基本割る数yが定数で使われるので、LONG2FIXを使うようにしましょうか。

         a = FIX2LONG(x);
         b = FIX2LONG(y);
         if (b == 0) rb_num_zerodiv();
+        if (b == -1) LONG2NUM(-a);
         c = a / b;
         if (c * b == a) {
-            return LONG2NUM(c);
+            return LONG2FIX(c);
         }
     }
     ret = rb_funcall(x, id_quo, 1, y);

とすると、以下の通り_rb_int2bigが消えます。

_time_subsec: # use Fixnum
0000000100146f30        pushq   %rbp
0000000100146f31        movq    %rsp, %rbp
0000000100146f34        pushq   %r14
0000000100146f36        pushq   %rbx
0000000100146f37        subq    $0x10, %rsp
0000000100146f3b        movq    %rdi, %rbx
0000000100146f3e        leaq    _time_data_type(%rip), %rsi
0000000100146f45        callq   _rb_check_typeddata
0000000100146f4a        movb    0x30(%rax), %cl
0000000100146f4d        andb    $0x7, %cl
0000000100146f50        movzbl  %cl, %ecx
0000000100146f53        cmpl    $0x3, %ecx
0000000100146f56        je      0x100146ff8
0000000100146f5c        movq    (%rax), %rdi
0000000100146f5f        leaq    -0x18(%rbp), %rdx
0000000100146f63        leaq    -0x20(%rbp), %rcx
0000000100146f67        movl    $0x77359401, %esi       ## imm = 0x77359401
0000000100146f6c        callq   _wdivmod
0000000100146f71        movq    -0x20(%rbp), %rdi
0000000100146f75        testb   $0x1, %dil
0000000100146f79        je      0x100146fb2
0000000100146f7b        movq    %rdi, %rcx
0000000100146f7e        sarq    %rcx
0000000100146f81        movabsq $0x112e0be826d694b3, %rdx ## imm = 0x112E0BE826D694B3
0000000100146f8b        movq    %rcx, %rax
0000000100146f8e        imulq   %rdx
0000000100146f91        movq    %rdx, %rax
0000000100146f94        shrq    $0x3f, %rax
0000000100146f98        sarq    $0x1a, %rdx
0000000100146f9c        addq    %rax, %rdx
0000000100146f9f        imulq   $0x3b9aca00, %rdx, %rax ## imm = 0x3B9ACA00
0000000100146fa6        cmpq    %rcx, %rax
0000000100146fa9        jne     0x100146fb2
0000000100146fab        leaq    0x1(%rdx,%rdx), %rax
0000000100146fb0        jmp     0x100146fef
0000000100146fb2        movq    _id_quo(%rip), %rsi
0000000100146fb9        movl    $0x1, %edx
0000000100146fbe        movl    $0x77359401, %ecx       ## imm = 0x77359401
0000000100146fc3        xorl    %eax, %eax
0000000100146fc5        callq   _rb_funcall
0000000100146fca        testb   $0x7, %al
0000000100146fcc        jne     0x100146fef
0000000100146fce        movq    %rax, %rcx
0000000100146fd1        andq    $-0x9, %rcx
0000000100146fd5        je      0x100146fef
0000000100146fd7        movq    (%rax), %rcx
0000000100146fda        andq    $0x1f, %rcx
0000000100146fde        cmpq    $0xf, %rcx
0000000100146fe2        jne     0x100146fef
0000000100146fe4        cmpq    $0x3, 0x18(%rax)
0000000100146fe9        jne     0x100146fef
0000000100146feb        movq    0x10(%rax), %rax
0000000100146fef        addq    $0x10, %rsp
0000000100146ff3        popq    %rbx
0000000100146ff4        popq    %r14
0000000100146ff6        popq    %rbp
0000000100146ff7        retq
0000000100146ff8        leaq    _rb_eTypeError(%rip), %rax
0000000100146fff        movq    (%rax), %r14
0000000100147002        movq    %rbx, %rdi
0000000100147005        callq   _rb_obj_class
000000010014700a        movq    %rax, %rcx
000000010014700d        leaq    0x8228d(%rip), %rsi     ## literal pool for: "uninitialized %li\013"
0000000100147014        xorl    %eax, %eax
0000000100147016        movq    %r14, %rdi
0000000100147019        movq    %rcx, %rdx
000000010014701c        callq   _rb_raise
0000000100147021        nopw    %cs:(%rax,%rax)

さて、今回のコードを見てまず注目したいのはc * b == aです。これは直前のa / bが割り切れたかを確認しているのですね。しかし、前回の記事を読んだ方ならピーンとくるのではないでしょうか。そう、/%コンパイラが一つにまとめてくれますコンパイラにこのコードの意図を教えてあげましょう。

         a = FIX2LONG(x);
         b = FIX2LONG(y);
         if (b == 0) rb_num_zerodiv();
+        if (b == -1) LONG2NUM(-a);
         c = a / b;
-        if (c * b == a) {
-            return LONG2NUM(c);
+        if (a % b == 0) {
+            return LONG2FIX(c);
         }
     }
     ret = rb_funcall(x, id_quo, 1, y);
0000000100147ecc        callq   _wdivmod
0000000100147ed1        movq    -0x20(%rbp), %rdi
0000000100147ed5        testb   $0x1, %dil
0000000100147ed9        je      0x100147f0b
0000000100147edb        movq    %rdi, %rcx
0000000100147ede        sarq    %rcx
0000000100147ee1        movabsq $0x112e0be826d694b3, %rsi ## imm = 0x112E0BE826D694B3
0000000100147eeb        movq    %rcx, %rax
0000000100147eee        imulq   %rsi
0000000100147ef1        movq    %rdx, %rax
0000000100147ef4        shrq    $0x3f, %rax
0000000100147ef8        sarq    $0x1a, %rdx
0000000100147efc        addq    %rax, %rdx
0000000100147eff        imulq   $0x3b9aca00, %rdx, %rax ## imm = 0x3B9ACA00
0000000100147f06        cmpq    %rax, %rcx
0000000100147f09        je      0x100147f4a
0000000100147f0b        movq    _id_quo(%rip), %rsi
0000000100147f12        movl    $0x1, %edx
0000000100147f17        movl    $0x77359401, %ecx       ## imm = 0x77359401
0000000100147f1c        xorl    %eax, %eax
0000000100147f1e        callq   _rb_funcall
0000000100147f23        testb   $0x7, %al
0000000100147f25        jne     0x100147f63
0000000100147f27        movq    %rax, %rcx
0000000100147f2a        andq    $-0x9, %rcx
0000000100147f2e        je      0x100147f63
0000000100147f30        movq    (%rax), %rcx
0000000100147f33        andq    $0x1f, %rcx
0000000100147f37        cmpq    $0xf, %rcx
0000000100147f3b        jne     0x100147f63
0000000100147f3d        cmpq    $0x3, 0x18(%rax)
0000000100147f42        jne     0x100147f63
0000000100147f44        movq    0x10(%rax), %rax
0000000100147f48        jmp     0x100147f63
0000000100147f4a        movq    %rcx, %rax
0000000100147f4d        imulq   %rsi
0000000100147f50        movq    %rdx, %rax
0000000100147f53        shrq    $0x3f, %rax
0000000100147f57        sarq    $0x1a, %rdx
0000000100147f5b        addq    %rax, %rdx
0000000100147f5e        leaq    0x1(%rdx,%rdx), %rax
0000000100147f63        addq    $0x10, %rsp
0000000100147f67        popq    %rbx
0000000100147f68        popq    %r14
0000000100147f6a        popq    %rbp
0000000100147f6b        retq

……わかりづらいと思いますが、命令数が増えています。ていうか、そもそもアセンブラに前回登場したidivがいません、ふしぎ。

これは、定数の除算がコンパイル時点で乗算とシフトに置き換えられているからです。整数の割り算を掛け算に変換のシリーズが詳しいので解説は譲り、ここでは動きだけ確認しましょう。

  • callq _wdivmod # wmodから戻ってくる
  • movq -0x20(%rbp), %rdi # 戻り値を%rdiに入れる
  • testb $0x1, %dil # 戻り値がFixnumか、1と論理積を取って判定。Fixnumの場合、VALUEは最下位ビットが1です。なお、これはquo(x, y)のxで、yは1000000000で定数なので消えています。
  • je 0x100147f0b # ZFが0の時にジャンプ。つまり、Fixnumならジャンプしません
  • movq %rdi, %rcx # %rdiの内容を%rcxにコピー
  • sarq %rcx # rcx >> = 1 # つまり、xの数値です
  • movabsq $0x112e0be826d694b3, %rsiに謎の値を入れる
  • movq %rcx, %rax # %rcxの内容を%raxにコピー
  • imulq %rsi # %rsi * %rax を計算し、下位64bitを%raxに、上位64bitを%rdxに入れます
  • movq %rdx, %rax # %rdxを%raxにコピー
  • shrq $0x3f, %rax # rax >>= 0x3f # 符号維持63bit右シフト
  • sarq $0x1a, %rdx # rdx >>= 0x1a # 20bit右シフト
  • addq %rax, %rdx %rdxに%raxを足す
  • imulq $0x3b9aca00, %rdx, %rax # %rdx * 0x3b9aca00 を %raxにいれる (0x3b9aca00 == 1000000000)
  • cmpq %rax, %rcx一致したか確認

微妙な誤差の調整を除いてまとめると、だいたい(123456789000000000*0x112e0be826d694b3)>>(64+0x1a) == 123456789ってとこですね。

同じ割り算を連続して行うようなアプリケーションならば、このような最適化をその都度行ってJIT的に処理すると言うことも考えられますが、Rubyだとちょっとやりづらいですかねぇ。

さて、今回は既にコンパイラが十分に最適化していたため、目立った成果はありませんでした。次回こそ頑張りましょう。