Erlangは内部的に無駄なコピーをしていないのか？

# Erlangは内部的に無駄なコピーをしていないのか？

プログラミングElixirにデータが内部的に再利用される旨の記述がある.
もちろん知ってはいたが, そういえばちゃんと調べたことはなかったことを思い出した.
そこで, Erlang Termの実体がどのタイミングでコピーされるのかについて調べてみた.

なお, 何かよい関数がないか軽く調べたが, 出てこなかったのでクラッシュダンプを見るという原始的なことをやったので, 方法については割愛する.
また, BEAMに詳しい訳ではないので, 間違った情報が含まれているかもしれない. その点はご了承頂きたい.


## リスト

```erl
1> A = [1,2,3].
2> B = A ++ [4,5,6].
3> C = [4,5,6 | A].
```

これの実体はこうなった. 

    A : 1 | * --> 2 | * --> 3 | * --> nil
    B : 1 | * --> 2 | * --> 3 | * --> 4 | * --> 5 | * --> 6 | * --> nil
    C : 4 | * --> 5 | * --> 6 | * --> A

ErlangのリストはLispと同様の構造……1つのtermと次へのポインタのセットが数珠繋ぎになった構造を取る.
そして, Headへの追加の場合はコピーは発生せず, Tailへの追加はコピーが発生することが分かる.

なお, これらは `erts_debug:size/1` , `erts_debug:internal_size/1` の結果が同じ値となる.
これは, Cも構造としてはBと同じであり, 変数間で共通している部分については考慮されないからである.

rawデータは以下のようになっている.

    7F10C083AF40:t2:A1:A,H7F10C083B048
    7F10C083B048:lI1|H7F10C083B120
    7F10C083B120:lI2|H7F10C083B168
    7F10C083B168:lI3|N
    7F10C083AF58:lH7F10C083B058|H7F10C083B070
    7F10C083B058:t2:A1:B,H7F10C083B130
    7F10C083B130:lI1|H7F10C083B178
    7F10C083B178:lI2|H7F10C083B1A8
    7F10C083B1A8:lI3|H7F10C083B1D8
    7F10C083B1D8:lI4|H7F10C083B208
    7F10C083B208:lI5|H7F10C083B228
    7F10C083B228:lI6|N
    7F10C083B070:lH7F10C083B140|N
    7F10C083B140:t2:A1:C,H7F10C083B188
    7F10C083B188:lI4|H7F10C083B1B8
    7F10C083B1B8:lI5|H7F10C083B1E8
    7F10C083B1E8:lI6|H7F10C083B048
## タプル

```erl
1> A = {1, 2, 3}.
2> B = {A, 4}. % {{1, 2, 3}, 4}
3> C = setelement(2, B, 5). % {{1, 2, 3}, 5}
4> D = setelement(1, B, 6). % {6, 4}
```

これの実体はこうなった.

    A : {1, 2, 3}
    B : {A, 4}
    C : {A, 5}
    D : {6, 4}

rawデータは以下.

    7FB967F625F0:lH7FB967F38350|H7FB967F62668
    7FB967F38350:t2:A1:A,H7FB967F38330
    7FB967F38330:t3:I1,I2,I3
    7FB967F62668:lH7FB967F38388|H7FB967F62758
    7FB967F38388:t2:A1:B,H7FB967F383A0
    7FB967F383A0:t2:H7FB967F38330,I4
    7FB967F62758:lH7FB967F386D8|H7FB967F62808
    7FB967F386D8:t2:A1:C,H7FB967F38720
    7FB967F38720:t2:H7FB967F38330,I5
    7FB967F62808:lH7FB967F62828|N
    7FB967F62828:t2:A1:D,H7FB967F62850
    7FB967F62850:t2:I6,I4

record/tupleを作り直す場合は一番外側のtupleだけ作り直されるのが分かる.
integerのような小さな物に関しては例外でコピーされる. (ポインタを挟む意味がないですからね)


## バイナリ

バイナリは[ドキュメント](http://erlang.org/doc/efficiency_guide/binaryhandling.html)を参考にした方が良いが, 大事なところのみ纏める.


コンテナ

- refc binaries（参照カウンターバイナリー）
 - プロセスヒープの外にバイナリ自体は保存される。
 - 参照カウンターによって管理される
- heap binaries
 - 64bytesに満たない小さな物で、プロセスヒープに直接保存される。

参照

 - sub binaries
  - split_binary/2 とパターンマッチで生成される
  - コンテナの一部分を参照する
  - コピーは発生しない
 - match contexts
  - パターンマッチに最適化されている
  - バイナリデータへの直接のポインタを含む


## マップ

OTP19時点でhashmapとflatmapが内部的には存在する.
どこから切り替わるかについての記述が見当たらなかったが,

```erl
1> erts_internal:term_type(maps:from_list([{X, X} || X <- lists:seq(1, 32)])).
flatmap
2> erts_internal:term_type(maps:from_list([{X, X} || X <- lists:seq(1, 33)])).
hashmap
```

およそ, 33要素からhashmapになると思われる.

### flatmap

結論から言うと, mapについてはcrashdumpの読み方が分からなかった.
なので, mapに入れた後に取り出してみて, 同じアドレスを指しているかどうかで判別した.


```erl
1> A = #{1 => 2}.
#{1 => 2}
2> B = #{3 => A}.
#{3 => #{1 => 2}}
3> C = #{A => 3}.
#{#{1 => 2} => 3}
4> D = C#{A := 4}.
#{#{1 => 2} => 4}
5> B2 = maps:get(3, B).
#{1 => 2}
6> C2 = maps:keys(C).  
[#{1 => 2}]
7> D2 = maps:keys(D).
[#{1 => 2}]
```

    B2: A
    C2: A | * --> nil
    D2: A | * --> nil

となっており, key/valueともに使い回している状況が確認できた.

rawデータは以下.

    7FC6992C4728:lH7FC6992C3DF8|H7FC6992C4738
    7FC6992C3DF8:t2:A1:A,H7FC6992C3D00
    7FC6992C3D00:ED:83640009756E646566696E6564
    7FC6992C4738:lH7FC6992C3E70|H7FC6992C4748
    7FC6992C3E70:t2:A1:B,H7FC6992C3E88
    7FC6992C3E88:ED:83640009756E646566696E6564
    7FC6992C4748:lH7FC6992C4608|H7FC6992C4758
    7FC6992C4608:t2:A2:B2,H7FC6992C3D00
    7FC6992C4758:lH7FC6992C40A0|H7FC6992C4768
    7FC6992C40A0:t2:A1:C,H7FC6992C40E0
    7FC6992C40E0:ED:83640009756E646566696E6564
    7FC6992C4768:lH7FC6992C46F0|H7FC6992C4778
    7FC6992C46F0:t2:A2:C2,H7FC6992C4718
    7FC6992C4718:lH7FC6992C3D00|N
    7FC6992C4778:lH7FC6992C4190|H7FC6992C4788
    7FC6992C4190:t2:A1:D,H7FC6992C41A8
    7FC6992C41A8:ED:83640009756E646566696E6564
    7FC6992C4788:lH7FC6992C4798|N
    7FC6992C4798:t2:A2:D2,H7FC6992C47B0
    7FC6992C47B0:lH7FC6992C3D00|N


## まとめ

勝手にアドレスを使い回してくれるので, BEAMを信じて (binaryのgcは経験上気をつける必要がありますが), あまり気にせずに実装しても問題なさそうです.