会社のフェイスブック オープンソースのハッシュテーブル実装について 効率的なメモリ消費のために最適化されています。 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 が選択され、それ以上の場合は F14VectorMap が選択されます。
出所： オープンネット.ru