Swiss TableによるGoのマップの高速化

Faster Go maps with Swiss Tables by Michael Pratt

ハッシュテーブルはコンピュータサイエンスにおける中心的なデータ構造であり、Goを含む多くの言語でマップ型の実装を支えています。

ハッシュテーブルという概念は、1953年にHans Peter LuhnによるIBM社内メモの中で最初に説明されました。このメモでは、要素を「バケット」に入れ、バケットがすでに要素を持っている場合には連結リストであふれた分を扱うことで検索を高速化する方法が提案されていました。これは今日でいう「チェイン法によるハッシュテーブル」にあたります。

1954年には、Gene M. Amdahl、Elaine M. McGraw、Arthur L. SamuelがIBM 701のプログラミングにおいて初めて「オープンアドレス法」の仕組みを使いました。バケットがすでに要素を持っている場合、新しい要素は次の空いているバケットに置かれます。このアイデアは1957年にW. Wesley Petersonによって「Addressing for Random-Access Storage」という論文の中で定式化され発表されました。これは今日でいう「線形探査によるオープンアドレス法のハッシュテーブル」にあたります。

これほど昔からあるデータ構造については、もう「完成されて」いて、知るべきことはすべて知り尽くしており、これ以上改善のしようがないと考えがちです。しかし、それは間違いです。計算機科学の研究は、アルゴリズムの計算量という観点でも、現代のCPUハードウェアを活用するという観点でも、基本的なアルゴリズムの改良を今なお続けています。たとえば、Go 1.19では、sortパッケージが従来のクイックソートから、Orson R. L. Petersが2015年に初めて発表した新しいソートアルゴリズムであるpattern-defeating quicksortに切り替えられました。

ソートアルゴリズムと同様に、ハッシュテーブルというデータ構造にも改良が続けられています。2017年、GoogleのSam Benzaquen、Alkis Evlogimenos、Matt Kulukundis、Roman Perepelitsaは、「Swiss Tables」と名付けられた新しいC++のハッシュテーブル設計を発表しました。2018年には、その実装がAbseil C++ライブラリの中でオープンソース化されました。

Go 1.24には、Swiss Tableの設計に基づいた、組み込みのマップ型に対する完全に新しい実装が含まれています。この記事では、Swiss Tableが従来のハッシュテーブルからどのように改良されているかを見ていき、さらにSwiss Tableの設計をGoのマップに導入する際に直面した独自の課題についても取り上げます。

オープンアドレス法のハッシュテーブル

Swiss Tableはオープンアドレス法によるハッシュテーブルの一形態なので、まずは基本的なオープンアドレス法のハッシュテーブルがどのように動作するかを簡単に概観しておきましょう。

オープンアドレス法のハッシュテーブルでは、すべての要素が1つの配列（バッキング配列）に格納されます。この配列内の各位置を スロット と呼ぶことにします。あるキーがどのスロットに属するかは、主に ハッシュ関数 である hash(key) によって決まります。ハッシュ関数は各キーを整数に対応付けるもので、同じキーは常に同じ整数に対応付けられ、異なるキーは理想的には整数の一様ランダムな分布に従います。オープンアドレス法のハッシュテーブルを特徴づけているのは、衝突が起きたときにキーをバッキング配列内の別の場所に格納することで解決する点です。つまり、あるスロットがすでに埋まっている場合（これを 衝突 と呼びます）には、空いているスロットが見つかるまで プローブシーケンス を使って他のスロットを検討していきます。実際にサンプルのハッシュテーブルを見て、この仕組みを確認してみましょう。

例

以下は、ハッシュテーブルの16スロットからなるバッキング配列と、各スロットに格納されているキー（あれば）を示したものです。値についてはこの例には関係ないため表示していません。

新しいキーを挿入するには、ハッシュ関数を使って対象のスロットを選びます。スロットは16個しかないため、この範囲に収める必要があり、hash(key) % 16 を対象スロットとして使います。キー 98 を挿入したいとして、hash(98) % 16 = 7 だとします。スロット7は空いているので、そこに98をそのまま挿入します。一方、キー 25 を挿入したいとして、hash(25) % 16 = 3 だとします。スロット3はすでにキー56を持っているため衝突が発生します。したがってここには挿入できません。

