[最適化マニアクス]知らないとはまるDictionaryの問題

C#

Dictionary便利ですよね。特に検索がO(1)で超高速なのが気に入ってます。

しかし世の中そんな甘くはありません。なにかしらのペナルティがあるのが世の常です。そこで今回は、O(1)アクセスを実現するかわりに、どういうデメリットがあるのか調べてみました。

  • メモリ使用量が多い
  • Listに比べアクセスが遅い
  • Enumをキーにすると遅い、boxingでgc allocが発生する
  • コードサイズが肥大化しやすい
  • シリアライズできない

メモリ使用量が多い

【C#】Dictionaryの実装・データ構造・アルゴリズムを考える。 | 創造的プログラミングと粘土細工

O(1)検索は魔法ではありません。上記のようなハッシュテーブルを追加で持っています。その分メモリ消費量がListに比べかなり多いです。

Unity2018.2.19f IL2CPP .net4.6 win standloneで測定してみました。 単位KB

要素数List<int>Dictionary<int,int>
1000421.8
1000039.1197.6
100000390.7424.4

Listは 4byte×要素数 +ヘッダとシンプルですね。Dictionaryは要素数100000だけおかしな値になりました。しかし要素数100000は使うことがないので無視してもよいでしょう。要素数1000、10000に限定してみれば、Listの約5倍です!メモリ消費量に神経質にならなければいけないモバイルゲームでは気をつける必要があります。

Listに比べアクセスが遅い

どうしてもhashcodeを計算する必要があるためListに比較して遅くなってしまいます。stringのhashcodeとなればさらに遅いでしょう。

ただし、これが露骨にボトルネックになることは現実のプロジェクトではあまりないです。

アセットバンドル名でのアクセスが一番考えられますが、高頻度でアクセスすることがないかぎり問題ないでしょ

Enumをキーにすると遅い、boxingでgc allocが発生する

測定してみると誤差程度です。特に.net4.6では高速化されているため気にしなくてよさそうです。

一方boxingによるgc allocの方は深刻です。アクセスするたびにgc allocが発生します。

回避策は

  • IEqualityComparerを実装したクラスを用意して、Dictionaryのコンストラクタに設定する
  • intにキャストして使う

あたりでしょうか。他には、

public enum Week
{
    Mon,
    Tue,
    Wed,
    Tur,
    Fri,
    Sat,
    Sun,
}
private string[] weekStr =
{
    "月","火","水","木","金","土","日"
};
public string GetWeekStr(Week week)
{
    return weekStr[(int)week];
}

このように、enumの配列に対応した要素配列をもつという方法もあります。気をつけるべき点として、enumに変更があった場合対応する配列もちゃんと更新しないと値がずれたり、配列範囲外アクセスになったりします。

コードサイズが肥大化しやすい

IL2CPP Internals: Generic sharing implementation – Unity Blog
This is the fifth post in the IL2CPP Internals series. In the last post, we looked at how methods are called in the C++ code generated for the IL2CPP scrip...

メモリ消費量に神経質になっている場合は、コードサイズも気をつけたいです。Dictionaryはkey, value型の組み合わせの分、コードが生成されます。そのため他のジェネリクスに比べコードサイズが増えやすいです(上記ある通りshareの概念があるため、参照型は気にしなくても大丈夫で

しかし最初からこれを意識してコードを書くのは、早すぎる最適化かなと思います。最後の最後にもうちょっと常駐メモリを削りたい…というときに検証してみるくらいでよいと思います。

シリアライズできない

ScriptableObjectやJsonUtilityでパースできません。

スポンサーリンク

まとめ

パフォーマンス上の落とし穴に気をつけて使いましょう。