Dictionary<TKey, TValue>のキーにするならGetHashCodeとIEquatable<T>を実装しよう

初めに

あるコードでDictionaryを使っていました。
そのコードでパフォーマンスが要求されるようになったので調べてそもそもDictionaryから値を取り出すのもそれなりに重い様子...ということで少しでもパフォーマンスを上げるためにはどうしたらいいかと調べたのでそのメモです。

結論

タイトル通りですが、キーに使うstructには

• GetHashCodeをオーバーライド実装する
• IEquatableを実装する

と改善されました。

もともとの実装と計測

もともとの実装は以下のようなstructをキーとして利用していました。
(名前は適当に変更してあります)

public struct IntPair
{
  public int a;
  public int b;
}

// これをキーに使う例
public Dictionary<IntPair, string> _dict = new ();

Unity上で動かしていたので、この実装でシンプルに_dict.Addと_dict.TryGetValueを1000回ずつ回してプロファイラを見てみました。
※Deep Profileなので実際にはもう少し処理時間は短いはずです。

赤枠で囲った部分がDictionaryのAddとTryGetValueの部分です。
これを見るに、キーの比較にかなり時間がかかってそうですね。

改善する

Dictionaryのリファレンスを見るに、ざっくりとですが

• GetHashCodeをオーバーライドする
• 等価比較を実装する

とよさそうです。ちなみに、等価比較はいくつか方法がありそうですが今回は型の中で完結したいのでIEquatable<T>を選択しています。

これを反映すると、

public struct IntPair : IEquatable<IntPair>
{
    public int a;
    public int b;

    public bool Equals(IntPair another)
    {
        return this.a == another.a && this.b == another.b;
    }

    public override int GetHashCode()
    {
        return (this.a << 16) ^ this.b;
    }
}

こんな感じになりました。

さて、結果はというと...

GC Alloc も処理速度もめちゃくちゃ改善してます！
呼び出しもかなりシンプルになっており、効果は絶大でした。
ただし、裏を返せばGetHashCodeやEqualsの実装は気を付けないとパフォーマンスに大きな影響が出そうですね。
GetHashCodeとか、なるべくかぶらないように、かつ高速な演算が必要なので少し複雑な型だと難しそう...(そんな型をキーにするかといわれるとしない気がしますが)

まとめ

GetHashCodeとIEquatable<T>を実装すると、Dictionaryのキーにしたときにパフォーマンスが改善する！

注意点

今回、EqualsとGetHashCodeを実装しましたがGetHashCodeの影響が大きそうです。
呼び出し回数を見た感じ、GetHashCodeを実装したことでハッシュの衝突回数が減っているのかEqualsが呼び出される回数が極端に低いです。
とは言え、Equalsも呼び出しがシンプルになっているので効果はありそうなのと、Dictionaryの構造上ハッシュ計算で等価比較の回数を減らすのが重要であるのでこの2つをやっておけば良さそうという結論でよいのかなと思っています。