巷の噂で 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; [] <<1; end
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 が呼び出されていて、push は rb_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_m は rb_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<<2; end
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,9; end
end
r.report "<< v1" do
8000000.times do; [] <<0<<1<<2<<3<<4<<5<<6<<7<<8<<9; end
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,19; end
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<<9; end
$ 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
