トーク Talk

Go 1.24では、mapの内部実装がSwiss Tableベースに変更されました。本セッションでは、この新しい実装を実際のソースコードとともに詳細に議論していきます。 Swiss Tableはグループ単位でのSIMD並列処理を活用したアプローチです。ハッシュ値をH1（上位57ビット）とH2（下位7ビット）に分割し、H2を使って8つのスロットを並列でマッチングする仕組みを、実際のコードを見ながら議論します。特にctrlGroup.matchH2メソッドでの興味深いビット操作テクニックには目を見張るものがあります。 https://github.com/golang/go/blob/53af292aed21c3f6ea75d16e5b25f660b2c028fb/src/internal/runtime/maps/group.go#L157-L172 Go特有の要件がどのように実装に反映されているかについても議論していきます。8要素以下の小さなmapでは、テーブル構造を使わずに単一グループで直接管理するSmall Map最適化、 https://github.com/golang/go/blob/53af292aed21c3f6ea75d16e5b25f660b2c028fb/src/internal/runtime/maps/map.go#L267-L283 マップが実際に使用されるまで領域確保を遅延する設計、XORによるトグルを使った並行アクセス検出など、 https://github.com/golang/go/blob/53af292aed21c3f6ea75d16e5b25f660b2c028fb/src/internal/runtime/maps/map.go#L489-L491 実用的な最適化が随所に見られます。また、Go言語仕様の「イテレーション中でもmap変更を許可する」というセマンティクスに対応するため、古いテーブルへの参照を保持し続ける複雑な実装についても詳しく解説します。 さらに、Extendible Hashingによる段階的成長戦略を取り上げます。map全体を一度に再構築するのではなく、個別のテーブルを分割して成長させることで、大きなmapでのパフォーマンス劣化を防ぐ設計です。globalDepthとlocalDepthを使ったディレクトリ管理の仕組みや、テーブル分割時の複雑な処理を、実際のinstallTableSplitメソッドを追いながら理解していきます。 https://github.com/golang/go/blob/53af292aed21c3f6ea75d16e5b25f660b2c028fb/src/internal/runtime/maps/map.go#L359-L391 本セッションを通じてSwiss Tableへの理解と、それがどのように実装されているかを知る機会を提供できたらと思います。