要約

C#のDictionaryのキーとして2つのint x,y (ただしxとyは[-32768, 32767]の範囲内)を使いたい場合、(x << 16) ^ yとHashCodeを計算すると処理が早くなりました。

When use two int x and y (where x and y range is [-32768, 32767]), as keys in a C# Dictionary, computing the hash code using the expression (x << 16) ^ y can improve performance.

背景

xとyが高々[-10000, 10000]の範囲に収まるグリッド状の2Dマップがあって、1マスごとにDataクラスを持つとします。方法はいくつかあると思いますが、まずは2次元配列を試してみます。

// 巨大すぎる配列を使う例(数GB以上になってNG)
var map = new Data[20001, 20001];
var (xi, yi) = (x + map.Length / 2, y + map.Length / 2);
map[xi, yi] = data;

配列がこれほど大きいと仮にDataが1バイトだったとしても約3GBの配列になってしまい使用に耐えません。却下です。

次にDictionaryを使って必要なデータだけ保持しておくことを考えます。

// Dictionaryのキーに(int, int)を使う例
var map = new Dictionary<(int, int), Data>();
map[(x, y)] = data;

使用するキーの型は色々使えますが、とりあえず簡単に実装できるValueTupleの(int, int)にしてみました。x,yを変えて色々AddしたりLookupしたりしましたが、ちゃんと動くようです。

他にも128x128などでChunk化した2次元配列をDBから動的にロードしたり様々な方法があると思いますが、今回はシンプルに実装できるDictionaryを使ってみたいと思います。

では、そのDictionaryのキーには何を使えば一番早いのかが気になって調べたのがこの記事の趣旨です。結論から言うと、調べた中では次のコードが一番早かったです。

// intの上位16bitをx, 下位16bitをyとする
// xyが[-32768, 32767]の範囲を超えると衝突して遅くなる
var map = new Dictionary<int, Data>();
var hash = (x << 16) ^ y;
map[hash] = data;

Dictionaryがキーから格納位置を決める仕組み

まず、Dictionaryがどのように動作しているかについてですが、私が下手に説明するより次のページを見てもらった方が良いと思うのでとりあえず貼ります。

「与えられたKeyに対してGetHashCode()を行い、そのハッシュからテーブル内の位置を決め、ハッシュが衝突していればEquals()で一致確認をしつつ別の空きスペースを線形に探す」といった感じでしょうか。

なので、GetHashCode()の結果が[-10000, 10000]の中で衝突していると、それだけ線形探索のコストが掛かってしまうことになります。DictionaryのAddやLookupはO(1)と思いきや、HashCodeが全部同じなら全て線形探索してしまってO(N)になる可能性があるということですね。

理想的には、[-10000, 10000]の中でどんなxyを選んでもハッシュが全て異なる、単射なハッシュ関数が見つかると良いので探してみましょう。

(int,int)だとHashCodeがほとんど衝突する？

ということで様々な方法についてHashCodeの衝突率を調べていたのですが、実はValueTupleの(int,int)を使うとGetHashCode()が[-1000, 1000]の範囲で既にほとんど衝突していることが分かります。次のコードは衝突率を調べたものです。

var hashes = new HashSet<int>();
var ok = 0;
var ng = 0;

// xyが[-1000, 1000]の範囲、約4,000,000マスのHashCodeの衝突を計測
// [-10000,10000]にしたらメモリが足りなかったので1000にした
for (int x = -1000; x <= 1000; x++) {
    for (int y = -1000; y <= 1000; y++) {
        var hashCode = (x, y).GetHashCode();
        if (hashes.Add(hashCode)) {
            ok++;
        } else {
            ng++;
        }
    }
}

Debug.Log($"OK {ok}");
Debug.Log($"NG {ng}");
Debug.Log($"CollisionRate {(float)ng / (ok + ng)}");

実行すると次のようにHashCodeの衝突率が分かります。

OK 67584
NG 3936417
CollisionRate 0.9831209

計測ミスを疑いましたが、98.3%も衝突してました。マジ？

今回はHashSetにintを直接入れたので衝突したときにAddが失敗しましたが、(int,int)をキーに使うと、ハッシュが衝突してもEquals()によって「ハッシュは同じだが内部のx,yが異なる」と判定されて線形探索によりAddが成功してしまいます。なので、普段使っていて98.3%も衝突していることに全く気が付きませんでした。

