2017/02/11

Recent entries from same category

  1. Ruby の a = a + 1 はなぜ undefined method '+' for nil:NilClass なのか
  2. Re: Ruby 製バッチ処理を省メモリ化した
  3. Crystal と CRuby でHTTPサーバのベンチマーク
  4. pure mruby な JSON パーサ書いた。
  5. bundle exec がウザい

巷の噂で Ruby の Array#<<Array#push よりも速いと聞いたので調べてみた。まずはベンチマークを取ってみた。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push" do
    8000000.times do; [].push(1); end
  end
  r.report "<<" do
    8000000.times do; [] <<1end
  end
end

結果は以下の通り。

                 user     system      total        real
push         1.570000   0.000000   1.570000 (  1.579687)
<<           1.280000   0.000000   1.280000 (  1.288951)

確かに Array#<< の方が速い。実際何が違うのか調べてみる。

array.c のソースを見ると、確かに <<push は違う処理が行われていた。

<< の処理

<<rb_ary_push が呼び出されていて、pushrb_ary_push_m が呼び出されている。rb_ary_push (push と言いながら <<)は以下のコード。
VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, 1);
    RARRAY_PTR_USE(ary, ptr, {
        RB_OBJ_WRITE(target_ary, &ptr[idx], item);
    });
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

ary_ensure_room_for_push で追加する領域を伸張し、RB_OBJ_WRITE で格納、ARY_SET_LEN で配列長を再設定している。RARRAY_PTR_USE は Array の実装で少量の場合とそうでない場合に VALUE の格納方法を変えており、それをシームレスに扱うためのマクロになっている。RB_OBJ_WRITE は実際は rb_obj_write でありコードは以下の通りになっている。

static inline VALUE
rb_obj_write(VALUE a, VALUE *slot, VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
#ifdef RGENGC_LOGGING_WRITE
    RGENGC_LOGGING_WRITE(a, slot, b, filename, line);
#endif

    *slot = b;

#if USE_RGENGC
    rb_obj_written(a, RUBY_Qundef /* ignore `oldv' now */, b, filename, line);
#endif
    return a;
}

世代別 GC は有効なのでライトバリアされる事になる。

static inline VALUE
rb_obj_written(VALUE a, RB_UNUSED_VAR(VALUE oldv), VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
#ifdef RGENGC_LOGGING_OBJ_WRITTEN
    RGENGC_LOGGING_OBJ_WRITTEN(a, oldv, b, filename, line);
#endif

#if USE_RGENGC
    if (!RB_SPECIAL_CONST_P(b)) {
        rb_gc_writebarrier(a, b);
    }
#endif

    return a;
}

push の処理

rb_ary_push_mrb_ary_cat をそのまま呼び出し

VALUE
rb_ary_cat(VALUE ary, const VALUE *argv, long len)
{
    long oldlen = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, len);
    ary_memcpy0(ary, oldlen, len, argv, target_ary);
    ARY_SET_LEN(ary, oldlen + len);
    return ary;
}

ary_ensure_room_for_push で伸長し、ary_memcpy0 で空いたところにコピーし、ARY_SET_LEN で配列長を再設定。<< とほぼ同じ。ただ ary_memcpy0 は単なる memcpy ではない。

static void
ary_memcpy0(VALUE ary, long beg, long argc, const VALUE *argv, VALUE buff_owner_ary)
{
#if 1
    assert(!ARY_SHARED_P(buff_owner_ary));

    if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) {
        rb_gc_writebarrier_remember(buff_owner_ary);
        RARRAY_PTR_USE(ary, ptr, {
            MEMCPY(ptr+beg, argv, VALUE, argc);
        });
    }
    else {
        int i;
        RARRAY_PTR_USE(ary, ptr, {
            for (i=0; i<argc; i++) {
                RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]);
            }
        });
    }
#else
    /* giveup write barrier (traditional way) */
    RARRAY_PTR(buff_owner_ary);
    MEMCPY(RARRAY_PTR(ary)+beg, argv, VALUE, argc);
#endif
}

