HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Golang Maps: how Swiss Tables replaced the old bucket design (blog.gaborkoos.com)

22 pointsby Terretta3 コメント

要約

Go 1.24で導入されたマップ実装の大きな変更点について解説しています。従来のバケットとオーバーフローの設計から、Swiss Tableにインスパイアされた新しい設計に移行したことで、パフォーマンスとメモリ効率が向上しました。この変更は、マップの内部構造に焦点を当て、その利点とトレードオフを説明しています。

全文翻訳

Golangのマップ:Swiss Tableが古いバケット設計に取って代わった方法

はじめに

マップは、ほとんどの nontrivial な 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 つのキー/値ペアと、マッチングを高速化しスロットの状態を追跡するために使用されるメタデータを保持していました。バケットがいっぱいになると、ランタイムはオーバーフローバケットを割り当て、それを元のバケットにチェーンしました。

高レベルで見ると、レイアウトは次のようでした。

[画像: Diagram: pre-1.24 map layout with buckets, 8 slots per bucket, and overflow chains]

このアイデアはシンプルで実用的でした。キーをハッシュし、ハッシュの一部を使用してバケットを選択し、そのバケットのエントリをスキャンします。一致するキーが見つからず、オーバーフローバケットが存在する場合、キーが見つかるかチェーンが終了するまでチェーンをたどり続けます。

簡略化された形式で、コア構造はほぼ次のようでした。

// Conceptual shape, not the exact runtime source.
type hmap struct {   // map header
	count      int
	B          uint8   // number of buckets is 1<<B
	buckets    *bmap
	oldbuckets *bmap   // previous bucket array during growth
}

type bmap struct {   // bucket with 8 slots
	tophash  [8]uint8
	keys     [8]K
	values   [8]V
	overflow *bmap
}

この設計には実際の強みがありました。安定しており、実証済みで、段階的な成長をサポートしていたため、リサイズ作業が1回の大きなレイテンシスパイクとして現れることはありませんでした。成長中、マップはしばらくの間、古いバケットと新しいバケット配列の両方を保持し、マップがアクセスされるにつれて、操作は古いバケットを新しい位置に徐々に退避させていました。

主なコストは、プレッシャー下でのメモリ局所性でした。オーバーフローチェーンはポインタの追跡を導入し、ポインタの追跡はキャッシュミスを意味します。ホットなバケットがオーバーフローにスピルし始めると、ルックアップと挿入は非連続なメモリを横断する可能性がありました。また、この実装には、成長のプレッシャーと衝突コストが無視できなくなる前に、実用的なロードファクターの制限(約 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 つの値スロット

概念的には次のようになります。

group 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つのタイトな操作でグループのすべてスロットの状態を検査できます。

[画像: Diagram: Swiss Table group with control bytes, key slots, value slots, and slot-state metadata]

プローブシーケンス:まずフィルタリング、次にキー比較

ルックアップは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)
}

[画像: Diagram: probe sequence where h2 matches filter candidate slots before full key comparison]

hasEmpty(ctrl[g]) チェックが重要です。オープンアドレス方式では、空のスロットはプローブを終了できることを意味します。もしキーがこのシーケンスに沿って挿入されていた場合、プローブはその最初の真に空のスロットに遭遇する前にそれを見つけるはずです。

挿入と削除済みスロットの役割

挿入は、ルックアップと同じプローブパスに従いますが、最初に見つかった再利用可能な位置を追跡します。再利用可能とは、ポリシーとプローブの進行状況に応じて、空のスロットまたは削除済みスロット(トゥームストーン)のいずれかを意味します。

ルックアップがキーを見つけられなかった場合、挿入はこれまでに見つかった最良の再利用可能なスロットに書き込みます。これにより、プローブの不変性が維持され、制御不能なクラスターの成長が制限されます。

削除は通常、クラスターをすぐにコンパクト化しません。代わりに、メタデータを削除済みとしてマークします。即時のコンパクト化は、単一の削除をコストのかかるものにし、プローブの連続性の保証を壊す可能性があります。トレードオフとして、トゥームストーンが多すぎると将来のプローブが長くなる可能性があるため、実装では成長または再編成フェーズ中にクリーンアップ動作が必要です。

