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

# ことの始まり

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

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

これって一般的に遅いコードという認識は割と有名で、だいたい1.6倍ぐらい遅くなるということが知られています。（[ソースはここ](https://github.com/JuanitoFatas/fast-ruby#enumerableeach--push-vs-enumerablemap-code)）ところで、なぜ遅くなるかを解説した人はそんなに多くありません。
正直、

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

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

# やりたいこと

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

# 処理の比較
## `Array#<<`

### 処理順

- [method define](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L6299)
    - [`rb_ary_push`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L917)
        - [`ary_ensure_room_for_push`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L358)
            - [`ary_double_capa`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L250)
                - [`ary_resize_capa`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L205)
                    - [`MEMCOPY`](https://docs.ruby-lang.org/ja/latest/function/MEMCPY.html)
                    - or [`SIZED_REALLOC_N`](`https://github.com/ruby/ruby/blob/d83536c980fb96a880def3e952eb4920815eeb51/internal.h#L1322`)
                        - [`REALLOC_N`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/include/ruby/ruby.h#L1604)
                            - [`RB_REALLOC_N`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/include/ruby/ruby.h#L1598)
                                - [`ruby_xrealloc2`](`https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/include/ruby/defines.h#L234`)
                                    - [`ruby_xrealloc2_with_location`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/include/ruby/defines.h#L284)
                                        - ...
        - [`RB_OBJ_WRITE`](https://github.com/ruby/ruby/blob/d83536c980fb96a880def3e952eb4920815eeb51/include/ruby/ruby.h#L1487)

### 軽い解説

```
+-----+-----+-----+
| &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](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L6300)
    - [`rb_ary_push_m`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L956)
        - [`rb_ary_cat`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L929)
            - `ary_ensure_room_for_push`
            - [`ary_memcpy0`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L172)
                - [`MEMCOPY`](https://github.com/ruby/ruby/blob/d83536c980fb96a880def3e952eb4920815eeb51/include/ruby/ruby.h#L1691)
                    - `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 よりも速いか](https://mattn.kaoriya.net/software/lang/ruby/20170211232700.htm)

## `Array#map`

### 処理順

- [method define](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L6326)
    - [`rb_ary_collect`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L2744)
        - [`rb_ary_new2`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/include/ruby/intern.h#L90)
            - [`rb_ary_new_capa`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L479)
                - [`ary_new`](https://github.com/ruby/ruby/blob/384fda18b885872aacf225ac6ad7805fb101e497/array.c#L453)
        - `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動かすときに証明書やら必要になるので）

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

Docker コンテナ内で以下実行

```shell
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
```

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

```ruby:~/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の起動はこんなかんじ

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

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