Array#push は一度に複数個の値を追加できる。

a = []
a.push 1,2,3,4,5

この個数が一定以上であればこのコードは異なる処理を行う。VALUE は実際は単なるポインタでしかない。uintptr_t なので8バイト。つまり push で一度に16個足すと rb_gc_writebarrier_remember でライトバリア用のマーキングが行われ、先ほど説明した RARRAY_PTR_USE で直接 VALUE のメモリを得て MEMCPY でメモリを書き込む。

反対側は << をループで回したのと同じコードになる。

ちなみに一度に2個の要素を追加するベンチマークも取ってみた。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push" do
    8000000.times do; [].push(1,2); end
  end
  r.report "<<" do
    8000000.times do; [] <<1<<2end
  end
end
                 user     system      total        real
push         1.570000   0.000000   1.570000 (  1.584534)
<<           1.620000   0.000000   1.620000 (  1.634777)

2個目から push の方が速くなった。

分かったこと

この2つを見て、<<push の速さを決める条件が3つある事が分かった。

  • 1個だけで << もしくは push する
  • 2個以上16個未満で push する
  • 16個以上で push する

最初の場合、<<push はフェアになる。ただし push の場合は上記の通り、一定個数以上で別の処理を行う為に条件文が1箇所あるのと1個の為にforループを回す処理がある。よって上記のベンチマーク結果の様に若干ではあるが << の方が速くなる。

次に16個未満の場合。コードの例だと以下。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push v1" do
    8000000.times do; [].push 0,1,2,3,4,5,6,7,8,9end
  end
  r.report "<< v1" do
    8000000.times do; [] <<0<<1<<2<<3<<4<<5<<6<<7<<8<<9end
  end
  r.report "push v2" do
    8000000.times do; [].push(0).push(1).push(2).push(3).push(4).push(5).push(6).push(7).push(8).push(9); end
  end
  r.report "<< v2" do
    8000000.times do; (((((((((([]<<0)<<1)<<2)<<3)<<4)<<5)<<6)<<7)<<8)<<9); end
  end
end

この場合、<< は一度に1つしか追加できないので <<push はフェアではない。

                 user     system      total        real
push v1      5.220000   0.010000   5.230000 (  5.276128)
<< v1        6.990000   0.000000   6.990000 (  7.050749)
push v2     10.000000   0.010000  10.010000 ( 10.098266)
<< v2        6.980000   0.000000   6.980000 (  7.198814)

純粋にインタプリタが実行する量に比例してしまう為、当然の事ながら push が速くなる。

最後に push の量が16個以上の時とそうでない場合。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push v1" do
    8000000.times do; [].push 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19end
  end
  r.report "push v2" do
    8000000.times do; [].push(0,1,2,3,4,5,6,7,8,9).push(0,1,2,3,4,5,6,7,8,9); end
  end
end

push を2回実行しているのでCの世界とRubyの世界を1回多く回っている分、フェアではないけれどベンチマークを取ってみた。

                 user     system      total        real
push v1      5.760000   0.000000   5.760000 (  5.817951)
push v2      6.320000   0.010000   6.330000 (  6.404566)

想像通り、16個以上の場合の方が早くなった。

まとめ

今回の調査で以上の事が分かった。

Array に要素を足す場合

  • 1個であれば << の方が速い
  • 2個以上であれば push の方が速い

ただしベンチマーク結果から分かる様に、ループ回数が多いので差が出ている様に見えるが実際大した差ではないので書きやすい方で書いたらいい。

なお、mruby の場合 <<処理push処理は同じだった。ベンチマークも想像通り。

5000000.times do; [].push(0,1,2,3,4,5,6,7,8,9); end
5000000.times do; [].push 0<<1<<2<<3<<4<<5<<6<<7<<8<<9end
$ time bin/mruby.exe push1.rb

real    0m5.574s
user    0m0.000s
sys     0m0.015s

$ time bin/mruby.exe push2.rb

real    0m9.412s
user    0m0.015s
sys     0m0.000s

blog comments powered by Disqus