8
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

NimAdvent Calendar 2019

Day 11

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

Last updated at Posted at 2019-12-10

目的

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(デフォルト値)となり、addlenを1つずつ拡張すると何度もメモリの再割り当てが発生するため、方法1は可能なら避けた方がよい(明らかに他の方法より遅い)

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

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

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

8
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?