なぜこれが最新の CPU に適しているのか

Swiss Tables は「SIMD フレンドリー」とよく説明されますが、より広い点は局所性と分岐動作です。

  • 連続したメタデータスキャン: グループのコントロールバイトはまとめて読み取られ、メモリへの散発的なアクセスが減少します。
  • 完全なキーロードの減少: ほとんどのスロットはフィンガープリント段階で失敗するため、キー比較はまばらです。
  • 予測可能なホットループ: プローブステップはシンプルで反復的であり、分岐予測に役立ちます。
  • キャッシュレジデンシーの向上: メタデータと近くのスロットは、キャッシュラインを優先するようにパックされています。

アーキテクチャ固有のベクトル命令がなくても、マップが現実的な本番サイズに達すると、この形状はポインタを多用するトラバーサルよりもパフォーマンスが高くなる傾向があります。

ロードファクターと実用的な上限

古いバケット・オーバーフローモデルは、比較的早期にオーバーフロー成長のコストをバランスさせる必要がありました。Swiss スタイルのオープンアドレス方式は、プローブ作業が主にコンパクトなメタデータと近くのスロットに対する線形スキャンであるため、パフォーマンスが急激に低下する前に、より高密度な占有率を許容します。

実際には、これは有用なロードファクターを 80% 台後半(8 スロットグループ設計ではしばしば 87.5% 周辺で議論される)に押し上げます。正確な閾値は実装依存ですが、重要な結果は一貫しています。ルックアップと挿入が高価になりすぎる前に、より高密度のテーブルが可能になります。

より高い使用可能な密度は、格納されるエントリあたりのメモリオーバーヘッドが少なくなり、同じ数の要素に対する成長イベントが少なくなることを意味します。これら両方の効果が、ヒーププロファイルと割り当て率に直接現れます。

トレードオフは消えない

Swiss Tables は、あらゆるコーナーケースで普遍的に高速というわけではありません。高いトゥームストーン密度や特定の削除が多いパターンでは、クリーンアップまたは成長がテーブルの品質を回復するまで、プローブ長が後退する可能性があります。極端に敵対的なハッシュ分布は、強力なメタデータフィルタリングがあっても、依然としてあらゆるオープンアドレス方式の設計に悪影響を与えます。

改善は、すべての困難なケースを排除することではなく、一般的なケースをはるかにキャッシュ効率の高いパスに移行させることから来ています。

だからこそ、このシフトは Go にとって非常に重要です。マップはどこでも使用されており、一般的なケースがほとんどの CPU サイクルの消費場所だからです。

Go 固有の適応

もしこれが単なる Abseil スタイルの Swiss Tables の直接的な移植であれば、ランタイムの作業はもっと簡単だったでしょう。しかし、Go のマップには、言語の動作、GC との統合、そしてレイテンシとイテレーションに関する長年の期待からくる制約があります。Go 1.24 の興味深い点は、Swiss スタイルのプローブを採用しただけでなく、それらの制約が依然として満たされるように適応させたことです。

長時間停止型スパイクなしの成長

従来のオープンアドレス方式のテーブルは、より大きなテーブルを割り当て、すべてを1回の大きな移行ステップで再挿入することによってリサイズされることがよくあります。これは一部のシステムでは問題ありませんが、Go のマップはホットなリクエストパスで使用され、単一操作のレイテンシが重要です。フルテーブルの再ハッシュを時折実行するリサイズ戦略は、ランタイムが避けようとするまさにその種のロングテールを作成する可能性があります。

Go の適応は、作業をより小さな単位に分散することで、このモノリシックなジャンプを回避します。マップを一度に倍増して完全に再ハッシュする巨大なテーブルとして扱うのではなく、ランタイムは拡張が段階的に行われるように作業を分割できます。運用上、これにより、単一の挿入が既存のすべての要素を移動する完全なコストを継承する可能性が低くなるため、変更コストがより安定します。