そこで、別のスロットを見つけるためにプローブシーケンスを使います。よく知られたプローブシーケンスにはさまざまな種類があります。最も原始的で単純なプローブシーケンスは 線形探査 で、単純に後続のスロットを順番に試していくものです。

つまり、先ほどの hash(25) % 16 = 3 の例では、スロット3が使用中なので、次はスロット4を検討しますが、これも使用中です。スロット5も同様です。最終的に空いているスロット6にたどり着き、そこにキー25を格納します。

ルックアップも同じ考え方に従います。キー25のルックアップはスロット3から始まり、そこにキー25が入っているか確認し（入っていません）、その後線形探査を続けてスロット6でキー25を見つけます。

この例では16スロットのバッキング配列を使っています。では16個より多くの要素を挿入するとどうなるでしょうか。ハッシュテーブルの空きがなくなると、テーブルは拡張されます。通常はバッキング配列のサイズを倍にすることで行われます。既存のエントリはすべて新しいバッキング配列へ再挿入されます。

実際には、オープンアドレス法のハッシュテーブルはバッキング配列が完全に埋まるまで拡張を待つわけではありません。配列が埋まっていくにつれて、プローブシーケンスの平均的な長さが増えていくからです。先ほどのキー25の例では、空きスロットを見つけるために4つの異なるスロットをプローブする必要がありました。もし配列に空きスロットが1つしかなければ、最悪の場合のプローブ長はO(n)になってしまいます。つまり、配列全体を走査しなければならない可能性があるということです。使用済みスロットの割合は 負荷率 と呼ばれ、ほとんどのハッシュテーブルは 最大負荷率 （一般に70〜90%）を定めており、それに達すると、非常に埋まったハッシュテーブルにありがちな極端に長いプローブシーケンスを避けるために拡張を行います。

Swiss Table

Swiss Tableの設計もまた、オープンアドレス法のハッシュテーブルの一形態です。これが従来のオープンアドレス法のハッシュテーブルに対してどのように改良されているのかを見ていきましょう。ストレージとしては引き続き1つのバッキング配列を使いますが、この配列を8スロットずつの論理的な グループ に分割します。グループサイズをもっと大きくすることも可能で、これについては後述します。

さらに、各グループはメタデータ用に64ビットの 制御ワード を持ちます。制御ワード内の8バイトはそれぞれ、グループ内のいずれかのスロットに対応しています。各バイトの値は、そのスロットが空いているか、削除済みか、使用中かを表します。使用中の場合、そのバイトにはそのスロットのキーのハッシュの下位7ビット（h2 と呼ばれます）が格納されます。

（スロット0〜7がグループ0、スロット8〜15がグループ1に対応します。）

各グループの制御ワードは次のようになります。

挿入は次のように行われます。

1. hash(key) を計算し、そのハッシュを上位57ビット（h1 と呼ばれます）と下位7ビット（h2 と呼ばれます）の2つに分割します。
2. 上位ビット（h1）を使って最初に検討するグループを選びます。ここではグループが2つしかないので h1 % 2 を使います。
3. グループ内では、すべてのスロットが等しくそのキーを保持する候補になります。まず、いずれかのスロットにすでにこのキーが入っていないかを確認する必要があります。入っていれば、新規挿入ではなく更新ということになります。
4. どのスロットにもキーが入っていなければ、このキーを置くための空きスロットを探します。
5. 空いているスロットがなければ、次のグループを調べることでプローブシーケンスを続けます。

ルックアップも基本的に同じ手順に従います。手順4で空きスロットが見つかった場合、挿入が行われるとすればそのスロットが使われるはずだとわかるので、探索を打ち切れます。