もちろん実行環境によって変わることも想定されますが、安定して高速で動かしたいので、衝突率の低いGetHashCode()を用意することにします。

試した方法たち

GetHashCode()の実装として有力そうな方法を、UnityのTestRunnerを使用してそれぞれ20回計測して中央値を取りました。まずは結果から。

Name	処理	衝突率	Add > Lookup(Median)
Test1	(x, y).GetHashCode()	98.31%	12.61 s
Test2	(17 * 23 + x) * 23 + y	99.40%	16.04 s
Test3	System.HashCode.Combine(x, y)	0%	6.50 s
Test4	new Unity.Mathematics.int2(x, y).GetHashCode()	0%	4.29 s
Test5	(x << 16) ^ y	0%	2.41 s

その他の指標

※ 衝突率と速度はx, yともに[-1000, 1000]という限られた範囲内での値です（メモリ不足のため範囲を縮小しています）

速度は次の処理で計測しています。DictionaryにKey-Valueを追加してから、Keyで参照する処理を繰り返しました。

const int Range = 1000;

const int WarmupCount = 5;
const int IterationsPerMeasurement = 10;
const int MeasurementCount = 20;

[Test]
[Performance]
public void Test1() => TestLoops((x, y) => new TestStruct1(x, y));

[Test]
[Performance]
public void Test2() => TestLoops((x, y) => new TestStruct2(x, y));

[Test]
[Performance]
public void Test3() => TestLoops((x, y) => new TestStruct3(x, y));

[Test]
[Performance]
public void Test4() => TestLoops((x, y) => new TestStruct4(x, y));

[Test]
[Performance]
public void Test5() => TestLoops((x, y) => new TestStruct5(x, y));

void TestLoops<T>(Func<int, int, T> hashGetter)
{
    Measure.Method(() => {
        // 衝突した状態での線形探索コストが計測できるように
        // Keyをx,yのstructにしてHashCodeが衝突してもEqualsが異なる状態を作る
        var map = new Dictionary<T, bool>();

        for (int x = -Range; x <= Range; x++) {
            for (int y = -Range; y <= Range; y++) {
                // Add
                var key = hashGetter(x, y);
                map.Add(key, true);

                // Lookup
                var value = map[key];

                // 最適化で消えないために適当な処理を入れる
                Debug.Assert(value != !value);
            }
        }
    })
    .WarmupCount(WarmupCount)
    .IterationsPerMeasurement(IterationsPerMeasurement)
    .MeasurementCount(MeasurementCount)
    .Run();
}

