Go マップの内部動作と Go 1.24 での実装変更：Swiss Tables

Go 1.24 でランタイム実装が大きく変更されました。この記事では、新しい「スイス式テーブル（Swiss Tables）」に基づくマップの内部構造と動作について、視覚的かつ段階的に解説します。

ランタイムでのマップとは何か

make

m := make(map[string]int)

• map[string]int

  は言語レベルの型であり、キーに文字列、値に整数を使用することを示します。
• 実際には、

  m

  は

  internal/runtime/maps.Map

  構造体へのポインタを指しています。

マップ構造体の内部フィールド

type Map struct {
	used uint64
	seed uintptr
	...
}

used

len(m)

seed

注意: これらのフィールドは、実際のキー・バリューエントリ自体を指すものではありません。

グループ (Group)

最も小さいストレージ単位はグループです。

• 最大 8 組のキー・バリューペアを格納します（1 つのグループ内）。
• 各スロットに対応する コントロールバイト（Control Byte） を持つ配列を含みます。

コントロールバイトとハッシュ値 (H2)

Go はキーをハッシュ化し、結果を以下のように分割します（64 ビットターゲットの場合）：

• H1: 上位 57 ビット → 検索開始位置のテーブル選択に使用
• H2: 下位 7 ビット → グループ内でのスロット探索に使用

コントロールバイトの構成例（8ビット）：

0

H2

cow

00101010

1

10000000

1

11111110

スロットの探索プロセス

1. キー

   "cow"

   を追加する際、Go はハッシュから H2 = 42 を取得します。
2. グループ内の全 8 バイトを同時に比較（SIMD 命令を使用）し、一致する候補スロットを特定します。
3. ヒットしたスロットに対して完全なキーの等価チェック（

   ==

   ）を行います。

テーブル (Table)

グループ単体のストレージが満杯（通常はアクティブエントリ/空スロット比など）になった場合、マップは成長しテーブルに切り替わります。

• 最初のテーブルは 2 つのグループ（合計 16 スロット）を持ちます。
• ストレージ単位が大きくなったため、再分配が必要です。

再分配と開始位置の決定 (H1)

既存のエントリを新しいグループへ移す際、Go はハッシュ値の H1 を使用します。

$$ \text{Starting Group} = \text{H1} % \text{Number of Groups} $$

• グループ数が 2 の場合（

  % 2

  ）、H1 の最下位ビットのみで十分です。
• 一部のキーはグループ 0、一部はグループ 1 に移されます。

三角探索シーケンス (Triangular Probe Sequence)

再分配後の「新しい」空きスロットが見つからない場合（全埋め）、Go は三角探索シーケンスを用いて空きスロットを探します。

• ステップ: 開始位置から +1, +2, +3... と広げるようにグループを順番にチェックします。
• 特徴: グループ数が 2 の累乗（例：4, 8, 16）なので、探索前に全グループを一度だけ正確に訪れることができます。

ディレクトリ (Directory)

グループ単体のマップからテーブル backed マップへ移行すると、ストレージアクセスの仕組みが変化します。

• dirPtr

  はグループを直接指さなくなり、ディレクトリエントリ配列へのポインタになります。
• ディレクトリは、ハッシュ値 H1 の上位ビット（左端） を使用して適切なテーブルを選択する役割を持ちます。

テーブルの分割と成長

• 最大 128 グループ（1024 スロット）まで成長可能ですが、その限界に達した際もさらに成長すると分割が発生します。
• ロードファクター制限: テーブルは完全に満杯になるのを待たず、7/8 (87.5%) 程度の使用率で再構築されます（削除済みスロットを含む計算）。

ディレクトリの深さ

ディレクトリがテーブルの分割に対応し続けるために、ハッシュビット数の概念を導入します。

• GlobalDepth: ディレクトリ全体を指すための H1 の上位ビット数。
• LocalDepth: 個別のテーブルを特定するための H1 の上位ビット数。

重要: テーブルが分割されても、既存の他のテーブルは再構築せず、ディレクトリの深さ（ビット数）を増やすことで指し示すだけとなります。

Go 1.24 で何が変化したか

Go 1.23 以前の古い実装との比較です。

旧実装（バケットとオーバーフローチェーン）

• バケットが満杯になると、追加の「オーバーフローバケット」を連結していました。
• チェーンが長くなるほどポインタ読み込みのコストが増大します。

新しい実装（Swiss Tables）

• すべてのグループを 1 つの配列に割り当てています。
• オバーフローではなく、三角探索シーケンスで空きスロットを見つけます。
• 成長戦略: 全マップを再構築するのではなく、選択されたテーブルのみを再構築します。

性能影響

• マップ関連の操作は、特定のカテゴリで最大 60% 高速化。
• アプリケーション全体のベンチマークでは CPU 時間に対して約 1.5% の改善。

バONUS: 削除処理について

「空」と「削除済み（Tombstone）」の違いが検索コストに大きく影響します。

• 小規模なマップでは、削除後は自動的に「空」になります。
• 大規模なマップ（テーブル backed）では、空きがない場合のみ「削除済み」としてマークされます。

なぜロードファクターなのか？

Go はなぜ 100% まで埋める代わりに、7/8 (87.5%) の制限を設けるのでしょうか？

• 探索コストの削減: テーブルがほぼ満杯だと、空のスロットを見つけるのが困難になります。
• 三角探索の影響: 空のスロットは探索を早期に中断させますが、それが「必要なキー」を含むグループでなければ無駄なチェックになります。
• Abseil の採用: Go は Google のライブラリ Abseil が採用している Swiss Tables の仕様（7/8 の限界）を採用しています。

分裂型グループレイアウト（The split group layout）

Go 1.27 で実験的導入された、さらなるメモリ効率化のレイアウトです（

GOEXPERIMENT=mapsplitgroup

従来のレイアウト

• キーと値をペアにして格納。
• 末尾に値がない場合、パディングにより無駄なメモリを消費。

type slot struct {
	key   Key
	elem  Elem
}

分裂型レイアウト（Split Layout）

• キー配列と値配列を分離して格納。
• キー検索時に一致すれば初めて値配列にアクセスする。
• メモリ効率化：グループあたり約 56 バイトの節約が可能になります。

type group struct {
	ctrl uint64
	keys [8]Key
	elem [8]Elem
}

リソース

より詳細な情報が必要な場合は以下のドキュメントを参照してください。

• Go 仕様:

  Map types

• Go Blog: "Faster Go maps with Swiss Tables"
• Abseil: Swiss Tables Design Notes
• Source Code:

  runtime/maps