RubyのArray#unshiftが速すぎる件と償却解析

プログラミング言語によって呼ばれ方はさまざまであるが、rubyにおいてpushは Arrayの最後尾にあらたな要素を付け足す処理を指す。

a = [1,2,3,4,5]
a.push('push')
puts a # => [1, 2, 3, 4, 5, 'push']

Linked Listではなく、Arrayという名前が付いているということは、格納された要素はメモリ上で連続した領域に配置されている必要がある。この時、問題になるのがメモリの確保のやり方だ。

a = []
a.push('push')
a.push('push')
a.push('push')
a.push('push')

上の様にArrayに対して1個ずつ要素が追加されていった際に、pushが呼ばれるたび新なArrayのためのメモリを確保していたのでは、pushのたびにmallocが動作することになり、非常に効率が悪い。
そこで、ruby(やその他のプログラミング言語)では、以下のように要素の追加によってArrayの領域の拡張の必要が生じた際に、現在の要素数の倍の領域を確保しておき、将来の更なる要素の追加に備えるというやり方が取られている。

array-push

このようにメモリ確保という遅い操作を避け、平均的な計算量を下げる最適化は償却解析と呼ばれる。

unshiftの計算量

一方でunshiftは、以下のように配列の先頭に要素を付け足す動作を指している。

a = [1,2,3,4,5]
a.unshift('unshift')
puts a # => ['unshift', 1, 2, 3, 4, 5]

この場合には、unshiftを実行するたびに新な要素を先頭に加えたArray全体の領域をmallocするのでpushの場合と比較して配列の要素が大きくなるほど、計算時間が大きくなっていくような気がする。

array-unshift

ところが、実際はそうではなかった。以下のようなコードで確認してみると実行結果は、pushが0.09秒に対して、unshiftが0.08秒で、実行時間に大差はなかった。

a = []
t = Time.now
1_000_000.times{a.unshift(1)}
puts "unshift: #{Time.now - t}"

a = []
t = Time.now
1_000_000.times{a.push(1)}
puts "push: #{Time.now - t}"

これはかなり予想外の結果だった。確認のためjavascriptとpythonで同様の比較を試してみるとunshiftはpushに較べて明らかに低速で、rubyのunshiftが異常に速い事が分かる。

言語	push	unshift
ruby (MRI 2.6.0)	0.09	0.08
javascript (node v12.2.0)	0.04	251.47
python (c-python 3.7.2)	0.12	331.53

(pythonの場合は、push,unshiftという名前のメソッドではなくappend,insert)

unshiftの償却解析

調べてみるとRuby 2.0.0(MRI)から以下のコミットでunshiftに対しても償却解析が導入されていた。
https://github.com/ruby/ruby/commit/fdbd3716781817c840544796d04a7d41b856d9f4

肝になるのが、以下のary_ensure_room_for_unshift関数になる。

static VALUE
ary_ensure_room_for_unshift(VALUE ary, int argc)
{
    // 中略
    if (head - sharedp < argc) {
        long room;
      makeroom:
        room = capa - new_len;
        room -= room >> 4;
        MEMMOVE((VALUE *)sharedp + argc + room, head, VALUE, len);
        head = sharedp + argc + room;
    }
    // 中略
}

この関数では、unshiftが実行されたが、先頭に追加するための領域が存在しない時 MEMMOVEで、既存のArrayの内容をsharedp(実際のデータが入る領域のポインタ)から、argc(unshiftで付け足す要素の個数)とroom(将来のunshiftに備えた領域)の分だけ余裕を持たせた位置に格納している。

このようにunshiftの場合も償却解析されている事実はunshiftしていった際のArrayのサイズを以下のように見ていくことでも別る。

[5] pry(main)> a = []
=> []
[6] pry(main)> ObjectSpace.memsize_of(a)
=> 40
[7] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 40
[8] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 40
[9] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 192
[10] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 192
[11] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 192
[12] pry(main)> ObjectSpace.memsize_of(a.unshift(1))
=> 192

unshiftでの償却解析はArrayクラスをキュー(unshiftが頻繁に必要になる)として使用する場合を想定して行われた様だ。
細かな工夫だが場合によっては劇的にパフォーマンスを改善してくれる修正だ。rubyコミュニティすごい