会社のフェイスブック ハッシュテーブル実装のソースコード公開について 効率的なメモリ消費のために最適化されています。F14はFacebookのインフラストラクチャにおいて、ほとんどの種類のハッシュテーブルの代替として利用されており、パフォーマンスを損なうことなくメモリ消費を削減できます。F14は、これまでメモリ消費の点で最も効率的と考えられていたgoogle::sparse_hash_mapハッシュテーブルを大幅に上回ります。プロジェクトコードはC++で記述されており、ライブラリに含まれています。 .
F14は14の二重ハッシュ衝突解決アルゴリズムである。 （ハッシュテーブルの14つのセルには2個のスロットのチェーンが格納され、セル間の間隔は補助ハッシュ関数を用いて計算されます。）セルフィルタリング操作を高速化するために、実装ではx86_64システムではSSE64ベクター命令、Aarch14ではNEON命令が使用されています。これにより、キーチェーンを使用したスロット選択操作とチェーン内のキーフィルタリング操作を並列実行できます。XNUMXスロットのブロックが一度に処理されるため、プロセッサキャッシュの使用効率と衝突回数の間の最適なバランスが実現されます。
F14 の特別な機能は、さまざまなデータ ストレージ戦略を選択できることです。
- F14NodeMap - 大規模および中規模のキーに対してメモリ消費量が最も少ない。挿入のたびにmalloc関数を呼び出すことで、要素の間接的な保存場所を提供します。
- F14ValueMap — 小さなキーに対してメモリ消費を最小限に抑えます。要素はセル自体（インライン）に格納されます。中規模および大規模なキーの場合、このアプローチはメモリのオーバーヘッドを顕著に増加させます。
- F14VectorMap - 大きなテーブルや複雑なキーでは高速に動作しますが、単純なキーや小さなテーブルでは動作が遅くなります。要素は連続的に埋め込まれた配列にパックされ、32ビットのインデックスポインタによってアドレス指定されます。
- F14FastMapは複合的な戦略です。キーが24バイト未満の場合はF14ValueMapが選択され、14バイトを超える場合はFXNUMXVectorMapが選択されます。
出所： オープンネット.ru
