割り切れてるかの確認を高速化しようとして、コンパイラに負けた話
今日見ていきたいのはtime.cのquo(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か、１と論理積を取って判定。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だとちょっとやりづらいですかねぇ。
さて、今回は既にコンパイラが十分に最適化していたため、目立った成果はありませんでした。次回こそ頑張りましょう。
