🟰
【C#】構造体キーにはIEquatable<T>【ベンチマーク有】
背景
- 構造体を
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
はボクシングが発生してしまう
比較の意味を明確に定義できる
- 比較処理を自分で実装するため、許容値などを導入することができる
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>
が実装される
- 自動で
参考
- Microsoft - Dictionary<TKey,TValue> Class
- Microsoft - EqualityComparer<T>.Default Property
- Microsoft - Fundamentals of garbage collection
- BenchmarkDotNet
- 滅入るんるん - 【C#】構造体の防衛的コピーについて
- @shunsuke-saito-mummy - 今日からできるC#のパフォーマンス改善小ネタ11選
余談
- 調べる過程で「構造体も
readonly
化で防衛的コピー回避」というテクを知った- 内部状態の変更を防ぐため、コピーを返してデータの整合性を守る手法
- 非
readonly
構造体のreadonly
メンバを操作する際、コンパイルが自動で行う場合アリ - ということで
private readonly struct Key
に後々修正した
Discussion