実質的な効果は、古いマップの段階的な退避モデルの精神に似ています。成長は依然として発生しますが、移行作業は1回の高コストイベントに集中するのではなく、通常の操作に償却されます。

複数の独立したテーブルとディレクトリスタイルのルーティング

Go 固有の重要な選択の1つは、単一の常に成長するモノリスではなく、複数の小さな Swiss スタイルのテーブルとしてストレージを編成することです。より高レベルのディレクトリ(概念的には拡張ハッシュに似ています)がキーを特定のテーブルセグメントにルーティングし、プレッシャー下にあるセグメントのみが分割する必要があります。

成長をローカルに保つことは、ホットなキー領域がグローバルな再構築を強制することなく拡張できることを意味し、メモリ移動を分割セグメントに限定することで、書き込み負荷の高いバースト下でのレイテンシ予測可能性が向上します。

概念レベルでは、挿入は次のようになります。

hash key
use high bits to select table segment
probe within that segment's Swiss groups
if segment exceeds thresholds, split that segment and update directory

そのディレクトリの更新は、すべてのセグメントを再構築するよりもはるかに低コストであり、Go の段階的なランタイム作業の好みとよく組み合わさります。

テーブルが変更されている間も Go の range セマンティクスを維持する

最も困難な制約の1つは、挿入、削除、および成長が発生している間も、Go のマップイテレーションの動作を維持することです。

Go では、マップに対する range を使用したイテレーションは、意図的に緩い順序保証を持っていますが、安全性と一貫性の期待は依然としてあります。ランタイムは、破損した状態を公開したり、言語ルール下でまだ表示されるべきエントリへの到達可能性を失ったり、リロケーションメカニズムがイテレータの正確性を侵害したりすることはできません。

セグメント化された Swiss スタイルのストレージでは、これはイテレータがセグメントの分割や内部プローブレイアウトの変更に伴ってエントリが移動する可能性があることを理解する必要があることを意味します。したがって、ランタイムはイテレーション状態をマップ内部のバージョン管理とトラバーサルメタデータに結合するため、構造が進化している間でもイテレータは安全に続行できます。

実装の詳細は複雑ですが、ユーザーが見える結果は単純です。for k, v := range m は、ランタイムが内部でキャッシュ局所性を向上させ、ストレージをより密にする間も機能し続けます。

GC およびライトバリアへの親和性

Go はテーブルエントリを純粋な機械的なバイトとして扱うことはできません。キーと値にはポインタが含まれる可能性があり、ポインタの移動はガベージコレクションとライトバリアと相互作用します。マップ内部の再設計は、挿入、削除、成長、およびイテレータ遷移中に正確なポインタの可視性とバリアの動作を維持する必要があります。

セグメント化された成長もここで役立ちます。より小さなリロケーションステップは、バリア付き書き込みとの統合が容易になり、単一のポインタ移動操作のサイズを縮小します。これは複雑さをなくすわけではありませんが、影響範囲を狭め、ランタイムのブックキーピングをより管理しやすくします。

Swiss スタイルのメタデータプローブは生のアルゴリズム的な勝利をもたらしますが、Go 固有の適応 — セグメント化された成長、イテレータ安全な移行、および GC バリアの統合 — が、ガベージコレクションされ、レイテンシに敏感なランタイムで大規模にその勝利を利用可能にしています。次のセクションのパフォーマンス数値は、両方のレイヤーが連携して機能していることを反映しています。

