メインコンテンツまでスキップ

ハッシュテーブルの最適化：ハッシュコードを隠す

· 約7分
[Sathya Gunasekaran](https://twitter.com/_gsathya)、ハッシュコードの管理者

ECMAScript 2015 は、Map、Set、WeakSet、WeakMap といった複数の新しいデータ構造を導入しました。これらはいずれも、内部的にハッシュテーブルを使用しています。この投稿では、最近の改善点と V8 v6.3+ がどのようにしてハッシュテーブルにキーを格納するかを詳しく解説します。

ハッシュコード​

ハッシュ関数 は、与えられたキーをハッシュテーブル内の位置にマッピングするために使用されます。ハッシュコード は、このハッシュ関数を与えられたキーに対して実行した結果です。

V8 において、ハッシュコードは単なる乱数であり、オブジェクトの値とは無関係です。このため、再計算ができず、格納する必要があります。

以前は、キーとして使用された JavaScript オブジェクトのハッシュコードは、そのオブジェクトの非公開シンボルとして格納されていました。V8 の非公開シンボルは、Symbol に似ていますが、列挙可能ではなく、ユーザー空間の JavaScript に漏洩しません。

function GetObjectHash(key) {
  let hash = key[hashCodeSymbol];
  if (IS_UNDEFINED(hash)) {
    hash = (MathRandom() * 0x40000000) | 0;
    if (hash === 0) hash = 1;
    key[hashCodeSymbol] = hash;
  }
  return hash;
}

この方法は、オブジェクトがハッシュテーブルに追加された時点で、新しい非公開シンボルをオブジェクトに格納するためのメモリを予約する必要がないという点で効果的でした。

また、V8 は IC システムを使用して他のプロパティ検索と同様にハッシュコードシンボルの検索を最適化できたため、非常に高速な検索が可能でした。これは、モノモーフィック IC 検索 で、キーが同じ 隠しクラス を持つ場合にうまく機能します。しかし、実際のコードではこのパターンに従わないことが多く、キーが異なる隠しクラスを持つことが多いため、メガモーフィック IC 検索 が遅くなります。

非公開シンボルアプローチのもう一つの問題は、ハッシュコードを格納する際にキーの 隠しクラスの遷移 を引き起こすことでした。これにより、ハッシュコード検索だけでなく、キーの他のプロパティ検索や、最適化されたコードの 最適化解除 にも悪影響を及ぼしました。

JavaScript オブジェクトのバックストア​

V8 における JavaScript オブジェクト（JSObject）は、（ヘッダ以外に）2つの単語を使用します。一つは要素バックストアのポインタを格納するため、もう一つはプロパティバックストアのポインタを格納するためのものです。

要素バックストアは 配列インデックス のように見えるプロパティを格納するために使用され、プロパティバックストアはキーが文字列またはシンボルであるプロパティを格納するために使用されます。これらのバックストアについての詳細は、Camillo Bruni によるこの V8 ブログ記事 を参照してください。

const x = {};
x[1] = 'bar';      // ← 要素に格納
x['foo'] = 'bar';  // ← プロパティに格納

ハッシュコードを隠す​

ハッシュコードを格納する最も簡単な解決策は、JavaScript オブジェクトのサイズを1単語分拡張し、ハッシュコードを直接オブジェクトに格納することです。しかし、この方法では、ハッシュテーブルに追加されないオブジェクトに対してメモリが無駄になります。代わりに、要素ストアまたはプロパティストアにハッシュコードを格納する方法を検討します。

要素バックストアは、その長さとすべての要素を含む配列です。ここではあまり手の施しようがありません。例えば、予約スロット（インデックス 0 など）にハッシュコードを格納する場合でも、オブジェクトをハッシュキーとして使用しない場合にはメモリが無駄になります。

プロパティバックストアを見てみましょう。プロパティバックストアとして使用されるデータ構造には、配列と辞書の2種類があります。

要素バックストアで使用される配列とは異なり、プロパティバックストアで使用される配列には 1022 個の値という上限があります。この制限を超えると、パフォーマンス上の理由から辞書に移行します。（若干簡略化していますが、V8 は他のケースでも辞書を使用する場合があります。ただし、配列に格納できる値の数には固定の上限があります。）

したがって、プロパティバックストアには次の3つの可能な状態があります：

  1. 空（プロパティがない）
  2. 配列（1022 個までの値を格納可能）
  3. 辞書

それぞれについて説明しましょう。

プロパティの裏ストアが空の場合​

空のケースでは、JSObjectのこのオフセットに直接ハッシュコードを保存できます。

プロパティの裏ストアが配列の場合​

V8では、231未満の整数（32ビットシステム上）が Smi としてアンボックス形式で表されます。Smiでは、最下位ビットはポインタとの識別のためのタグとして使用され、残りの31ビットが実際の整数値を保持します。

通常、配列はその長さをSmiとして保存します。この配列の最大容量が1022であることが分かっているので、長さを保存するためにはわずか10ビットしか必要ありません。残りの21ビットをハッシュコードの保存に使用できます！

プロパティの裏ストアが辞書の場合​

辞書の場合、辞書のサイズを1ワード増やして、辞書の先頭にある専用スロットにハッシュコードを保存します。この場合、メモリの1ワードを無駄にする可能性がありますが、配列の場合のような比例的なサイズ増加はそれほど大きくありません。

これらの変更により、ハッシュコードの検索が複雑なJavaScriptプロパティ検索プロセスを介する必要がなくなります。

パフォーマンスの向上​

SixSpeed ベンチマークはMapとSetの性能を追跡しますが、これらの変更により約500%の改善が見られました。

この変更により、ARES6 のBasicベンチマークにおいても5%の改善が見られました。

さらに、Ember.jsをテストする Emberperf ベンチマークスイートのあるベンチマークにおいても18%の改善が見られました。