背景

構造体を Dictionary キーに使ったら「IEquatable 実装しなよ」と言われた
その理由も、IEquatable 自体も知らなかった
Dictionary 自体の解説： Dictionaryの使い方と落とし穴

どんなプログラムをどうした？

改善前

private struct Key
{
    public Key(int a, int b) { this.a = a; this.b = b; }

    private readonly int a,b;
}
private Dictionary<Key, bool> state = new();

構造体をキーに用いる辞書を使用

改善後

private struct Key : IEquatable<Key>
{
    public Key(int a, int b) { this.a = a; this.b = b; }
    public bool Equals(Key other) => a == other.a && b == other.b;
    public override int GetHashCode() => HashCode.Combine(a, b);

    private readonly int a, b;
}
private Dictionary<Key, bool> state = new();

IEquatable<Key> を実装 (Equals, GetHashCode)

`IEquatable<T>` を実装したメリットは？

ボクシング(ボックス化)の回避

ボクシング自体の解説：int → objectの裏側、ボクシング,アンボクシングとは
キー比較の際、以下のように処理が進む

IEqualityComparer<T> 実装がなければ、EqualityComparer<T>.Default が使われる
その際、Key が IEquatable<T> を実装していれば Equals(T)、
していなければ object.Equals が使われる
構造体キーの場合、object.Equals はボクシングが発生してしまう

!

IEqualityComparer<T> は比較ロジックを定義するクラスで、
Dictionary などに渡した場合のみ使われる

var comparer = new MyCustomComparer(); //IEqualityComparer<T> 実装クラス
var dict = new Dictionary<MyKey, string>(comparer);

つまり、自分の型への IEquatable<T> 実装とはまた別の仕組み

比較の意味を明確に定義できる

比較処理を自分で実装するため、許容値などを導入することができる

public bool Equals(Pos other) => Math.Abs(x - other.x) < 0.001 && Math.Abs(y - other.y) < 0.001;

具体的にどう変わるのか、ベンチマーク計測

何をするのか

BenchmarkDotNet を使用
PlainKey, EquatableKey 構造体を作成
- 前者: readonly struct で IEquatable<T> 実装ナシ
- 後者: readonly struct で IEquatable<T> 実装アリ
2つの構造体をキーに Dictionary を作成 (TValue は bool)
TryGetValue を大量に呼び出し、検索時の実行速度とGC発生回数を比較

実際のプログラム

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

public class TestProgram
{
    public static void Main(string[] args) =>
        BenchmarkRunner.Run<BenchWork>();
}

[MemoryDiagnoser]
public class BenchWork
{
    [Params(1000, 100000)]
    public int N;

    private Dictionary<PlainKey, bool> dictPlain = new();
    private Dictionary<EquatableKey, bool> dictEquatable = new();

    [GlobalSetup]
    public void Setup()
    {
        for (int i = 0; i < N; i++)
        {
            dictPlain[new(i, i + 1)]     = true;
            dictEquatable[new(i, i + 1)] = true;
        }
    }

    [Benchmark(Baseline = true)]
    public int Lookup_Plain()
    {
        int hits = 0;
        for (int i = 0; i < N; i++)
        {
            if (dictPlain.TryGetValue(new PlainKey(i, i + 1), out _))
            {
                hits++;
            }
        }
        
        return hits;
    }

    [Benchmark]
    public int Lookup_Equatable()
    {
        int hits = 0;
        for (int i = 0; i < N; i++)
        {
            if (dictEquatable.TryGetValue(new EquatableKey(i, i + 1), out _))
            {
                hits++;
            }
        }

        return hits;
    }
}

public readonly struct PlainKey
{
    public PlainKey(int a, int b) => (A, B) = (a, b);

    public readonly int A, B;
}

public readonly struct EquatableKey : IEquatable<EquatableKey>
{
    public EquatableKey(int a, int b) => (A, B) = (a, b);

    public bool Equals(EquatableKey other) => A == other.A && B == other.B;
    public override int GetHashCode() => HashCode.Combine(A, B);

    public readonly int A, B;
}

ベンチマーク環境

ハードウェア
- OS: Windows 11 Home 24H2
- CPU: Intel Core i7-11800H @ 2.30GHz
- RAM: 32.0 GB
ソフトウェア環境
- .NET SDK: 8.0.4
- ランタイム: .NET 8.0.4 (CoreCLR)
- ビルド: Release

結果を比較

試行回数 1000

	平均実行時間(μs)	「ナシ」との相対速度	GC発生回数(世代0)	GC発生回数(世代1)	ヒープ割当合計バイト数(B)	「ナシ」との相対メモリ割当量
ナシ	1,770.64	1.00	640.6250	-	8049505	1.00
アリ	17.78	0.01	-	-	-	0.00

試行回数 100000

	平均実行時間(μs)	「ナシ」との相対速度	GC発生回数(世代0)	GC発生回数(世代1)	ヒープ割当合計バイト数(B)	「ナシ」との相対メモリ割当量
ナシ	17,449,928.41	1.000	6376000.0000	1000.0000	80004834064	1.000
アリ	2,691.95	0.000	-	-	2	0.000

補足

Dictionary に加え、HashSet, ConcurrentDictionary にも有効
record struct として IEquatable<T> に対応するのもアリ
- 自動で IEquatable<T> が実装される

参考

余談

調べる過程で「構造体も readonly化で防衛的コピー回避」というテクを知った
- 内部状態の変更を防ぐため、コピーを返してデータの整合性を守る手法
- 非readonly構造体の readonlyメンバを操作する際、コンパイルが自動で行う場合アリ
- ということで private readonly struct Key に後々修正した

Discussion