🟰

【C#】構造体キーにはIEquatable<T>【ベンチマーク有】

に公開
C#
tech
コレクション
tech

背景

  • 構造体を 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> を実装したメリットは？

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

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

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

  • 比較処理を自分で実装するため、許容値などを導入することができる
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