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

aoさんの発表

/icons/hr.icon

Go1.23以下のmap

基本的なオープンアドレスハッシュテーブル

線形探索をする

クラスタリングを避けるために、オーバーフローが起こる前にバッキング配列が拡張される

サイズが大きくなってくると、埋まっているスロット場所が偏り（これをクラスタリングと呼ぶ）、線形探索の効率を悪くさせる可能性が高いため。しかし、サイズが大きなると探索効率は悪くなる

拡張時にリハッシュ（スロットの再配置）されるのでキャッシュ効率が悪い

Go1.24からのmap

オープンアドレスハッシュテーブルの一種だが、効率の良いSwiss Tablesが使用されている

Go 1.23と比較して最大60%高速化

単一のバッキング配列はそのままだが、この配列を8スロットずつのグループに分割している（グループサイズを大きくすることも可能）

さらに各グループにはメタデータ用の64ビットのControl Wordが割り当てられる

Control Wordは上位57ビット（h1と呼ばれる）と下位7ビット（h2と呼ばれる）2つの部分に分割される

構造イメージは下記

code:mmd

code:mmd

graph TD

既にキーが含まれているスロットがあるかどうかを確認する必要がある

この時、Control Wordのh2を使用することで、SIMDのサポートする演算（単一の命令を複数のデータに対して行う並列演算）が実行される

従来では線形探索を行われていたが、並列に探索できるようになったので検索と挿入が高速化される

Group探索時にQuadratic probingを使用することでクラスタリング発生を軽減させている

code:text

↓Groupイメージ

↑ 探索が飛び飛び → 分散が保たれる

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のマップ実装の中で最も複雑な部分となっていることを示しています。

かなり難しいので、ここではまとめない。詳しくは下記を参照

/icons/hr.icon

資料