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

目的

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

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

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

• sizeは最終的に必要となるシーケンス長
• addを用いるとあらかじめsizeが分かっている必要がないというメリットがある
• newSeq, newSeqOfCap, newSeqUninitialized, add, setLenについては公式ドキュメントを参照してください。

テストプログラム

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

ソースコード

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]"

実行環境

• 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の要素を参照した時に値が不定となるものを非安全としている。詳しくはこの記事で説明しています。

考察

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

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

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

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

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