【Unity/C#】DictionaryでCapacityを指定して初期化する場合の速度比較

別のページでC#のDictionaryに値を追加する場合、値を取得する場合の速度比較を行なってみました。その時の結果においてはContainsKeyによるキーの有無を確認するより、TryAddやTryGetValueなど、Try系のメソッドを使って追加や取得を行なった方が速くなりました。

値の追加を行う際、Dictionaryの要素数が増えていくとDictionaryの容量も増えていきます。今回のケースではデータ数が決まっていたため、Dictionaryの初期化時に容量を指定しておくことで容量変更の処理が減らせる可能性があったことから、追試験を行なってみたいと思います。一度作った性能比較用コードを使って何ページか書けるぜラッキー！　という気持ちもありはしますが、辞書を扱う際にデータ数の見積りができている場合に処理時間を減らせるのであればゲーム開発的にも多少貢献できるかもしれません。

以前確認したもの

エクスプラボ

【Unity/C#】DictionaryでTryGetValueのメソッドを使って処理速度を比較

https://ekulabo.com/dictionary-try-get-value

C#のDictionaryで値を追加・取得する際にTry系メソッドを使うか、ContainsKeyを使って存在確認をしてからAddや取得を行うか、といった部分を比較を行っています。実際にコードを書いて比較すると納得して使いやすくなりますね(ご満悦)

環境

MacBook Pro 2023 Apple M2 Max

Unity6 (6000.0.26f1) Silicon

比較するもの

C#のDictionaryについて、値を追加する対象のDictionaryに関して初期化時に容量を指定した場合としなかった場合で、追加の完了までの処理時間に変化があるかを比較してみます。

値の追加については、TryAddを使うケース、ContainsKeyで確認後にAddするケース、の2つを使って比較してみます。以前作ったコードを変更することなくそのまま比較できるようにしてあるため、そのまま使いまわしたいと思います。

結果の要約

TryAddを使うケース、ContainsKeyで確認後にAddするケースのどちらにおいても、Dictionaryの初期化時に容量を指定した方が速くなりました。

コード

調子に乗って色々便利になるよう改造していたらとても長くなってしまったので、以下のリポジトリをご覧ください。コメントで解説を加えているので、Updateあたりから出現したメソッドを辿っていただけると良いかもしれません。

GitHub

GitHub - todorok1/DictionarySpeedCheck: C#の辞書への値の追加、辞書からの値の...

https://github.com/todorok1/DictionarySpeedCheck

C#の辞書への値の追加、辞書からの値の取得の速度を比較するコード集. Contribute to todorok1/DictionarySpeedCheck development by creating an account on GitHub.

コード内では、Capacityの指定を行うかどうかのフラグをフィールドとして用意し、そのフラグを確認して初期化時にCapacityを指定するかどうかを決めています。

結果

1,000回、10,000回、100,000回、1,000,000回、10,000,000回と、辞書内の要素を変えて処理を行いました。

TryAddの比較

TryAddのメソッドを使ってCapacityの指定をした場合、しなかった場合の処理時間を比較してみます。試行回数は10回で、その平均時間をとっています。

全体的にCapacityを指定した方(左)が速い結果になりました。辞書内の要素数が容量に達したら辞書の容量を増やす処理が入ると考えれば、直感的で分かりやすい結果です。

ContainsKeyで確認後のAddの比較

ContainsKeyでキーの存在有無を確認してからAddしたケースです。TryAddの場合と同様に試行回数は10回で、その平均時間をとっています。

こちらも全体的にCapacityを指定した方が速い結果になりました。

感想

TryAddを使うケース、ContainsKeyで確認後にAddするケースのどちらにおいても初期化時にCapacityを指定した方が速くなりました。上でも書きましたが、データの追加中に容量変更の処理が入らない分だけ速くなるのは直感的ですね。

C#の実装(というよりは.NETの実装)はMicrosoft社が公開している以下のページで確認できます。

referencesource.microsoft.com

 

97 Users

606 Pockets

Reference Source

https://referencesource.microsoft.com

Dictionaryのクラスにある容量変更の処理を追ってみると、ざっくりと以下のような流れになっています。(.NET Framework4.8の時の情報なので、後年改善されている可能性あり)

1. DictionaryのAddが呼ばれる
2. Addメソッド内で、同じDictionaryクラス内のInsertメソッドが呼ばれる
3. freeCount(空き容量)のフィールドの値が0未満で、辞書の要素の長さに達していたらResizeメソッドを呼ぶ
4. Resizeメソッド内でHashHelpersクラスのExpandPrimeメソッドを呼んで変更後の容量を取得
5. ExpandPrimeメソッドでは元の容量を2倍して、それに近い素数を新しい容量として返す
6. Resizeメソッドのオーバーライドメソッド内で、要素の配列を新しい容量で作成して格納

素数に関しては、使われる頻度の高いものが配列として定義されていて、それより大きいものだと自力で計算して返しているようです。素数を使うのはハッシュ値の衝突の確率を減らすためです。

空き容量がなくなったら追加の処理が走る、というのもコードから読めたので直感、結果、実装が一致してスッキリです。

今回の実験においては追加されるデータ数が一定のため、固定でCapacityを指定していますが、実際にゲーム内で使用する場合はここまで大量のデータを扱うことはそうそうないかと思います。あっても1万くらいでしょうか？　要素量が少なければそこまで気にしなくても良い気がしますが、要素の規模が分かっている場合はあらかじめ指定しておくのも良いかもしれません。例えばアイテムの辞書を作る場合、アイテムが100種類前後あるなら初期化時の引数で200くらいを渡しておく、といった感じです。

おまけ

値の追加を行う際に、キーが重複しているケースも計測してみました。以前の計測では重複がない場合の比較だったので、辞書の容量変更の入らない状態で重複確認を行なってみましょう。

どちらもDictionaryの初期化時にCapacityの指定を行なって、重複対象のキーを追加後に計測を行なっています。

比較してみると、それぞれ重複がない場合に比べるとありの方が若干処理時間が長くなっていました。TryAddのデータ数1000の時は逆転していますが、全体の傾向を見るに桁数が少なくて誤差も入っていそうですね。

ContainsKeyで確認する場合、キー重複があれば追加処理を行わずに次に進むコードにしていました。追加処理がなくてもTryAddの方が速い結果になったので、追加時はTryAddがやはり有利なようです。

まとめ

Dictionaryを初期化する際にCapacityを指定しておくことで、容量変更の処理が呼ばれる回数が減らせることから処理時間が短くなります。Dictionaryに格納する要素数がある程度見積もれる場合には、初期化時のCapacity指定が有効に働きそうです。

この内容を書くにあたってC#のDictionaryのソースコードを読んだのも楽しかったです。普段何気なく使っているクラスやメソッドの中身を確認できるのは興味深く、速いと言われているメソッドがなぜ速いのか、時間のかかるメソッドが内部でどんな処理をしているのか、といった点を自分の目で追ってみるのも自己修練に良さそうですね。