(それらの適応の背後にあるコードレベルのルール、三角形プローブシーケンスとトゥームストーン不変性から拡張ハッシュ成長ステップまで、import chaos newsletter のコンパニオンDirector's Cut にあります。)

パフォーマンスとメモリ分析(詳細)

マップベンチマークで誤解されやすい最も簡単な方法は、単一の合成テストのみを見て、その数値が直接本番に適用されると仮定することです。Go の Swiss マップの場合、公開データはよりニュアンスのある物語を語っています。マイクロレベルの勝利は現実的でしばしば大きく、アプリケーションレベルの全体的な勝利は小さいですが依然として肯定的であり、いくつかのワークロード形状は注意に値するほど後退します。

Go 1.24 の公式リリースノートによると、新しい Swiss マップの実装を含むランタイム作業は、代表的なベンチマークスイート全体で平均して CPU オーバーヘッドを約 2~3% 低減しました(Go 1.24 release notes, Runtime section)。これはランタイム全体での数値であり、マップのみの数値ではありませんが、混合ワークロード全体で測定されているため、現実確認として役立ちます。

マップ中心の結果については、ランタイムチームからの最も具体的な要約は、Michael Pratt の Swiss マップ追跡問題への最後のコメントにあります。大規模マップへのアクセスと代入は約 30~35% 高速化し、イテレーションは全体で約 10%、低負荷の大規模マップでは最大約 60% 高速化したと報告されています。一方、Sweet でのフルアプリケーションベンチマークでは、約 1.5% の幾何平均スピードアップが見られました(golang/go#54766 comment, Sweet benchmark suite)。

「ここで 30%」と「あそこで 1.5%」のギャップは、まさに期待すべきことです。マイクロベンチマークはマップ操作を分離し、コードパスをホットに保ち、しばしば一度に1つの操作タイプを強調します。実際のサービスは、解析、システムコール、RPC境界、スケジューリング、GCアシスト、およびマップ以外の多数のコードパスで時間を費やすため、マップの勝利は、マップがプロファイルを支配しない限り希釈されます。

ベンチマーク設計自体が効果を誇張したりマスクしたりする証拠もあります。マップベンチマークの品質に関するフォローアップの問題で、Go チームは分岐予測子に優しいキーパターン、2のべき乗のマップサイズ、およびベンチマークハーネスのオーバーヘッドを歪みとして指摘し、ベンチマーク構造を変更すると観測された差が大幅に変化することを示しました(golang/go#70700)。これらのフォローアップからの具体的なデータポイントの1つは、予測不可能なキーに対する小規模マップのルックアップ修正が、同じベンチマークセットでヒットレイテンシを約 1.7 倍(投稿された数値で約 25ns から約 14ns へ)、ミスも約 1.3 倍改善したことです(CL 634396 summary in #70700)。

メモリに関しては、2つの事実が公開ソースによってよく裏付けられています。第一に、Swiss スタイルのプローブは、古いオーバーフローチェーン設計よりも高い実用的な占有率で実行でき、多くの場合、エントリあたりのオーバーヘッドを削減する傾向があります(Abseil Swiss table design, golang/go#54766)。第二に、Go の初期の公開 Swiss マップベンチマークの要約では、広範ですがワークロード依存の範囲でメモリ削減が報告されており、ほとんどの場合 0~25% と記述され、特に固定サイズのマップを再利用する際に余分な割り当てを回避することについての注記がありました(performance summary in #54766)。

しかし、注意すべき側面も同様に重要です。Go チームとユーザーは、1.24 のロールアウト後、特にコールドキャッシュの動作やスパースな大規模マップのパターンに関して、いくつかの後退またはエッジケースを追跡しました。コールドキャッシュの追跡問題は、ディレクトリの間接参照と複数の割り当てがミスコストを増加させる理由を説明しており、その問題を目指したレイアウト実験について議論しています(golang/go#70835)。そのスレッドでの Prometheus ベンチマークからの具体的な外部レポートは、このワークロード形状において Go 1.24.2 が 1.23 よりも runtime.mapaccess1_fast64 の CPU 時間が高いことを示しており、これはまさに幾何平均の後ろに隠れる可能性のあるプロファイル固有の動作です(Prometheus report in #70835)。

大規模容量のスパースマップでの clear(m) も、非一様な動作の別の例です。問題の議論では、クリアのコストが一部のパターンで割り当てられたテーブルサイズに比例する場合があり、ランタイムの貢献者は緩和策と、空のグループでの不要な作業をスキップする関連する CL について議論しています(golang/go#70617)。言い換えれば、Swiss マップは多くのパスを改善しましたが、初日からすべての病的なコーナーケースをなくしたわけではありません。

実用的な解釈は単純です。あなたのサービスが中規模から大規模なマップでルックアップまたは挿入中心である場合、Go 1.24 以降はおそらく無料のスピードアップと、しばしばより良いメモリ効率を提供します。あなたのプロファイルがコールドミス、非常にスパースな巨大マップ、またはタイトなクリア/再利用ループによって支配されている場合、あなたのワークロードで直接測定し、ランタイムの継続的な作業を監視する必要があります。なぜなら、それらは解決された歴史ではなく、アクティブな最適化領域だからです。

Go 開発者向けの実際的なテイクアウェイ

新しい実装がどこでその利点を獲得するのかを理解することは、より良いプロファイリングの決定を下し、マップフレンドリーなパターンを書き、1.24 以降へのアップグレードがあなたの特定のサービスに実際に何をもたらすのかを調整するのに役立ちます。

最も影響が見られる場所

マップが実際のボトルネックである場合に、利点は最大になります。頻繁にアクセスされる大規模マップが最も明確なケースです。マップにポインタ追跡とキャッシュミスのコストを古い実装で露呈させるのに十分なエントリがあると、ルックアップと挿入は最も顕著に高速化します。大規模なインメモリ検索テーブル、構造化された識別子をキーとするキャッシュ、または多数のシャード化されたマップに対する同時アクセスパターンを維持するサービスは、すべて測定可能な恩恵を受けることができます。

大規模だが疎に人口が少ないマップのイテレーションも大幅に改善されます。古い設計では、占有率に関係なくすべてのバケットをウォークする必要がありましたが、Swiss スタイルのコントロールバイトメタデータにより、ランタイムは空のグループを迅速にスキップできます。コードが range を使用して大きなマップをスキャンまたはドレインする場合、そのパスは高速化します。

メモリ制約のあるサービスも測定する価値のあるケースです。より高いロードファクターとオーバーフローバケットチェーンの排除は、マップストレージからのヒーププレッシャーを削減でき、それが GC の頻度を減らし、全体的なヒープ効率を改善できます。

利点が最も小さいのは、非常に小さいマップ(数個のキー)、コールドアクセスが支配的なマップ、または小さな整数および文字列キーのランタイムの高速パスの特殊化をエスケープしないマップです。それらのマップでは、新しい設計は中立であるか、一部のマイクロベンチマークで小さな後退を示す可能性があります。実際には、それらのマップがプロファイルでホットスポットとして表示されない場合、その違いはほとんど関連性がありません。

サービスでのマップ動作のプロファイリング

マップが CPU プロファイルに表示される場合、runtime.mapaccess1、runtime.mapassign、runtime.mapiterinit、および関連するシンボルが監視すべき関数です。それらのシンボルでの CPU 時間の大部分と、フラットまたはゆっくりと改善するヒープの組み合わせは、「Swiss テーブル以前」のパフォーマンスレジームにいるか、既知のコールドキャッシュエッジケースが影響している良い兆候です。

メモリについては、ヒーププロファイルでマップエントリがライブ割り当てに不釣り合いに寄与しているかどうかを確認できます。Go 1.24 以降は多くのワークロードでここで役立つはずですが、キーが削除された後も大規模なマップ割り当てが持続している場合、Go マップは削除後に割り当てられたバックストレージを縮小しないことを覚えておく価値があります。それは変わっていません。

マップがベンチマークまたは本番ワークロードに意味のある貢献をしているかどうかをプローブする簡単な方法は、Go 1.23 と 1.24 以降のビルド間で go tool pprof プロファイルを比較することです。ランタイムレベルのスピードアップは自動ですが、それを自身のコードで定量化することは、それを強調する価値があるか無視する価値があるかを教えてくれます。

削除パターンと clear イディオム

コードレベルで少し考える価値のあるパターンは、重い削除の使用です。ホットパスが多数のキーを繰り返し削除および再挿入するタイトなループである場合、各プローブグループ内のトゥームストーンパスを実行しています。Swiss スタイルのオープンアドレス方式はこれを正しく処理しますが、高いトゥームストーン密度では、成長中またはテーブル再編成ポイントでクリーンアップが発生するまでプローブが長くなります。これは他のオープンアドレス方式の設計にも存在するのと同じトレードオフであり、Go の実装はアプリケーションの関与なしにそれを管理しますが、削除が支配的なワークロードは純粋なルックアップまたは挿入ワークロードよりもメリットが少ない可能性があることを意味します。

マップをクリアして再利用するために使用される clear(m) イディオムは、注意すべき別の点です。Go マップはクリア時にバックストレージを縮小しないため、以前に大きくなったマップで clear を呼び出しても、そのメモリは解放されません。clear 自体のコストは、現在の設計で割り当てられたグループの数に比例しますが、かつては大きかったが現在はほとんどエントリを保持していないマップにとっては高価になる可能性があります。

// This pattern is fine and common.
// clear(m) resets map entries without releasing backing storage.
// If the map previously held many keys, the next iteration of inserts
// skips re-allocation, which is the intent.
m := make(map[string]int)
for {
    populate(m)
    process(m)
    clear(m)   // fast if m is consistently sized; more expensive if m grew large once
}

このパターンを、大きくなった後に縮小するマップで使用する場合、クリアされたマップの長期的なバックサイズが実際に適切かどうか、またはそれらのケースで新しいマップを作成する方が望ましいかどうかを検討してください。

ランタイムがまだ変更する可能性のあるもの

マップのコールドキャッシュ動作に関する継続的な作業があります。ランタイムの貢献者は、メモリレイアウトの変更を積極的に実験しており、グループ内でキーと値を分離すること(#70835 で追跡されている GOEXPERIMENT=mapsplitgroup 実験)も含まれています。コールドキャッシュの問題自体は Go 1.27 でも未解決です。これらはユーザーに公開される API 変更ではありませんが、マップのパフォーマンスプロファイルが進化し続けることを意味します。

Abseil の C++ 実装が x86 で使用している SIMD ベースのコントロールバイトスキャンは、現在 Go の Swiss マップパスには含まれていません。 CockroachDB swiss README で述べられているように、純粋な Go アセンブリで SIMD を使用してプローブループを実装することには、関数呼び出し境界からの非自明なオーバーヘッドがありますが、Go チームは代わりに SWAR (SIMD Within A Register) アプローチを採用しています。これは、Go のアセンブリモデルと CPU サポートが進化するにつれて、将来のバージョンで変更される可能性があります。

結論

Go 1.24 のマップ再設計は、よく踏みならされたコードでもまだ大きな改善が可能であることを明確に示しています。バケットとオーバーフローのモデルは長年 Go プログラムを確実にサポートしてきましたが、新規性からではなく、Swiss Table にインスパイアされたレイアウトが一般的なケースを実際に高速化し、メモリ効率を向上させ、本番スケールで機能するという蓄積された証拠から置き換えられました。

コア設計の選択、よりタイトなグループレベルのメタデータ、完全なキー比較前の高速な候補フィルタリング、およびフラットなプローブパスは、Abseil の Swiss Tables から直接来ています。Go が追加したのは、それらの選択を安全にし、ガベージコレクション、イテレータセマンティクス、およびレイテンシに敏感な成長と互換性があるようにするランタイムインフラストラクチャです。この2番目のレイヤーはあまり目立ちませんが、同様に重要です。

開発者にとって、この変更はほとんど透過的です。1.24 以降にアップグレードするだけで、改善を享受できます。ただし、マップが CPU プロファイルを支配しない限り、本番環境での全体的なゲインは控えめになる傾向があり、コールドアクセスパターンは特定の形状で後退する可能性があり、ランタイムチームはまだイテレーションを行っています。マイクロベンチマークの見出しから外挿するのではなく、実際のワークロードを測定してください。

Go は、慎重で検証されたエンジニアリングを通じて改善できるものとして、そのランタイムを扱い続けています。Swiss マップの作業はその規律の良い例です。提案、設計、実装、およびベンチマークにわたる数年間の取り組みが、最終的に言語の表面をまったく変更することなく出荷されました。