Golangのマップ：Swiss Tablesが古いバケット設計をどのように置き換えたか

Golangのマップ：Swiss Tablesが古いバケット設計を置き換えた方法 2026年7月24日（金）•チュートリアル golang ランタイム内部 データ構造 パフォーマンス はじめに マップは、ほとんどの非自明なGoプログラムのホットパス上に位置しています。リクエストルーティング、キャッシュルックアップ、重複排除セット、集計パイプライン、そして遅くなるまでほとんど気づかない多くのグルーコードを支えています。それらは非常に一般的であるため、マップの動作におけるランタイムレベルのわずかな改善でさえ、実際のシステム全体で測定可能な効果を生み出すことができます。 Go 1.24は、長年にわたるマップ内部の最大の変更の1つをリリースしました。従来のバケットプラスオーバーフローの実装は、Swiss Tableにインスパイアされた設計に置き換えられました。外部APIは変更されておらず、コードはこれまで通りmap[K]Vと書き、make、インデックス作成、delete、rangeを同じように呼び出します。しかし、内部では、ルックアップと挿入パスが、よりタイトなメタデータ、フラットなプロービングパターン、そしてはるかに優れたキャッシュ局所性に合わせて再構築されました。 その実質的な効果は単純です。ポインタ追跡の削減、キャッシュミスの減少、より高い有用なロードファクター、そして多くのワークロードでの一般的な操作の高速化です。マイクロベンチマークでは劇的な効果が見られることがありますが、フルアプリケーションでは通常、より小さいながらも依然として意味のある全体的な勝利が見られます。メモリの動作も多くのシナリオで改善され、特に古いオーバーフローチェーンが蓄積していた場所では顕著です。 この記事では、Goのランタイム設計で具体的に何が変更され、なぜその選択が重要なのか、そしてトレードオフが依然としてどこに現れるのかに焦点を当てます。最初にハッシュテーブルの概念的な復習が必要な場合は、Hash Map Deep Diveを参照してください。 Goの古いマップ実装（1.24より前） Go 1.24より前、マップは長年洗練されてきたバケット設計を使用していました。これは幅広いワークロードでうまく機能していました。各マップはバケットの配列を所有していました。各バケットは最大8つのキー/値ペアと、マッチングを高速化しスロットの状態を追跡するために使用されるメタデータを保持していました。バケットがいっぱいになると、ランタイムはオーバーフローバケットを割り当て、それを元のバケットにチェーンしました。高レベルで見ると、レイアウトは次のようでした。 キーのアイデアはシンプルで実用的でした。キーをハッシュし、ハッシュの一部を使用してバケットを選択し、そのバケットのエントリをスキャンします。一致するキーが見つからず、オーバーフローバケットが存在する場合、キーが見つかるかチェーンが終わるまでチェーンをたどります。簡略化された形式では、コア構造はおおよそ次のようでした。 // コンセプト上の形状であり、正確なランタイムソースではありません。 type hmap struct { // マップヘッダー count int B uint8 // バケットの数は 1<<B です buckets *bmap oldbuckets *bmap // 成長中の前のバケット配列 } type bmap struct { // 8つのスロットを持つバケット tophash [8]uint8 keys [8]K values [8]V overflow *bmap } この設計には実際の強みがありました。安定しており、実証済みで、段階的な成長をサポートしていたため、リサイズ作業は一度の大きなレイテンシスパイクとして現れませんでした。成長中、マップは一時的に古いバケット配列と新しいバケット配列の両方を保持し、マップがアクセスされるにつれて、操作は古いバケットを徐々に新しい位置に退避させていました。 主なコストは、プレッシャー下でのメモリ局所性でした。オーバーフローチェーンはポインタ追跡を導入し、ポインタ追跡はキャッシュミスを意味します。ホットなバケットがオーバーフローにスピルし始めると、ルックアップと挿入は非連続的なメモリを飛び回る可能性がありました。実装には、成長圧力が衝突コストを無視できなくなる前に、約81パーセント（おおよそ8スロットバケットあたり6.5個の埋められたスロット）という実用的なロードファクター制限もありました。 したがって、古いマップは置き換えを待つ壊れた設計ではなく、現代のCPU、キャッシュの動作、高スループットサービスがよりタイトでフラットなプローブパスを要求するにつれて、そのトレードオフがより顕著になった効果的な実装でした。 Swiss Tables：コア設計 歴史的に、Swiss TablesはGoogleのハッシュテーブルに関する社内パフォーマンス作業から生まれ、後にAbseil（GoogleのオープンソースC++ライブラリコレクション）を通じてflat_hash_mapおよび関連コンテナとして文書化され、オープンソース化されました。設計ノートは、モデルとそのトレードオフに関する最良の一次参照資料であり続けています。 Swiss Tablesは同じ高レベルのハッシュテーブル契約を維持しますが、データパスを2つのアイデアを中心に再編成します。コンパクトなスロットごとのメタデータと、プローブに優しい連続したグループです。この設計は、一般的なプローブ作業をはるかにキャッシュ効率の高いパスに移行させるため、その後、いくつかのランタイムやデータベースで採用されています。 最初に理解すべきことは、Swiss Tablesは完全なキーを読み取ることからプローブを開始しないということです。それらは、バルクでスキャンするのが安価なメタデータバイトを読み取ることから開始します。候補のみが完全なキー比較に進みます。これは小さく聞こえますが、CPU時間の使い道を変えます。 ハッシュの分割：配置用の一部、フィルタリング用の一部 キーは一度ハッシュされ、2つの論理的な部分に分割されます。 h1：初期グループインデックスの選択に使用されます。 h2：スロットごとのメタデータに格納される短いフィンガープリントです。 h2は高速な事前チェックと考えることができます。スロットのフィンガープリントが一致しない場合、そのスロットのキーバイトに触れる理由はありません。ほとんどのプローブは、このメタデータ段階で多くのスロットを拒否することになり、これは完全なキーを繰り返しロードして比較するよりもはるかに安価です。 グループ指向のレイアウト Swiss Tablesは、各スロットを独立したユニットとして扱うのではなく、スロットを固定サイズのグループに編成します。Goの設計では、そのグループサイズは8スロットであり、これはコンパクトなメタデータ処理と実用的なキャッシュの動作に一致します。各グループは以下を格納します。 - コントロールワード（スロットあたり1バイトのメタデータ、まとめてパックされています） - 8つのキーのスロット - 8つの値のスロット 概念的には次のようになります。 グループ i: ctrl: [c0 c1 c2 c3 c4 c5 c6 c7] keys: [k0 k1 k2 k3 k4 k5 k6 k7] vals: [v0 v1 v2 v3 v4 v5 v6 v7] コントロールバイトはスロットの状態（空、削除済み、占有済み）をエンコードし、占有済みスロットの場合はh2フィンガープリントビットを含みます。それらの8つのコントロールバイトは連続しているため、ランタイムは1つのタイトな操作でグループのすべてスロットの状態を検査できます。 プローブシーケンス：まずフィルタリング、次にキー比較 ルックアップは2段階のループになります。 1. 現在のグループのコントロールバイトを読み取ります。 2. フィンガープリントがh2と一致するコントロールバイトの位置を見つけます。 3. その位置のみについて、実際のキーを比較します。 4. 一致しない場合、プローブシーケンスの次のグループに進みます。 5. 空のスロットがキーが存在しないことを証明するまで停止します。 簡略化された擬似コード： g = startGroup(h1) for { matches = matchFingerprint(ctrl[g], h2) for each pos in matches { if keys[g][pos] == key { return vals[g][pos] } } if hasEmpty(ctrl[g]) { return not found } g = nextGroup(g) } hasEmpty(ctrl[g])チェックが重要です。オープンアドレス指定では、空のスロットはプローブを終了できることを意味します。もしキーがこのシーケンスに沿って挿入されていた場合、プローブはその最初の真に空のスロットに遭遇する前にそれを見つけていたはずです。 挿入と削除済みスロットの役割 挿入は、ルックアップと同じプローブパスを使用しますが、最初に見つかった再利用可能な位置を追跡します。再利用可能とは、ポリシーとプローブの進行状況に応じて、空のスロットまたは削除済みスロット（トムストーン）のいずれかを意味します。ルックアップがキーを見つけられない場合、挿入はこれまでに見つかった最良の再利用可能なスロットに書き込みます。これにより、プローブの不変性を維持しつつ、制御不能なクラスターの成長を制限します。 削除は通常、クラスターをすぐにコンパクト化しません。代わりに、メタデータを削除済みとしてマークします。即時のコンパクト化は、個々の削除をコストのかかるものにし、プローブの連続性の保証を壊す可能性があります。トレードオフは、トムストーンが多すぎると将来のプローブが長くなる可能性があるため、実装では成長または再編成フェーズ中にクリーンアップ動作が必要になることです。 なぜこれが現代のCPUによく適合するのか Swiss Tablesはしばしば「SIMDフレンドリー」と説明されますが、より広範なポイントは局所性と分岐動作です。 - 連続したメタデータスキャン：グループのコントロールバイトはまとめて読み取られ、散発的なメモリタッチを減らします。 - 完全なキーロードの削減：ほとんどのスロットがフィンガープリント段階で失敗するため、キー比較はまばらです。 - 予測可能なホットループ：プローブステップはシンプルで反復的であり、分岐予測に役立ちます。 - 改善されたキャッシュレジデンシー：メタデータと近くのスロットは、キャッシュラインを優先するようにパックされています。 アーキテクチャ固有のベクトル命令を使用しない場合でも、マップが現実的な本番サイズに達すると、この形状はポインタを多用するトラバーサルよりもパフォーマンスが高くなる傾向があります。 ロードファクターと実用的な考慮事項 Swiss Tablesは、より高いロードファクターを許容します。Goの新しい実装では、最大90パーセント（8スロットバケットあたり約7.2個の要素）まで効率的に使用できます。これは、古い設計の81パーセントよりも大幅な改善です。 しかし、この改善にはトレードオフが伴います。Swiss Tablesは、特に挿入と削除のコストに関して、古い設計よりもわずかに高いオーバーヘッドを持つ可能性があります。また、削除されたスロット（トムストーン）が蓄積すると、プローブの長さが増加する可能性があります。このため、Goのランタイムは、マップが成長する際や、定期的な内部再編成中に、これらのトムストーンをクリーンアップするメカニズムを組み込んでいます。 結論 Go 1.24のマップ実装の変更は、パフォーマンスとメモリ使用量における大きな進歩です。Swiss Tableの設計を採用することで、Goは現代のハードウェアの特性をより良く活用し、開発者が意識することなく、より高速で効率的なマップ操作を提供できるようになりました。この変更は、Goのランタイムの継続的な進化と、パフォーマンスへのコミットメントを示すものです。