構造体のEqualityとパフォーマンス最適化

2025/02/28(Fri) 00:23 Higtyのシステムの作り方

ｋこの記事は

https://devblogs.microsoft.com/premier-developer/performance-implications-of-default-struct-equality-in-c/

の日本語訳です。

はじめに

C# でカスタム構造体（struct）を定義する際、「Equals と GetHashCode を常にオーバーライドすべき」というアドバイスを耳にしたことがあるかもしれません。パフォーマンス上の理由が挙げられることが多いのですが、なぜそうした推奨があるのかを詳しく見ていきましょう。

本記事では、まずデフォルトの Equals/GetHashCode 実装が抱える問題とその原因を紹介し、次に実プロジェクトで発生したパフォーマンスバグの事例を見たうえで、最後にこれらの問題を回避するためのツールやアプローチを紹介します。

どの程度重要な問題か？

パフォーマンス上の懸念事項であっても、アプリケーション全体の処理時間に大きな影響を与えない場合もあります。たとえば Enum.HasFlag の実装は古いランタイムでは効率的とは言えませんが、もしこれが非常に頻繁に呼び出される“ホットパス”にないなら、最終的な処理時間への影響は大きくないでしょう。同様に、readonly 構造体ではない構造体を in パラメータとして受け取る際に発生する防御的コピーも、状況によっては大きく目立たない可能性があります。

ただし、今回取り上げる「構造体で Equals/GetHashCode をオーバーライドしていないせいで発生するデフォルト実装の問題」は、アプリケーションのエンドツーエンドのパフォーマンスにかなりの影響を与える可能性があります。なぜなら、構造体でこれらを明示的にオーバーライドしない場合、System.ValueType に定義されているデフォルトの実装が呼ばれますが、これが非常に非効率的になり得るからです。

なぜデフォルト実装は遅いのか？

CLRの設計上、構造体で Equals や GetHashCode をオーバーライドしないと、以下のような理由でパフォーマンスが悪くなる可能性があります。

ボクシングによるアロケーションが発生する
CLR では、System.ValueType や System.Enum に定義されたメンバーを呼び出すとき、通常はボクシングが発生します。
※ ただし JIT イントリンシックとして最適化される場合は除きます。たとえば .NET Core 2.1 以降では Enum.HasFlag は最適化され、ボクシングせずに処理できます。
デフォルトの GetHashCode が衝突しやすい実装になり得る
一般的に、「速いハッシュ関数」と「衝突の少ない（分布の良い）ハッシュ関数」を両立させるのは難しいものですが、ValueType.GetHashCode のデフォルト実装は特に分布の面で問題を引き起こす場合があります。
具体的には、リフレクションを使って構造体の最初の「非 null フィールド」のハッシュコードを取り、それに型IDを混ぜ合わせる簡易的な手法が用いられています（詳しくは .NET Runtime のソースコードを参照）。そのため、「最初のフィールド」が多くのインスタンスで同じ値になるような構造体を大量にハッシュセットなどに格納すると、ほぼ同じハッシュ値が返るために衝突が多発し、パフォーマンスが大きく低下してしまいます。
リフレクションベースの実装がとにかく遅い
ValueType.Equals/ValueType.GetHashCode では、内部的にフィールド取得のためのリフレクションが使われるケースがあります（型によっては最適化される場合もありますが、後述するように条件は厳しいです）。リフレクションは高コストな操作なので、ホットパスで大量に呼ばれると深刻な性能劣化を引き起こします。

デフォルト実装の遅さをベンチマークで確認

下記のサンプルでは、同じ構造体でもフィールドの順序によってハッシュが衝突しやすい場合と衝突しにくい場合の違い、そして Equals/GetHashCode をカスタム実装した場合の性能差を計測しています。

public readonly struct Location1
{
    public string Path { get; }
    public int Position { get; }
    public Location1(string path, int position) => (Path, Position) = (path, position);
}

public readonly struct Location2
{
    // フィールドの順序を変えただけ！
    public int Position { get; }
    public string Path { get; }
    public Location2(string path, int position) => (Path, Position) = (path, position);
}

public readonly struct Location3 : IEquatable<Location3>
{
    public string Path { get; }
    public int Position { get; }
    public Location3(string path, int position) => (Path, Position) = (path, position);

    public override int GetHashCode() => (Path, Position).GetHashCode();
    public override bool Equals(object other) => other is Location3 l && Equals(l);
    public bool Equals(Location3 other) => Path == other.Path && Position == other.Position;
}

private HashSet<Location1> _locations1;
private HashSet<Location2> _locations2;
private HashSet<Location3> _locations3;
// 中略: _locations1, _locations2, _locations3 を初期化してベンチマークを実施

