【ITニュース解説】Swiss Tables the superior performance hashmap

システム開発において、データを効率よく管理することは非常に重要である。その中でも「ハッシュマップ」は、キー（鍵）と値（データ）をペアにして保存し、キーを使って素早く値を取り出すための基本的なデータ構造である。多くのプログラマーは、ハッシュマップの内部がどのように動いているかを深く知らなくても、get("キー")やset("キー", 値)といった基本的な操作で利用できる。しかし、内部の仕組みを理解することで、より高性能なアプリケーションを開発するための重要な知識が得られる。

最近、Go言語がデフォルトのハッシュマップ実装を、従来の「バケット方式」から「Swiss Tables」という新しい方式に変更したことは、そのパフォーマンスの重要性を示す事例の一つである。これは、既に高いパフォーマンスで知られるRust言語のハッシュマップに近づけることを目的としており、実際にいくつかの企業では、この変更によって数百ギガバイトものメモリを節約できたと報告されている。このSwiss Tablesは、プロトコルバッファやgRPCといった技術を生み出したGoogleの一部のエンジニアによって開発されたもので、既存の技術をさらに改良し、性能を高めることを常に追求していることがわかる。

従来のオープンアドレス方式のハッシュマップは、キーと値のペアを一つの大きな配列に直接保存する。新しいデータを挿入する際、まずキーをハッシュ関数に通して、そのハッシュ値に基づいてデータを格納する「スロット」の場所を決定する。もしそのスロットが既に埋まっていた場合、隣の空いているスロットを探す、という動作を繰り返す。この方式自体に根本的な問題があるわけではないが、特定のシナリオ、例えばたくさんのデータが衝突して密集している場合、あるデータを見つけるために配列の半分近くを順番に辿る必要が出てくることがある。これは検索に時間がかかり、システムの応答速度を低下させる原因となる。

Swiss Tablesは、この従来の課題を解決するために「メタデータ配列」という画期的なアイデアを導入した。これは、メインのデータ配列とは別に、各スロットの状態を記録する専用の配列である。メインデータ配列の各スロットに対して、対応する1バイトのメタデータが存在する。この1バイトは単にスロットが「空」か「使用中」かを示すだけでなく、もっと多くの情報を持っている。最も重要なのは、そのスロットに格納されているキーのハッシュ値の最後の7ビットを保存している点である。

このメタデータ配列の存在が、Swiss Tablesを高速化する大きな要因である。なぜなら、特定のキーがどこにあるかを検索する際、メインのデータ配列に実際にアクセスする前に、まずこのメタデータ配列をチェックできるからである。これにより、目的のキーが格納されている可能性のあるスロットを素早く特定し、無駄なデータアクセスを大幅に削減できる。これは、パフォーマンスにとって非常に大きなメリットとなる。

Swiss Tablesにキーと値を挿入する際の具体的な手順を見てみよう。まず、挿入したいキーを強力なハッシュ関数に通し、64ビットの長いハッシュ値を得る。Swiss Tablesは、このハッシュ値を二つの部分に分割する。一つは57ビットの「h1」、もう一つは最後の7ビットの「h2」である。h1の部分は、ハッシュマップ全体をいくつかの「グループ」または「バケット」に分割するための情報として使われ、どの初期グループにデータが属するかを決定する。h2の部分は「プローブインデックス」と呼ばれ、そのグループ内のどのスロットから検索や挿入を開始するかを示す。もし目的のスロットにすでに同じキーが存在すれば値を更新し、なければ空いているスロットを探す。もし現在のグループ内の全てのスロットが埋まっていた場合は、次のグループへと探索範囲を広げる。

次に、キーに対応する値を取り出す「検索」の動作を見てみる。検索時も同様に、まずキーをハッシュ関数に通し、h1（57ビット）とh2（7ビット）に分割する。h1を使ってデータの属するグループを特定し、h2を使ってそのグループ内のどのブロック（通常は16スロットのまとまり）から探索を開始するかを特定する。ここでSwiss Tablesの魔法が始まる。CPUは、検索対象のキーから得られた7ビットのハッシュスニペット（h2）を特別なレジスタに読み込む。そして、この値と、ターゲットとなるブロック内の8または16個のメタデータバイトを同時に比較する。これはSIMD（Single Instruction, Multiple Data）と呼ばれるCPUの命令セットを使うことで実現され、文字通り並行して多数の比較を行う。CPUは各メタデータバイトに対して、「このスロットは使われているか？」と「このスロットの7ビットハッシュスニペットは、探しているキーの7ビットハッシュスニペットと一致するか？」という二つのチェックを同時に行う。これにより、一致する可能性のあるスロットの候補をビットマスクとして非常に高速に生成する。

