2017/02/11


巷の噂で 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

2017/02/08


僕は日々 memolist.vim という Vim plugin を使い、仕事で思いついた疑問点や会話の一部をメモ取りする様にしています。相手と会話している最中に「あ、ここ大事だ」と思ったら vim を起動して :MemoNew してメモを編集していました。もちろん Vim ですから起動は抜群に速くてとてもご機嫌良く動くのですが、どうしてもこれをシェルから扱いたいという要求に負けてささっと作ってみました。

GitHub - mattn/memo: Memo Life For You

README.md memo Memo Life For You Usage NAME: memo - Memo Life For You USAGE: memo [global options] c...

https://github.com/mattn/memo
memo

とても単純なコマンドなのです。やりたい事は単純です。

  • 即座にメモ取りを開始したい
  • Markdown で書きたい
  • 簡単に grep したい
  • シェルと融合したい
  • できれば jekyll っぽく markdown をサーブしたい
memo new を実行するとタイトルを聞かれるます。このタイトルがファイル名に使われます。形式は Jekyll の様な日付付きのファイル名です。memo list を実行すると保持しているエントリ一覧を表示します。端末で表示する場合には先頭の行(おそらくタイトル)も表示されます。シェル等でパイプから使う場合にはファイル名のみ渡されます。このファイル名は memo edit xxx の様に編集コマンドに引き渡せます。引数を省略して memo edit とすると流行りのコマンドラインセレクタが起動して編集するファイル名を簡単に絞り込めます。
memo edit

なお、memo list --fullpath にはフルパスにも出来ますのでシェルスクリプトから何かしたい場合にも使えます。さらに memo grep keyword で grep する事もできます。あのメモどこだっけ、という場合に使います。おまけ機能ですが memo serve でウェブサーバが起動する様になっています。ブラウザが勝手に起動して

memo serve

この様なエントリ一覧が表示されます。リンクをクリックすると Markdown が HTML として表示されます。

memo serve

とっさに誰かにメモの内容を見てもらいたい場合には有効かもしれません。設定のデフォルト値を変更したい場合は memo config を実行すると TOML ファイルを指定してエディタ(デフォルトはもちろん Vim)が起動するのでお好きなコマンドセレクタや grep コマンド、テキストエディタに変更して下さい。もちろんワンバイナリで UNIX、Windows どちらでも動く様にしてあります。


2017/02/01


以前からずっと疑問に思っていた事があった。

ruby の後置 if/unless で条件が偽になった場合でも代入構文が実行されるのはどうしてだろう

例えば以下のコードを irb や pry で実行してみて欲しい。

a = 1 if false

続けて a をタイプする。すると nil が表示される。

僕のこれまでの理解だと後置if/unlessは、ステートメントに作用するのでそのステートメント自体が無効になる、つまり代入自体されなかった事になるという理解だった。ruby のパーサのソースコードを見ても後置ifはステートメントに作用している様だった。

        | stmt modifier_if expr_value
            {
            /*%%%*/
            $$ = new_if($3, remove_begin($1), 0);
            fixpos($$$3);
            /*%
            $$ = dispatch2(if_mod, $3, $1);
            %*/
            }
だって raise "foo" if false で例外が飛ばないなら、代入もされないでしょと思っていたけど nil が代入される。この ruby のコードを AST ダンプするとこうなる。
# @ NODE_SCOPE (line: 1)
# +- nd_tbl: :a
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_PRELUDE (line: 1)
#     +- nd_head:
#     |   (null node)
#     +- nd_body:
#     |   @ NODE_IF (line: 1)
#     |   +- nd_cond:
#     |   |   @ NODE_FALSE (line: 1)
#     |   +- nd_body:
#     |   |   @ NODE_DASGN_CURR (line: 1)
#     |   |   +- nd_vid: :a
#     |   |   +- nd_value:
#     |   |       @ NODE_LIT (line: 1)
#     |   |       +- nd_lit: 1
#     |   +- nd_else:
#     |       (null node)
#     +- nd_compile_option:
#         +- coverage_enabled: true

これを見ると、AST に落とし込んだ時点でノードテーブルに a が現れている。つまり、後置ifが偽であろうとも代入構文を認識しているという事になる。この AST をどう walk しても代入構文には到達しないよなーと悩んでソースを見たりしたけど良く分からなかったので Matz に直接聞いた。

つまり ruby はこの stmt modifier_if expr_value を見つけると、まずステートメントが何かを判定して代入構文であれば変数 a を用意し、そのあと後置ifを判定して最後に代入という動きを取る。もちろん後置ifが偽であれば代入はされない。よって a は初期化されたままの nil が格納されるという事になる。これを理解した上で以下を見ると、なぜ NameError: undefined local variable or method `a' for main:Object ではなく NoMethodError: undefined method `+' for nil:NilClass なのか理解できた。なるほど深い。

irb(main):001:0> a = a + 1
NoMethodError: undefined method `+' for nil:NilClass
        from (irb):1
        from c:/msys64/mingw64/bin/irb.cmd:19:in `<main>'
irb(main):002:0>