The Go Blog
Swiss TablesでGoマップを高速化
ハッシュテーブルはコンピュータサイエンスにおける中心的なデータ構造であり、Goを含む多くの言語でマップ型の実装を提供します。
ハッシュテーブルの概念は、1953年にハンス・ピーター・ルーンによって内部のIBMメモで初めて記述されました。このメモでは、アイテムを「バケット」に配置し、バケットがすでにアイテムを含んでいる場合はオーバーフローにリンクリストを使用することで検索を高速化することを提案していました。今日では、これをチェイニングを用いたハッシュテーブルと呼ぶでしょう。
1954年、ジーン・M・アムダール、エレイン・M・マクグロー、アーサー・L・サミュエルは、IBM 701のプログラミングで初めて「オープンアドレス」スキームを使用しました。バケットがすでにアイテムを含んでいる場合、新しいアイテムは次の空のバケットに配置されます。このアイデアは、1957年にW・ウェスリー・ピーターソンによって「ランダムアクセスストレージのアドレス指定」で形式化され、発表されました。今日では、これを線形探索を用いたオープンアドレスハッシュテーブルと呼ぶでしょう。
これほど長く使われているデータ構造については、「完成している」と考えがちです。つまり、それらについて知るべきことはすべて知られており、これ以上改善できないと。しかし、それは真実ではありません！コンピュータサイエンスの研究は、アルゴリズムの複雑さの観点からも、最新のCPUハードウェアを活用する観点からも、基本的なアルゴリズムにおいて進歩を続けています。例えば、Go 1.19では、sortパッケージが従来のクイックソートから、2015年にオーソン・R・L・ピーターズによって初めて記述された新しいソートアルゴリズムであるパターン対策クイックソートに切り替わりました。
ソートアルゴリズムと同様に、ハッシュテーブルのデータ構造も改善され続けています。2017年、Googleのサム・ベンザケン、アルキス・エヴロギメノス、マット・クルクンディス、ローマン・ペレペリツァは、「Swiss Tables」と名付けられた新しいC++ハッシュテーブル設計を発表しました。2018年には、彼らの実装がAbseil C++ライブラリでオープンソース化されました。
Go 1.24には、Swiss Table設計に基づいた組み込みのマップ型の全く新しい実装が含まれています。このブログ記事では、Swiss Tablesが従来のハッシュテーブルをどのように改善しているか、そしてSwiss Table設計をGoのマップに導入する上でいくつかのユニークな課題について見ていきます。
オープンアドレスハッシュテーブル
Swiss Tablesはオープンアドレスハッシュテーブルの一種なので、基本的なオープンアドレスハッシュテーブルがどのように機能するかを簡単に見てみましょう。
オープンアドレスハッシュテーブルでは、すべてのアイテムが単一のバッキング配列に格納されます。配列内の各位置をスロットと呼びます。キーが属するスロットは主にハッシュ関数hash(key)によって決定されます。ハッシュ関数は各キーを整数にマッピングし、同じキーは常に同じ整数にマッピングされ、異なるキーは理想的には整数の均一なランダム分布に従います。オープンアドレスハッシュテーブルの決定的な特徴は、キーをバッキング配列内の別の場所に格納することで衝突を解決することです。そのため、スロットがすでに満杯（衝突）の場合、探索シーケンスを使用して空のスロットが見つかるまで他のスロットを検討します。この仕組みを見るために、サンプルハッシュテーブルを見てみましょう。
例
以下に、ハッシュテーブルの16スロットのバッキング配列と、各スロットに格納されているキー（もしあれば）を示します。この例では値は関係ないため、表示していません。
| スロット | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| キー | 56 | 32 | 21 | 78 |
新しいキーを挿入するには、ハッシュ関数を使用してスロットを選択します。スロットは16個しかないので、この範囲に制限する必要があります。したがって、hash(key) % 16をターゲットスロットとして使用します。キー98を挿入したいとし、hash(98) % 16 = 7だとします。スロット7は空なので、そこに98を挿入するだけです。一方、キー25を挿入したいとし、hash(25) % 16 = 3だとします。スロット3はすでにキー56を含んでいるため衝突です。したがって、ここには挿入できません。
別のスロットを見つけるために探索シーケンスを使用します。さまざまなよく知られた探索シーケンスがあります。元々の最も簡単な探索シーケンスは、単純に連続するスロットを順番に試す線形探索です。
したがって、hash(25) % 16 = 3の例では、スロット3が使用中のため、次にスロット4を検討します。これも使用中です。スロット5も同様です。最終的に空のスロット6にたどり着き、そこにキー25を格納します。
検索も同じアプローチに従います。キー25の検索はスロット3から始まり、キー25が含まれているかどうかを確認し（含まれていません）、その後、スロット6でキー25が見つかるまで線形探索を続けます。
この例では、16個のスロットを持つバッキング配列を使用しています。16個以上の要素を挿入するとどうなるでしょうか？ハッシュテーブルがスペース不足になると、通常、バッキング配列のサイズを倍にして拡張します。既存のエントリはすべて新しいバッキング配列に再挿入されます。
オープンアドレスハッシュテーブルは、バッキング配列が完全に満杯になるまで実際に待つことはありません。なぜなら、配列が満杯になるにつれて、各プローブシーケンスの平均長が増加するからです。上記のキー25の例では、空のスロットを見つけるために4つの異なるスロットをプローブする必要があります。配列に1つしか空のスロットがなければ、最悪のプローブ長はO(n)になります。つまり、配列全体をスキャンする必要があるかもしれません。使用済みのスロットの割合をロードファクターと呼び、ほとんどのハッシュテーブルは、非常に満杯なハッシュテーブルの非常に長いプローブシーケンスを避けるために、最大ロードファクター（通常70-90%）を定義し、その時点で拡張します。
Swiss Table
Swiss Tableの設計もオープンアドレスハッシュテーブルの一種です。従来のオープンアドレスハッシュテーブルと比べてどのように改善されているか見てみましょう。ストレージ用の単一のバッキング配列はありますが、配列を8スロットずつの論理的なグループに分割します。（より大きなグループサイズも可能です。これについては後述します。）
さらに、各グループにはメタデータ用の64ビットの制御ワードがあります。制御ワードの8バイトのそれぞれは、グループ内のスロットの1つに対応しています。各バイトの値は、そのスロットが空であるか、削除されているか、または使用中であるかを示します。使用中の場合、バイトにはそのスロットのキーのハッシュの下位7ビット（h2と呼ばれる）が含まれます。
| グループ0 | グループ1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| スロット | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| キー | 56 | 32 | 21 | 78 | ||||||||||||
| 64ビット制御ワード0 | 64ビット制御ワード1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| スロット | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| h2 | 23 | 89 | 50 | 47 | ||||||||||||
挿入は次のように行われます。
hash(key)を計算し、ハッシュを2つの部分に分解します。上位57ビット（h1と呼ぶ）と下位7ビット（h2と呼ぶ）。- 上位ビット（
h1）は、最初に検討するグループを選択するために使用されます。この場合、グループが2つしかないのでh1 % 2です。 - グループ内では、すべてのスロットがキーを保持する資格が同じです。まず、いずれかのスロットにこのキーがすでに含まれているかどうかを判断する必要があります。その場合、これは新しい挿入ではなく更新です。
- いずれのスロットにもキーが含まれていない場合、このキーを配置する空のスロットを探します。
- いずれのスロットも空でない場合、次のグループを検索して探索シーケンスを続行します。
検索も同じ基本的なプロセスに従います。ステップ4で空のスロットが見つかった場合、挿入がこのスロットを使用していたはずだとわかり、検索を停止できます。
ステップ3は、Swiss Tableの魔法が起こる場所です。グループ内のいずれかのスロットに目的のキーが含まれているかどうかを確認する必要があります。単純に線形スキャンを実行して8つのキーすべてを比較することもできます。しかし、制御ワードを使用すると、これをより効率的に行うことができます。各バイトには、そのスロットのキーのハッシュの下位7ビット（h2）が含まれています。制御ワードのどのバイトに探しているh2が含まれているかを特定できれば、候補となる一致のセットが得られます。
言い換えれば、制御ワード内でバイトごとの等値比較を行いたいのです。例えば、h2 = 89であるキー32を探している場合、行いたい操作は次のようになります。
| テストワード | 89 | 89 | 89 | 89 | 89 | 89 | 89 | 89 |
| 比較 | == | == | == | == | == | == | == | == |
| 制御ワード | 23 | 89 | 50 | - | - | - | - | - |
| 結果 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
これは、単一の命令がより大きな値（ベクトル）内の独立した値に対して並列操作を実行するSIMDハードウェアによってサポートされる操作です。この場合、特殊なSIMDハードウェアが利用できない場合でも、標準的な算術演算とビット演算のセットを使用してこの操作を実装できます。
結果は候補スロットのセットです。h2が一致しないスロットは一致するキーを持たないのでスキップできます。h2が一致するスロットは潜在的な一致ですが、衝突の可能性があるため（7ビットハッシュでは1/128の衝突確率なので、まだかなり低い）、キー全体をチェックする必要があります。
この操作は非常に強力です。なぜなら、プローブシーケンスの8ステップを一度に並行して実行したからです。これにより、実行する必要のある比較の平均回数が減り、検索と挿入が高速化されます。このプローブ動作の改善により、AbseilとGoの両方の実装で、以前のマップと比較してSwiss Tableマップの最大ロードファクターを増やすことができ、平均メモリフットプリントが削減されました。
Goの課題
Goの組み込みマップ型には、新しいマップ設計を採用する上で追加の課題となるいくつかの珍しい特性があります。特に扱いにくい点が2つありました。
漸進的成長
ハッシュテーブルが最大ロードファクターに達すると、バッキング配列を拡張する必要があります。通常、これは次の挿入で配列のサイズが倍になり、すべてのエントリを新しい配列にコピーすることを意味します。1GBのエントリを持つマップに挿入することを想像してください。ほとんどの挿入は非常に高速ですが、マップを1GBから2GBに拡張する必要がある1つの挿入は、1GBのエントリをコピーする必要があり、これには長い時間がかかります。
Goは遅延に敏感なサーバーで頻繁に使用されるため、組み込み型に対する操作がテールレイテンシーに任意に大きな影響を与えることを望みません。代わりに、Goマップは漸進的に成長し、各挿入が実行しなければならない成長作業の量に上限を設けます。これにより、単一のマップ挿入の遅延への影響が制限されます。
残念ながら、Abseil (C++) のSwiss Table設計は一括成長を前提としており、プローブシーケンスは合計グループ数に依存しているため、分割が困難です。
Goの組み込みマップは、各マップを複数のSwiss Tableに分割することで、この問題を間接的に解決しています。単一のSwiss Tableがマップ全体を実装するのではなく、各マップはキー空間のサブセットをカバーする1つ以上の独立したテーブルで構成されます。個々のテーブルは最大1024エントリを格納します。ハッシュの上位ビットの可変数が、キーが属するテーブルを選択するために使用されます。これは、テーブルの総数を区別するために必要に応じて使用されるビット数が増加する拡張可能ハッシュの一種です。
挿入中に個々のテーブルが拡張する必要がある場合、それは一括で行われますが、他のテーブルには影響しません。したがって、単一の挿入の上限は、1024エントリのテーブルを2つの1024エントリのテーブルに拡張し、1024エントリをコピーする遅延です。
イテレーション中の変更
AbseilのSwiss Tablesを含む多くのハッシュテーブルの設計では、イテレーション中のマップの変更を禁止しています。Go言語仕様は、以下のセマンティクスでイテレーション中の変更を明示的に許可しています。
- エントリが到達する前に削除された場合、それは生成されません。
- エントリが到達する前に更新された場合、更新された値が生成されます。
- 新しいエントリが追加された場合、それは生成されることもされないこともあります。
ハッシュテーブルのイテレーションの典型的なアプローチは、単にバッキング配列を歩いて、メモリに配置されている順序で値を生成することです。このアプローチは上記のセマンティクスと矛盾します。最も顕著なのは、挿入によってマップが拡張され、メモリレイアウトがシャッフルされる可能性があるためです。
イテレータが現在イテレーションしているテーブルへの参照を保持することで、拡張中のシャッフルの影響を避けることができます。イテレーション中にそのテーブルが拡張された場合でも、古いバージョンのテーブルを使い続け、したがって古いメモリレイアウトの順序でキーを提供し続けます。
これは上記のセマンティクスで機能しますか？拡張後に新しく追加されたエントリは、拡張されたテーブルにのみ追加され、古いテーブルには追加されないため、完全に失われます。これは問題ありません。セマンティクスが新しいエントリが生成されないことを許可しているためです。ただし、更新と削除は問題です。古いテーブルを使用すると、古いまたは削除されたエントリが生成される可能性があります。
このエッジケースは、古いテーブルをイテレーション順序を決定するためだけに使うことで対処されます。実際のエントリを返す前に、拡張されたテーブルを参照して、エントリがまだ存在するかどうか、そして最新の値を取得します。
これで主要なセマンティクスはすべて網羅されていますが、ここではカバーされていないさらに小さなエッジケースもあります。結局のところ、Goマップのイテレーションに対する寛容さの結果、イテレーションはGoのマップ実装の中で最も複雑な部分になっています。
今後の作業
マイクロベンチマークでは、マップ操作はGo 1.23と比較して最大60%高速化されています。正確なパフォーマンス向上は、マップの操作と使用法の多様性によりかなり異なります。また、一部のエッジケースではGo 1.23と比較してパフォーマンスが低下することもあります。全体として、完全なアプリケーションベンチマークでは、CPU時間の幾何平均で約1.5%の改善が見られました。
将来のGoリリースに向けて、さらに調査したいマップの改善点があります。例えば、CPUキャッシュにないマップでの操作の局所性を高めることができるかもしれません。
制御ワードの比較もさらに改善できる可能性があります。上記で説明したように、標準的な算術演算とビット演算を使用したポータブルな実装があります。しかし、一部のアーキテクチャには、この種の比較を直接実行するSIMD命令があります。Go 1.24はすでにamd64向けに8バイトのSIMD命令を使用していますが、他のアーキテクチャにもサポートを拡張できます。さらに重要なことに、標準命令が最大8バイトのワードで動作するのに対し、SIMD命令はほぼ常に少なくとも16バイトのワードをサポートしています。これは、グループサイズを16スロットに増やし、8回のハッシュ比較の代わりに16回のハッシュ比較を並行して実行できることを意味します。これにより、検索に必要な平均プローブ数がさらに減少します。
謝辞
Swiss TableベースのGoマップ実装は長い時間をかけて開発され、多くの貢献者によって支えられました。Go Swiss Table実装の初期バージョンを構築してくれたYunHao Zhang (@zhangyunhao116)、PJ Malloy (@thepudds)、そして@andy-wm-arthurに感謝します。Peter Mattis (@petermattis)は、これらのアイデアと上記のGoの課題に対する解決策を組み合わせて、Go仕様に準拠したSwiss Table実装であるgithub.com/cockroachdb/swissを構築しました。Go 1.24の組み込みマップ実装は、ピーターの作業に大きく基づいています。貢献してくださったコミュニティの皆さんに感謝します！