public readonly struct TestStruct1 : IEquatable<TestStruct1>
{
    public readonly int x;
    public readonly int y;

    public TestStruct1(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public override int GetHashCode()
    {
        // ここをstructごとに入れ替えてGetHashCodeの性能を計測する
        return (x, y).GetHashCode();
    }

    public bool Equals(TestStruct1 other)
    {
        return x == other.x && y == other.y;
    }

    public override bool Equals(object other)
    {
        if (other is TestStruct1 point) {
            return Equals(point);
        }
        return false;
    }
}

(以下略)

全てのコードはこちらのgistから確認ください。

ちなみに今回はHashCode衝突後の線形探索の速度を検証するために、Keyとしてintではなくstructを使用していますが、そのstructの中でGetHashCodeをoverrideしなかったり、IEquatable<T>を実装しなかったりすると速度が10倍以上遅くなりました。DictionaryのKeyにstructを使うときは実装しましょうね。

また、UnityでのTestRunnerを使用した測定方法についてはこちらのページを参考にさせていただきました。貴重な情報をありがとうございます。

各Testについて

Test1: (x, y).GetHashCode()

(int,int)でHashCodeを取得する処理はネットでよく見るので無難な方法なのかなと思っていましたが、98.31%と想像よりも多く衝突して驚きました。

C#のValueTupleの実装を追っていくと、HashHelpers.Combineで行っていることがわかり、手元で同じメソッドを試してみると確かに衝突率が98.31%になっています。

コンパイラの最適化によって速度が大きく変わる可能性もありますが、HashCodeの衝突率には変わりないと思うので今回は見送りました。

Test2: (17 * 23 + x) * 23 + y

こういった素数を掛けたり値を足してHashCodeを生成する方法はよく見ますが、これも99.40%と衝突率が非常に高く、結果的に試した中では一番遅くなってしまいました。なお、この1行は次の数行をまとめたものです。

var hash = 17;
hash = hash * 23 + x;
hash = hash * 23 + y;
return hash;

Test3: System.HashCode.Combine(x, y)

最も汎用的に使えるものがどれかと言えばこの関数でした。

public override int GetHashCode()
{
    return System.HashCode.Combine(x, y);
}

int2つの64bitをint1つの32bitに無理やりまとめているので原理的には結構衝突するはずですが、今回の範囲では衝突率0%でした。なお、後述するTest5では2^16の[-32768, 32767]を超えるとかなり衝突が多くなりますが、この関数はなぜかその範囲を超えても衝突するケースが全然見つかりません。なんで……？

C#の内部実装っぽいものは見つけたのですが、原理を全く説明できないのでリンクだけ貼っておきます。パッと見ではビットシフトや素数の掛け算をしていそうなので、逆算すれば衝突する組み合わせが見つかる可能性はありますが、計算が不可逆かもしれないし、私としてはそこまでやる必要もなかったので省略します。

ほとんど正解みたいな関数ですが、今回の限られた状況ではTest5の方が早かったので見送りました。

Test4: new Unity.Mathematics.int2(x, y).GetHashCode()

今回の範囲内では衝突せず、思ったより早いです。しかし、Unity限定のクラスのため汎用性がないのと、int2がreadonlyではないstructなので、DictionaryのKeyとして使うには問題があると判断して見送りました。

内部実装はおそらくこちら。何をやっているのか検討もつきません。

Test5: (x << 16) ^ y

最後に、xyの範囲が[-32768, 32767]に収まる場合はこの方法が最速でした。なお、この2^16の範囲を超えると一気に衝突が増えて使い物にならなくなります。

一見してyを符号付きでマスクもしないままxorしているので、「こんなん絶対どっかで衝突するだろ」と思って色々調べたのですが、どうやら16桁ごとの上位1bitがうまく機能して範囲内では衝突しないようです。（限界値周辺の数百万通りのHashを調べましたが大丈夫でした。）

うまく説明できないのですが、[-32768, 32767]の範囲ならyの上位16bitが全て0か1になるので、符号付きのままxorしても実質的にMaskされているかのように振る舞えているのだと思います。私には知識がなく厳密な証明ができないため、もし衝突する(x, y)の組み合わせなど見つけた方はお知らせください。

結果として私の手元では衝突するケースが1つも見つからず、最悪衝突してもEquals()でなんとかなるので僅かな例外は気にせず平均的な速度を取ることにしました。

おまけ: (x << 16) | (y & 0xFFFF)

yの上位16bitがMaskされてないのが気になる方はこちらを使ってください。こちらも確認した限りでは衝突しませんし、Test5とほとんど同じ速度です。次のページを参考にしました。

さらに高速化(非推奨)

さて、2つの[-32768, 32767]を1つの[-2147483648, 2147483647]へ一意に変換するGetHashCodeを作れたとすれば、ハッシュが衝突したときのEqualsによる線形探索の保険をかけずに、直接HashCodeを計算してintをKeyにぶち込めばもっと早くできるはずです。

Name	処理	衝突率	Add > Lookup(Median)
Test5	new Dictionary<struct, bool>()	0%	2.39 s
Test5'	new Dictionary<int, bool>();	0%	1.48 s

ただ、バグなどによって範囲外の値が1つでも入ってしまうと、突然例外が発生したり、逆に発生すべき部分で発生しなかったりと辛い状態になりそうなのでおすすめしません。前提条件がはっきりしている競プロでは時々役立つかも。

まとめ

C#のDictionaryのキーとして2つのint x,y (ただしxとyは[-32768, 32767]の範囲内)を使いたい場合、(x << 16) ^ yとHashCodeを計算すると処理が早くなりました。

ただし、その範囲を超えることが予想される場合はSystem.HashCode.Combineが汎用的で十分に高速なのでそちらをおすすめします。

検証環境

Unity 2021.3.9f1
Test Framework Version 1.3.3
Performance testing API 2.8.1-preview

Discussion