Nimのseqの初期化方法によるパフォーマンスの違い

# 目的
Nimの売りの一つはC言語に匹敵する（らしい）パフォーマンスの高さであるため、せっかくならパフォーマンスを気にしたコードを書きたい。
そこで、Nimの動的配列であるシーケンス(以下、`seq`)の初期化とシーケンス長(以下、`len`)拡張方法の違いによるパフォーマンスの違いを検証する。

# 今回検証する`seq`初期化と`len`拡張方法

1. `newSeq()`で初期化し、`add`でlenを一つずつ拡張する
1. `newSeq()`で初期化し、`setLen(size)`でlenを拡張する
1.  `newSeq(size)`で初期化及びlen指定する
1.  `newSeqOfCap(size)`で初期化し、`add`でlenを一つずつ拡張する
1.  `newSeqOfCap(size)`で初期化し、`setLen(size)`でlenを拡張する
1.  `newSeqUninitialized(size)`で初期化及びlen指定する

- sizeは最終的に必要となるシーケンス長
- `add`を用いるとあらかじめsizeが分かっている必要がないというメリットがある
- [newSeq](https://nim-lang.org/docs/system.html#newSeq), [newSeqOfCap](https://nim-lang.org/docs/system.html#newSeqOfCap%2CNatural), [newSeqUninitialized](https://nim-lang.org/docs/system.html#newSeqUninitialized%2CNatural), [add](https://nim-lang.org/docs/system.html#add%2Cseq%5BT%5D%5BT%5D%2CT), [setLen](https://nim-lang.org/docs/system.html#setLen%2Cseq%5BT%5D%5BT%5D%2CNatural)については公式ドキュメントを参照してください。

# テストプログラム

seqに1つずつ値を代入する処理におけるパフォーマンスを検証する。

<details><summary>ソースコード</summary><div>

```nim:seq_init_test.nim
var
  s: seq[int]
  s2: seq[int]
  time: float

s2 = newSeq[int](max_seq_size)
for i in countup(1, max_seq_size):
  s2[i-1] = i

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeq[int]()
  for i in countup(1, max_seq_size):
    s.add(s2[i-1] * 2)
echo "method 1: ", cpuTime() - time, "[sec]"

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeq[int]()
  s.setLen(max_seq_size)
  for i in countup(1, max_seq_size):
    s[i-1] = s2[i-1] * 2
echo "method 2: ", cpuTime() - time, "[sec]"

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeq[int](max_seq_size)
  for i in countup(1, max_seq_size):
    s[i-1] = s2[i-1] * 2
echo "method 3: ", cpuTime() - time, "[sec]"

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeqOfCap[int](max_seq_size)
  for i in countup(1, max_seq_size):
    s.add(s2[i-1] * 2)
echo "method 4: ", cpuTime() - time, "[sec]"

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeqOfCap[int](max_seq_size)
  s.setLen(max_seq_size)
  for i in countup(1, max_seq_size):
    s[i-1] = s2[i-1] * 2
echo "method 5: ", cpuTime() - time, "[sec]"

time = cpuTime()
for j in countup(1,max_itr_size):
  s = newSeqUninitialized[int](max_seq_size)
  for i in countup(1, max_seq_size):
    s[i-1] = s2[i-1] * 2
echo "method 6: ", cpuTime() - time, "[sec]"
```

</div></details>

## 実行環境
- OS : Ubuntu18.04 on Windows10 64bit WSL
- CPU : Intel Core i5-4690K
- Memory : 16GB
- Nim v1.0.4
- コンパイルコマンド : `nim c -d:release --opt:speed seq_init_test`

コンパイルオプションについては https://qiita.com/tlllune/items/0472fc5546e40b5ad5f4 を参照。


# 結果

10回計測した実行時間の平均値

||seq初期化|len拡張|実行時間[s]|安全性|
|:---:|---|:---|:---:|:---:|
|1|newSeq()|add|9.01|安全|
|2|newSeq()|setLen(size)|4.06|安全|
|3|newSeq(size)|-|3.52|安全|
|4|newSeqOfCap(size)|add|5.60|安全|
|5|newSeqOfCap(size)|setLen(size)|3.40|非安全|
|6|newSeqUninitialized(size)|-|3.36|非安全|

- 安全性については、値代入前に`seq`の要素を参照した時に値が不定となるものを非安全としている。詳しくは[この記事](https://qiita.com/tauplus/items/397d0c0615f1291f7464)で説明しています。

# 考察
- 1と4の比較から`seq`のCapacityはあらかじめ必要量を確保する方がよい。

- `newSeq()`を引数なしで呼び出すと`seq`のCapacityが0(デフォルト値)となり、`add`で`len`を1つずつ拡張すると何度もメモリの再割り当てが発生するため、方法1は可能なら避けた方がよい（明らかに他の方法より遅い）

- つまり、最終的に必要なsizeが分からない場合でも、方法4を用いて程度のCapacityを確保しておく方がよい

- 最終的に必要なsizeがあらかじめ分かっている場合は方法3が安全かつ高速である。

- 方法5,6は高速だが`seq`が初期化されないため`int`型の場合でも初期値が0とならず、`+=`などを使う場合は要注意である