(Array#each + Array#push) v.s. Array#map

ことの始まり

よく、レビューでこんなコードを見かけます。

hoge_array = []
fuga_array.each do |val|
  hohe_array << something(val)
end

これって一般的に遅いコードという認識は割と有名で、だいたい1.6倍ぐらい遅くなるということが知られています。（ソースはここ）ところで、なぜ遅くなるかを解説した人はそんなに多くありません。
正直、

hoge_array = fuga_array.map do |val|
  something(val)
end

と書いたほうがまぁ読みやすいですし、そういう理由でもいいんですが、mapを積極的に使う理由を今回はちゃんと見直そうと思います。

やりたいこと

• Array#map と Array#each + Array#push （もしくは Array#<<）の違い

処理の比較

Array#<<

処理順

• method define
  • rb_ary_push
    • ary_ensure_room_for_push
      • ary_double_capa
        • ary_resize_capa
          • MEMCOPY
          • or SIZED_REALLOC_N
            • REALLOC_N
              • RB_REALLOC_N
                • ruby_xrealloc2
                  • ruby_xrealloc2_with_location
    • RB_OBJ_WRITE

軽い解説

+-----+-----+-----+
| &p0 | &p1 | &p2 |
+-----+-----+-----+

なメモリ領域をもともと持っている配列 ary が ary_ensure_room_for_push によって

+-----+-----+-----+-----+
| &p0 | &p1 | &p2 | nil |
+-----+-----+-----+-----+

みたいに伸長した配列を新たにメモリ上の別空間に確保し、 RB_OBJ_WRITE によって、書き込みたい値 p3 が

+-----+-----+-----+-----+
| &p0 | &p1 | &p2 | &p3 |
+-----+-----+-----+-----+

このように入る。

Array#push

処理順

• method define
  • rb_ary_push_m
    • rb_ary_cat
      • ary_ensure_room_for_push
      • ary_memcpy0
        • MEMCOPY
          • memcpy
        • or RB_OBJ_WRITE

軽い解説

• ほとんど Array#<< 一緒だが、実際にメモリのアドレスを確保するときにpushは複数個確保することができる(ex: ary.push(1,2,3,4,5))。
  • 一度に追加する要素数が16個以上だと、 MEMCOPY で値を入れる
    • Cの実装で直接メモリオブジェクトが一気に処理される。(っぽい)
  • 16個未満だと RB_OBJ_WRITE で一個ずつ for で繰り返し挿入される

複数個を一気に追加できるなら << を使うより push で配列を渡したほうが良さそう。

詳しい解説: Big Sky :: Ruby の Array#<< は Array#push よりも速いか

Array#map

処理順

• method define
  • rb_ary_collect
    • rb_ary_new2
      • rb_ary_new_capa
        • ary_new
    • rb_ary_push

軽い解説

大きく違うのは、 rb_ary_new2 によって事前にまとめてメモリを確保しているところ。この rb_ary_new2 は「長さ（Array#length）が0で指定要素数のぶんだけのメモリを事前に確保する」処理を持っている。これにより、 rb_ary_push 内部の ary_ensure_room_for_push でメモリの再割当てが発生しない。具体的にかくと、

+-----+-----+-----+
| &p0 | &p1 | &p2 | length = 3
+-----+-----+-----+

という配列があったとき、 rb_ary_new2 によって

+-----+-----+-----+
| &p0 | &p1 | &p2 | length = 3
+-----+-----+-----+


+-----+-----+-----+
| nil | nil | nil | length = 0
+-----+-----+-----+

なメモリを確保する。このとき、新しい配列の現在のポインタは

   ↓(p)
+-----+-----+-----+
| nil | nil | nil | length = 0
+-----+-----+-----+

ここを見ている。 rb_ary_push によって

+-----+-----+-----+
| &p0 | &p1 | &p2 |
+-----+-----+-----+
   ↓
 block
   ↓　    ↓(p)
+-----+-----+-----+
| &p7 | nil | nil | length = 1
+-----+-----+-----+

となって順々にポインタの値が埋まっていく。lengthは元の配列を絶対に超えないので、 ary_ensure_room_for_push によるメモリ再割当ては絶対に発生しない。

まとめると

Array#each + (Array#push or Array#<<) は格納先の配列オブジェクトで ary_ensure_room_for_push を実行するときにたびたびメモリ再割当てが発生しやすくなり遅くなるが、 Array#map による同様の処理は、 rb_ary_new2 により一度に配列を指定長確保できるため、処理が早いことがわかった。

おまけ: いちおうやったDocker/gdb/rubyデバッグ環境準備（デバッグ環境が必要な方向け）

Dockerコンテナ立てます。MacOSだといろいろ面倒なことも多いです。（特にgdb動かすときに証明書やら必要になるので）

docker run -it --cap-add=SYS_PTRACE --security-opt seccomp=unconfined ubuntu bash

Docker コンテナ内で以下実行

apt-get update
apt-get install -y build-essential zlib1g-dev libyaml-dev libssl-dev libgdbm-dev libreadline-dev libncurses5-dev libffi-dev curl checkinstall libxml2-dev libxslt-dev libcurl4-openssl-dev libicu-dev logrotate python-docutils pkg-config cmake gdb git autoconf automake libtool bison ruby vim
cd
git clone --depth 1 https://github.com/ruby/ruby.git 
cd ruby
autoreconf
./configure --disable-install-rdoc optflags="-O0" debugflags="-g3"
make
make install

例えば以下のようなファイルを準備しておきます。

~/test_array.rb

test_array_1 = [1, 2, 3]

test_array_2 = test_array_1.map do |item|
  item * 2
end

puts test_array_1
puts test_array_2

gdbの起動はこんなかんじ

gdb --args ./ruby ./test_array.rb

あとはお好きにCの関数にbreakpointを貼ったりしてください。