証券取引所から「注文の更新」が届いています。各注文 ID は 1 から 100 000 000 の間であるため、1 億の配列を使用して 1 億の注文を格納でき、更新を受信すると、 index でアクセスするだけで配列から非常に高速に注文を検索できますarrray[orderId]。数ギガバイトのメモリを消費しますが、これで問題ありません。
別の方法として、ハッシュマップを使用することもできます。いつでも「アクティブな」注文の数が制限されているため (非常に大まかに 100 000 まで)、ルックアップもかなり高速になりますが、おそらく配列よりも少し遅くなります。
問題は、hashmap が実際に遅くなるかどうかです。1億の配列を作成するのは合理的ですか?
レイテンシだけが必要です。メモリはまったく気にしません。何を選択すればよいですか?
パフォーマンスの問題を考えるとき、1 回の実験は 1,000 の専門家の意見に値します。試して！
そうは言っても、私は闇の中で大胆な突き刺しをします.マルチギガバイトアレイを物理メモリに常駐させるようにOSを納得させることができれば(これは必ずしも簡単ではありません-mlockとmunlocksyscallsを見ることを検討してください)、比較的優れたパフォーマンスが得られます。このようなパフォーマンスの向上 (存在する場合) は、ハッシュ関数のコストをバイパスし、ハッシュマップの実装が使用する衝突解決とメモリ割り当て戦略に関連するオーバーヘッドを回避することによる可能性があります。
また、多くのハッシュ テーブルの実装では、一部の操作の複雑さが一定ではないことに注意する必要があります (たとえば、個別の連鎖O(n)は最悪の場合に低下する可能性があります)。レイテンシを最適化しようとしている場合、OS メモリ マネージャーへの非常にアグレッシブなシグナル伝達を行う配列 (例:madviseおよびmlock) は、マイクロプロセッサで簡単に取得できる定数レイテンシ ルックアップに最も近い結果になる可能性があります。
この質問に客観的に答える唯一の方法はパフォーマンス テストですが、私はハッシュテーブル マップを使用することを主張します。(キャッシングとメモリアクセスは驚きに満ちています。私には、どちらがいつ速くなるかを推測する専門知識がありません。局所的なパフォーマンスの違いは、他のコードによって取り残される可能性があることも考慮してください。)
ハッシュを「最初に選択」する最初の理由は、100M の個別のキーがあり、アクティブなレコードは 0.1Mしかないという観察に基づいています。これは、配列を使用する場合、インデックスの使用率が 0.1% になることを意味します。これは非常にまばらな配列です。
データが配列に値として格納されている場合は、比較的小さくする必要があります。そうしないと、配列のサイズが膨らみます。データが配列に格納されていない場合(たとえば、配列がポインターの場合)、配列内のデータの局所性に関する議論は部分的に軽減されます。いずれにせよ、単純な配列アプローチでは、未使用のスペースが大量に必要になります。
すべてのキーはすでに整数であるため、分散 (ハッシュ) 関数を効率的に実装できます。複雑な型/シーケンスのハッシュを作成する必要がないため、この関数の「コスト」はゼロに近づくはずです。
だから、私の単純な提案されたハッシュ：
特定のケースに対して「最適化された」特別なハッシュテーブル ルールを提示しましたが、通常の Map 実装 (ハッシュテーブルまたはツリー) から始めて、それをテストします.. 標準実装が適切に機能する場合は、それを使用しないのはなぜですか?
次に、予想される極端な負荷の下でさまざまな候補をテストし、勝者を選びます。
これは、ID のクラスタリングに依存しているようです。
アクティブな ID がすでに適切にクラスター化されている場合、ハッシュを使用しなくても、OS や L2 キャッシュは適切なデータを保持し、低レイテンシーを維持することができます。
それらが完全にランダムである場合、アクティブなトランザクションの数が利用可能なキャッシュ ラインの数を超えるか、それらのトランザクションのサイズがキャッシュのサイズを超えるとすぐに問題が発生します (どちらが発生する可能性があるかは明確ではありません)。あなたの場合は最初に）。
ただし、アクティブな ID が競合率の高い不運なパターン (たとえば、さまざまな属性のビットパックであり、頻繁に変化する属性がハードウェアの障害となる) であることが判明した場合は、インデックスの 1:1 ハッシュを使用してランダム ケースに戻すと、通常はそれ自体がかなり悪いケースと見なされますが、利点があります。
圧縮のためのハッシュに関する限り。一部の人々は、ハッシュ衝突の最悪の場合のフォールバック動作を懸念していることに注意してください。これには、合理的に制約された最悪のケースがあるため、連続したメモリにフルサイズのテーブルのキャッシュを実装するだけで済みます。単純にマップ内で最も混雑しているエントリを保持し、競合が発生した場合はテーブル全体にフォールバックします。よりアクティブな場合は、他のエントリをマップに移動します (これを決定する適切なアルゴリズムが見つかった場合)。
それでも、必要なハッシュ テーブルのサイズが、ワーキング セットをキャッシュ可能に縮小するのに十分かどうかは明らかではありません。あなたの注文はどれくらいの大きさですか？
ハッシュマップと配列のオーバーヘッドはほとんどありません。間違いなく、100,000,000 の配列に対する 100,000 レコードのハッシュマップに賭けます。
また、「メモリを気にしない」一方で、これはメモリをバックアップする方がよいことも意味します.100,000,000個の整数の配列は、すべてが空であっても400MBを占有します. データがスワップアウトされるリスクがあります。データがスワップアウトされると、数桁のパフォーマンス ヒットが発生します。
他の人が言ったように、テストしてプロファイリングする必要があります。ただし、暗闇の中でのランダムな刺し傷: 高負荷係数のハッシュ テーブルがここに行く方法です。巨大な配列が 1 つあると、TLB ミスが発生し、アクセスごとに最終レベルのキャッシュ ミスが発生します。これは高価です。あなたが言及したワーキングセットのサイズを考えると、ハッシュテーブルはおそらくいくつかの算術演算とL1ミスを犠牲にするだけです。
繰り返しますが、代表的な例で両方の選択肢をテストしてください。私たちは皆、暗闇の中で突き刺しています。