Swiss Tableの魔法が起きるのは手順3です。グループ内のいずれかのスロットに目的のキーが入っているかどうかを確認する必要があります。素朴には、単純に線形スキャンをして8個のキーすべてを比較すればよいのですが、制御ワードを使えばもっと効率よくこれを行えます。各バイトにはそのスロットのハッシュの下位7ビット（h2）が入っています。制御ワードのどのバイトが探している h2 を持っているかを判定できれば、候補となる一致の集合が得られます。

言い換えると、制御ワード内でバイトごとの等価比較を行いたいということです。たとえば、キー32を探していて h2 = 89 である場合、行いたい演算は次のようになります。

これはSIMDハードウェアがサポートする演算で、1つの命令によって、より大きな値（ベクトル）内にある独立した値に対して並列に演算を行います。専用のSIMDハードウェアが利用できない場合には、この演算を標準的な算術演算とビット演算の組み合わせによって実装できます。

結果として得られるのは候補となるスロットの集合です。h2 が一致しないスロットには一致するキーが存在しないので読み飛ばせます。h2 が一致するスロットは一致している可能性がありますが、衝突の可能性がある（7ビットのハッシュなので衝突の確率は1/128ですが、それでもかなり低い値です）ため、それでもキー全体を確認する必要があります。

この演算は非常に強力です。プローブシーケンスの8ステップ分を実質的に一度に、並列に実行できるからです。これによって必要な比較の平均回数が減り、ルックアップと挿入が高速化されます。このプローブ動作の改善のおかげで、AbseilとGoの実装のいずれも、以前のマップと比べてSwiss Tableのマップの最大負荷率を引き上げられ、平均的なメモリ使用量を減らせました。

Goにおける課題

Goの組み込みマップ型には、新しいマップ設計を採用するうえでさらなる課題となるいくつかの独特な性質があります。中でも特に対処が難しかったのが次の2つです。

段階的な拡張

ハッシュテーブルが最大負荷率に達すると、バッキング配列を拡張する必要があります。典型的には、次の挿入で配列のサイズを倍にし、すべてのエントリを新しい配列にコピーすることになります。1GB分のエントリを持つマップに挿入する場合を考えてみましょう。ほとんどの挿入は非常に高速ですが、マップを1GBから2GBに拡張する必要のあるその1回の挿入では1GB分のエントリをコピーしなければならず、長い時間がかかってしまいます。

Goはレイテンシに敏感なサーバーでよく使われる言語なので、テールレイテンシに任意の大きさの影響を与えかねない組み込み型の操作は避けたいところです。そこでGoのマップは段階的に拡張されるようになっており、各挿入が行わなければならない拡張作業の量には上限が設けられています。これにより、単一のマップへの挿入によるレイテンシへの影響が抑えられます。

残念ながら、Abseil（C++）のSwiss Table設計は一括での拡張を前提としており、プローブシーケンスがグループの総数に依存しているため、これを分割するのは困難です。

Goの組み込みマップは、各マップを複数のSwiss Tableに分割するというもう一段階の間接参照を導入することでこの問題に対処しています。マップ全体を1つのSwiss Tableで実装するのではなく、各マップはキー空間の一部をそれぞれ担当する1つ以上の独立したテーブルから構成されます。1つのテーブルが保持できるエントリは最大1024個です。ハッシュの上位ビットのうち可変長のビット数を使って、あるキーがどのテーブルに属するかを選びます。これはエクステンダブルハッシュ法の一形態であり、テーブルの総数を区別するために必要に応じて使用するビット数が増えていきます。

挿入の際、個々のテーブルが拡張を必要とする場合には一括で拡張されますが、他のテーブルには影響しません。したがって、1回の挿入における上限は、1024エントリのテーブルを2つの1024エントリのテーブルへと拡張する、つまり1024エントリをコピーするのにかかるレイテンシということになります。

イテレーション中の変更

AbseilのSwiss Tableを含む多くのハッシュテーブル設計では、イテレーション中にマップを変更することを禁止しています。しかしGo言語仕様では、次のようなセマンティクスのもとでイテレーション中の変更が明示的に許可されています。

