ビットシフトでRubyでも2^n倍の掛け算割り算は速くなる

ruby/src/error.c を眺めていて、RangeErrorの以下の例に、おやっと思った。

/*
 *  Document-class: RangeError
 *
 *  Raised when a given numerical value is out of range.
 *
 *     [1, 2, 3].drop(1 << 100)
 *
 *  <em>raises the exception:</em>
 *
 *     RangeError: bignum too big to convert into `long'
 */

RangeErrorはStandardErrorを継承している標準の例外クラスで、範囲外のインデックスを渡して値をフェッチしようとしたときなどにraiseされる。

ruby/src/error.c

  537: VALUE rb_eRangeError;
  538  VALUE rb_eNameError;
  539  VALUE rb_eEncodingError;
  ...
 1744      rb_eIndexError    = rb_define_class("IndexError", rb_eStandardError);
 1745      rb_eKeyError      = rb_define_class("KeyError", rb_eIndexError);
 1746:     rb_eRangeError    = rb_define_class("RangeError", rb_eStandardError);

それはいいんだけど、Array#dropに渡してる (1 << 100) ってなんだ？と、ぎょっとした。って、これはビットシフト演算なのだった。100回左にビットをゴソゴソっと動かすので、2進数で1の後に0が100個続く数になる。10進数だと31桁。つまり、1 << 100 は「明らかにデカイ数」という程度の意味。

Rubyで << は、Arrayに要素をpushするとか、文字列を concat するとか、eval するための文字列を組み立てるときのヒアドキュメントで使うとか、そういうのが多いので面食らってしまった。

そのぐらいRubyでビットシフト演算って、あまり見かけない。そういうことをやる言語ではないような気がする。のだけど、やっぱり2^n倍にする操作をやるのはビットシフトのほうが速い。当たり前か。

require 'benchmark'

p 1 << 1000 == 2**1000

Benchmark.bm do |x|
  x.report { 1_000_000.times { 1 << 1000} }
  x.report { 1_000_000.times { 2**1000} }
end

big_number = 1 << 1000
p (big_number >> 10) == (big_number / 1024)

Benchmark.bm do |x|
  x.report { 1_000_000.times { big_number >> 10 } }
  x.report { 1_000_000.times { big_number / 1024 } }
end

$ ruby -v bitshift.rb
ruby 1.9.3p327 (2012-11-10 revision 37606) [x86_64-darwin11.4.2]
true
       user     system      total        real
   0.560000   0.000000   0.560000 (  0.571141)
   3.180000   0.010000   3.190000 (  3.202365)
true
       user     system      total        real
   0.540000   0.000000   0.540000 (  0.550380)
   0.970000   0.000000   0.970000 (  0.985371)

しかし、Rubyの場合、FIXNUMとBIGNUMがあるし、その辺、ちゃんと面倒みてビットシフト演算もやってくれてるのかなと思って、numeric.cを見たら、

static VALUE
rb_fix_lshift(VALUE x, VALUE y)
{
    long val, width;

    val = NUM2LONG(x);
    if (!FIXNUM_P(y))
	return rb_big_lshift(rb_int2big(val), y);
    width = FIX2LONG(y);
    if (width < 0)
	return fix_rshift(val, (unsigned long)-width);
    return fix_lshift(val, width);
}

と、ちゃんとやってくれてた。FIXNUM_PはLispの命名法則に従ったCRubyのマクロで、与えられたオブジェクトがFIXNUMかどうかを判別する。Rubyで言えば、obj.is_a?(Fixnum) のようなもの。

シフトする数がFIXNUMでない場合には、rb_big_lshift(rb_int2big(val), y); と、BIGNUMのほうのシフト関数に渡している。で、シフトする数（width）がマイナスの場合、左右を反転して、内部APIに渡している。BIGNUMのほうの実装は、

VALUE
rb_big_lshift(VALUE x, VALUE y)
{
    long shift;
    int neg = 0;

    for (;;) {
	if (FIXNUM_P(y)) {
	    shift = FIX2LONG(y);
	    if (shift < 0) {
		neg = 1;
		shift = -shift;
	    }
	    break;
	}
	else if (RB_TYPE_P(y, T_BIGNUM)) {
	    if (!RBIGNUM_SIGN(y)) {
		VALUE t = check_shiftdown(y, x);
		if (!NIL_P(t)) return t;
		neg = 1;
	    }
	    shift = big2ulong(y, "long", TRUE);
	    break;
	}
	y = rb_to_int(y);
    }

    x = neg ? big_rshift(x, shift) : big_lshift(x, shift);
    return bignorm(x);
}

static VALUE
big_lshift(VALUE x, unsigned long shift)
{
    BDIGIT *xds, *zds;
    long s1 = shift/BITSPERDIG;
    int s2 = (int)(shift%BITSPERDIG);
    VALUE z;
    BDIGIT_DBL num = 0;
    long len, i;

    len = RBIGNUM_LEN(x);
    z = bignew(len+s1+1, RBIGNUM_SIGN(x));
    zds = BDIGITS(z);
    for (i=0; i<s1; i++) {
	*zds++ = 0;
    }
    xds = BDIGITS(x);
    for (i=0; i<len; i++) {
	num = num | (BDIGIT_DBL)*xds++<<s2;
	*zds++ = BIGLO(num);
	num = BIGDN(num);
    }
    *zds = BIGLO(num);
    return z;
}

という辺り。big_lshiftが何をやってるのか良く分からん……。numeric.cでシフト幅をwidthと名付けてあるのに、bignum.cのほうでは、shiftと呼んでいるのは不統一感があるけど作者が違うのかな。

numeric.c を眺めていて、

num = 0b1100110010101010

(0..15).each do |i|
  p num[i]
end

=>
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1

> [4[0], 4[1], 4[2], 4[4]]
=> [0, 0, 1, 0]

というInteger#[]という記法があるのを知った。