見てわかるように、Location1（最初のフィールドが string Path で、同じ空文字列が入る）の場合は、ほぼ同じハッシュ値を返してしまうため大幅に衝突が増え、HashSet がリストのような挙動になってしまいます。一方、Location2 では最初のフィールドが int なので、値が連番であればそこそこ分散します。また、Location3 ではそもそも GetHashCode と Equals を明示的に実装し、衝突しにくいようにしてあるため高速です。

実際に起きたパフォーマンス問題の事例

あるプロジェクトで、エンドツーエンドの実行時間が 10 秒から 60 秒に急増したという報告がありました。ETW トレースを見ると、ValueType.Equals に 50 秒も費やされていることがわかりました。

原因は単純で、以下のように「デフォルト実装の構造体をタプルと組みにして HashSet に大量格納」しており、さらにその最初のフィールドがほぼすべて同じ値（空文字列）だったのです。


private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;

readonly struct ErrorLocation
{
    // 空の場合がほとんど
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

要素数が少ないうちは問題なかったものの、要素数が大きくなるにつれ衝突回数が爆発的に増え、ValueType.Equals（リフレクションを多用）による処理時間が数十秒にも膨れ上がってしまったわけです。

デフォルト実装は常に遅いわけではない？

実は、ValueType.Equals/ValueType.GetHashCode には特別な最適化が存在します。構造体に「参照型フィールド」がなく、かつメモリ配置的に“詰め込みやすい”場合（アンマネージ参照がなく、パディングが少ない等）は、memcmp で一気に比較するなど高速化が行われる可能性があります。

// Optimized ValueType.GetHashCode
static INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef)
{
    INT32 hashCode = 0;
    INT32 *pObj = (INT32*)pObjRef;

    // ポインタやアライメントが“怪しく”ない構造体なら
    // 4 バイトごとに XOR してハッシュ値を作る
    INT32 size = mt->GetNumInstanceFieldBytes();
    for (INT32 i = 0; i < (INT32)(size / sizeof(INT32)); i++)
        hashCode ^= *pObj++;

    return hashCode;
}

ただし、この最適化が働くかどうかは非常に微妙な条件に左右され、少しでもレイアウトが変わると無効になる場合があります（フィールドの並びやアライメントでオンオフされるなど）。さらに、たとえば「-0.0 と +0.0 は IEEE 754 的にはビット列が異なる」というように、単に memcmp での比較が正しい等価性を示すとは限らないケースがあり得ます。つまり、「たまたま最適化されるから安全」と思いこむのは危険です。

どうやって今後この問題を避けるか

「構造体では必ず Equals と GetHashCode をオーバーライドするべき」というルールを FxCop（CA1815）などを使って強制するのは一つの方法です。しかし、巨大なコードベースで、ハッシュセットに入れない構造体まで含めてすべて警告が上がると、結局は多くの箇所で警告を抑制する羽目になり、実際に危険なケースを見逃す可能性もあります。

そこで、より実用的には「デフォルト実装の構造体（プロジェクト内定義や外部ライブラリ定義）が、HashSet や Dictionary などハッシュベースのコレクションに使われるタイミングを検知して警告する」静的解析ルールを導入するのがおすすめです。著者が開発している ErrorProne.NET では、この種のケースを検出するアナライザーを提供しています。

注意: 「カスタムの IEqualityComparer<T> を明示的に渡している場合」など、一部の正当なケースでも警告が出るかもしれません。しかし、「デフォルト実装のまま構造体がハッシュセットに入る」という状況をまずは誤検知覚悟で警告してくれるだけでも、重大なパフォーマンス問題を未然に防ぐうえで有益です。

まとめ

構造体のデフォルトの Equals/GetHashCode は、状況によって深刻なパフォーマンス劣化を引き起こす可能性がある。
CLR のデフォルト実装はリフレクションに頼りがちで、衝突も起きやすく、ホットパスに入るとアプリ全体の応答時間を大きく損なう場合がある。
ただし、一部の構造体に対しては memcmp ベースの最適化が入るが、条件が厳しく、わずかなコード変更で無効化されるリスクがある。また、-0.0 と +0.0 の比較など、ビット比較だけでは正しい等価性を保てないケースもある。
最も安全なのは、構造体で Equals/GetHashCode をしっかりオーバーライドし、必要に応じて分布の良いハッシュを実装しておくこと。
あるいは、構造体をハッシュベースのコレクションで利用する際に警告を出すようなアナライザー（たとえば ErrorProne.NET）を導入して、リスクを検知する。

参考リンク

以上が、構造体の Equals と GetHashCode をデフォルト実装のままにしておくと起こり得るパフォーマンス問題と、その回避策についての解説となります。C# で構造体を扱う際には、ハッシュ計算が絡む部分に注意を払うことをぜひ心がけてください。