• あるエントリが処理される前に削除された場合、そのエントリは生成されません。
• あるエントリが処理される前に更新された場合、更新後の値が生成されます。
• 新しいエントリが追加された場合、それが生成されるかどうかは決まっていません。

ハッシュテーブルのイテレーションでよくある実装方法は、単純にバッキング配列を走査して、メモリ上のレイアウト順に値を生成するというものです。このやり方は上記のセマンティクスと衝突します。特に問題になるのは、挿入によってマップが拡張されると、メモリレイアウトがシャッフルされてしまう可能性があるという点です。

イテレータが現在イテレーションしているテーブルへの参照を保持するようにすれば、拡張時のシャッフルによる影響を避けられます。そのテーブルがイテレーション中に拡張された場合でも、古いバージョンのテーブルを使い続けることで、古いメモリレイアウトの順序のままキーを配信し続けられます。

これは上記のセマンティクスと矛盾しないでしょうか。拡張後に追加された新しいエントリは、拡張後のテーブルにしか追加されず古いテーブルには追加されないため、完全に見逃されることになります。これは問題ありません。セマンティクス上、新しいエントリが生成されなくてもよいことになっているからです。しかし、更新と削除は問題です。古いテーブルを使うと、古くなった値や削除済みのエントリが生成されてしまう可能性があります。

このエッジケースには、古いテーブルをイテレーションの順序を決めるためだけに使うことで対処しています。実際にエントリを返す前に、拡張後のテーブルを参照して、そのエントリがまだ存在するかどうかを確認し、最新の値を取得します。

これでコアとなるセマンティクスはすべてカバーされますが、ここで触れていない細かいエッジケースがさらにいくつか存在します。結局のところ、Goのマップがイテレーションに対して寛容であることが理由で、イテレーションはGoのマップ実装の中で最も複雑な部分になっています。

今後の課題

マイクロベンチマークでは、マップの操作がGo 1.23と比べて最大60%高速化しています。マップの操作や用途は非常に多岐にわたるため、正確な性能改善の度合いにはかなりのばらつきがあり、一部のエッジケースではGo 1.23と比べて性能が悪化することもあります。全体としては、アプリケーション全体のベンチマークにおいて、CPU時間の幾何平均でおよそ1.5%の改善が見られました。

今後のGoのリリースに向けて検討したいマップの改善点はまだあります。たとえば、CPUキャッシュに載っていないマップに対する操作の局所性を高められるかもしれません。

制御ワードの比較についても、さらに改善できる余地があります。前述の通り、標準的な算術演算とビット演算を使った移植性の高い実装を用意していますが、アーキテクチャによってはこの種の比較を直接行うSIMD命令を持っているものもあります。Go 1.24ではamd64向けにすでに8バイトのSIMD命令を使っていますが、これを他のアーキテクチャにも拡張できるかもしれません。さらに重要なこととして、標準的な命令は最大8バイトのワードしか扱えないのに対し、SIMD命令はほぼ常に少なくとも16バイトのワードをサポートしています。つまり、グループサイズを16スロットまで増やし、8個ではなく16個のハッシュ比較を並列に行えるようになる可能性があるということです。これにより、ルックアップに必要な平均プローブ回数をさらに減らせるでしょう。

謝辞

Swiss Tableに基づくGoのマップ実装は長らく待ち望まれていたもので、多くの貢献者が関わってきました。GoにおけるSwiss Table実装の初期バージョンを構築してくれたYunHao Zhang（@zhangyunhao116）、PJ Malloy（@thepudds）、そして@andy-wm-arthurに感謝します。Peter Mattis（@petermattis）は、これらのアイデアと上記のGo特有の課題への解決策を組み合わせ、Go仕様に準拠したSwiss Table実装であるgithub.com/cockroachdb/swissを構築しました。Go 1.24の組み込みマップ実装は、Peterの成果を大いに基にしています。貢献してくださったコミュニティの皆さんに感謝します!

By Michael Pratt