もちろん、7ビットのハッシュスニペットが一致したからといって、キー全体が一致するとは限らない。これはあくまで「プリフィルター」であり、高速に候補を絞り込むためのものである。もし複数の候補（例えばスロット2と9）が見つかった場合、初めてメインのデータ配列にアクセスし、それらのスロットに格納されているキーと、探しているキーの「完全な比較」を行う。この完全なキー比較は比較的コストの高い処理だが、SIMDによる事前フィルタリングのおかげで、その回数をわずか数回に抑えることができる。もしキーが完全に一致すれば対応する値を返し、一致するものが一つも見つからなかった場合、Swiss Tablesは非常に高速に「このキーはマップに存在しない」と判断する。特にキーが存在しない場合の検索速度は、長い探索シーケンスを辿る必要のある従来のハッシュマップと比較して圧倒的に優位である。

Swiss Tablesがこれほど高速である理由は、主に現代のCPUの並列処理能力を最大限に活用している点にある。従来のCPUは一つずつデータを処理していたが、最近のCPUはSIMD命令を使うことで、複数のデータに対して同じ操作を同時に実行できる。Swiss Tablesは、スロットを16個のブロックとして扱い、このSIMD命令を使って、16個のメタデータバイトを同時に比較する。これにより、一回の高速なCPU操作で、キーが格納されている可能性のあるスロットのビットマスクを生成できる。そして、実際にメインのデータ配列にアクセスするのは、このビットマスクで「可能性あり」と示されたスロットのみである。これは、高コストなメモリアクセスを最小限に抑え、CPUの並列処理能力を有効活用する、まさに「キラー機能」である。その結果、特にキーの検索、そしてキーが見つからない場合の検索が非常に高速になる。これは、データ構造の効率を示す「Big O記法」で表されるパフォーマンスにも大きな影響を与える。

このSwiss Tablesのアーキテクチャは、単なる理論的なアイデアにとどまらない。実際のアプリケーションにおいて具体的な利点をもたらし、処理時間を劇的に短縮する。例えば、0.0004秒かかっていた処理が0.00002秒に短縮されるような変化である。Go言語の公式発表によると、従来のバケット実装と比較してパフォーマンスが約63%向上したとされている。具体的な利点は以下の通りである。

第一に、圧倒的に高速な検索である。メタデータによる事前フィルタリングとSIMDの組み合わせにより、find()やcontains()といった検索および存在確認の操作が、従来のハッシュマップに比べて格段に速くなる。これはベンチマークにおいても顕著な差として現れる。 第二に、非常に効率的なメモリ使用である。Swiss Tablesは、キーと値を別々に割り当てられたノードとしてではなく、配列に直接格納する「フラット」な構造で実装されることが多い。これにより、CPUの高速なキャッシュ（L1、L2、L3キャッシュなど）にデータがより多く載りやすくなり、いわゆる「キャッシュ局所性」が向上する。また、ポインタを使って要素を連結する方式に比べて、ポインタ自体のメモリオーバーヘッドも回避できるため、全体としてメモリ使用効率に優れている。 第三に、より賢いリサイズ処理である。メタデータ配列が存在することで、ハッシュマップは内部の制御ロジックをより賢く行えるようになる。データが増えた際に、いつハッシュマップのサイズを変更（リハッシュ）し、どのように要素を再配置するかをより適切に判断できるため、データ量が増えてもパフォーマンスをより一貫して維持できる。

しかし、Swiss Tablesも全てが完璧というわけではない。どのような技術にもトレードオフが存在する。主な欠点としては、メタデータ配列のために追加のメモリが必要になる点が挙げられる。これはメインデータ配列の約1/16から1/8程度の量になるが、多くの場合、このわずかなメモリ消費は、得られるパフォーマンス向上と比較して非常に良いトレードオフであるとされている。現代においてメモリは比較的手に入れやすいリソースの一つだからだ。また、内部の実装が非常に複雑であるという欠点もあるが、これはハッシュマップを利用する側のプログラマーには直接関係しない。これまでと同様に、意識することなくその高性能な恩恵を受けられる。