Mokori's Notes

Go1.24で進化したmap型について理解する

Properties1
tagsconference, go

6 min read

aoさんの発表

Go1.23以下のmap

  • 基本的なオープンアドレスハッシュテーブル
    • 線形探索をする
    • クラスタリングを避けるために、オーバーフローが起こる前にバッキング配列が拡張される
      • サイズが大きくなってくると、埋まっているスロット場所が偏り（これをクラスタリングと呼ぶ）、線形探索の効率を悪くさせる可能性が高いため。しかし、サイズが大きなると探索効率は悪くなる
      • 拡張時にリハッシュ（スロットの再配置）されるのでキャッシュ効率が悪い

Go1.24からのmap

  • オープンアドレスハッシュテーブルの一種だが、効率の良いSwiss Tablesが使用されている
    • Go 1.23と比較して最大60%高速化
    • 単一のバッキング配列はそのままだが、この配列を8スロットずつのグループに分割している（グループサイズを大きくすることも可能）
    • さらに各グループにはメタデータ用の64ビットのControl Wordが割り当てられる
      • Control Wordは上位57ビット（h1と呼ばれる）と下位7ビット（h2と呼ばれる）2つの部分に分割される
    • 構造イメージは下記
 
graph TD
  MAP[Go Map]
  MAP --> DIR["Directory"]
 
  DIR --> T0["SwissTable 0"]
  DIR --> T1["SwissTable 1"]
 
  T0 --> G00["Group 0"]
  T0 --> G01["Group 1"]
 
  T1 --> G10["Group 0"]
  T1 --> G11["Group 1"]
 
  G00 --> S000["Slot 0\nkey: 'a'\nvalue: 1\nctrl: 0x12"]
  G00 --> S001["Slot 1\nkey: 'b'\nvalue: 2\nctrl: 0x34"]
 
  G01 --> S010["Slot 0\n(empty)"]
  G01 --> S011["Slot 1\n(empty)"]
 
  G10 --> S100["Slot 0\nkey: 'x'\nvalue: 9\nctrl: 0x21"]
  G10 --> S101["Slot 1\n(empty)"]
 
  G11 --> S110["Slot 0\n(empty)"]
  G11 --> S111["Slot 1\nkey: 'z'\nvalue: 99\nctrl: 0x78"]
  • 既にキーが含まれているスロットがあるかどうかを確認する必要がある
    • この時、Control Wordのh2を使用することで、SIMDのサポートする演算（単一の命令を複数のデータに対して行う並列演算）が実行される
      • 従来では線形探索を行われていたが、並列に探索できるようになったので検索と挿入が高速化される
  • Group探索時にQuadratic probingを使用することでクラスタリング発生を軽減させている
↓Groupイメージ
[ x ][  ][ x ][  ][ x ][  ][ x ]
↑ 探索が飛び飛び → 分散が保たれる

Goのチャレンジ

  • 新しいマップ設計を採用する際に追加の課題となる特殊な特性があった。特に扱いが難しいのが下記2つである

Incremental growth

  • ハッシュテーブルが最大負荷係数に達すると、基盤となるバッキング配列を拡張する必要がある
    • 通常、これは次の挿入処理で配列のサイズが2倍になり、すべてのエントリが新しい配列にコピーされることを意味する
    • 例えば、1GBのエントリを持つマップだと、ほとんどの挿入処理は非常に高速だが、マップを1GBから2GBに拡張する必要がある挿入では、1GBのエントリをリハッシュ（スロットの再配置）する必要があり、非常に時間がかかる
  • Abseil (C++) スイス テーブルの設計では、すべてが一度に成長することを想定しているので、プローブシーケンスはグループの合計数に依存し、分割が困難になる
  • 上記を解決するためにGoはマップを複数のスイステーブルに分割することで、別の間接層でこの問題に対処している
    • 単一のスイステーブルでマップ全体を実装するのではなく、1つ以上の独立したテーブルで構成されている
    • 個々のテーブルには最大1024個のエントリが格納される。keyのハッシュの上位ビットの可変数は、キーがどのテーブルに属するかを選択するために使用される。これはExtendible hashing（拡張可能なハッシュ）の一種であり、テーブルの総数を区別するためにテーブルが増えてくると必要に応じてビット数が増加する
  • 挿入中に個々のテーブルを拡張する必要がある場合、そのテーブルは一度に拡張されるが、他のテーブルは影響を受けない
    • 1回の挿入の上限は、1024エントリのテーブルを2つの1024エントリのテーブルに拡張し、1024エントリをコピーする

Modification during iteration

  • Go の map は イテレーション中の変更を公式に許可している
    • そのため、内部実装が非常に複雑

Goのマップにおける反復処理の許容度の高さは、反復処理がGoのマップ実装の中で最も複雑な部分となっていることを示しています。

資料

Graph View

Backlinks