10

数秒で多数のオブジェクトを保持するアプリケーションがありDictionary、そのうちのいくつかはアプリの有効期間中に継続的に成長します (多くの商品と継続的に成長する注文/取引を伴う取引アプリケーション)。

OutOfMemoryException大きなオブジェクト ヒープの断片化が原因で、s に問題が発生しています。

これに対抗するために、すべてのリーフ ディクショナリが LOH に割り当てられるほど大きくない 2 レベルのディクショナリとして実装される「大きな」ディクショナリを作成しようとしました。単一のバケットが大きくなりすぎたときに辞書全体を再ハッシュする必要がないように、一貫したハッシュ アルゴリズムを使用しました。コンシステント ハッシュ「サークル」はTreeDictionary、C5 コレクション ライブラリからのものです。

私の質問は、C# 用のより良いデータ構造 (または、おそらく私が説明したもののより良い実装) はありますか?

アップデート

これは「大きな」辞書の実装です: https://gist.github.com/956621

LOH ヒープのしきい値も、各ディクショナリ エントリまたはスケーリング アルゴリズムのサイズも仕様に含まれていないため、絶対確実ではないことは理解しています。ただし、これは現在、アプリケーションが日中に爆発するのを避けるために考えられる最善の方法です.

4

2 に答える 2

3

辞書は、アプリケーションで最大の辞書である場合、残念なデータ構造です。ハッシュテーブルがいっぱいになると、サイズが2倍になることがよくあります。そのため、サイズ変更中に、重要なタイミングで150％の割り当て超過が必要になります。ハッシュテーブルは、巨大な場合は十分に機能しますが、ヒープアルゴリズムにストレスを与える連続的な割り当てが必要です。

マルチレベルのハッシュテーブルを使用すると、これらの欠点を軽減できます。たとえば、ハッシュコードのバイトを256個のハッシュテーブルへのインデックスとして使用できます。これは確かにいくらかのオーバーヘッドを追加しますが、さらに重要なことに、この戦略や他の戦略は、取得するハッシュコードなどのランダム性をいじり、パフォーマンスを大幅に悪化させる可能性があるため、危険にさらされます。このアプローチを使用するには、優れた理論的基盤と確かな経験的テストが必要です。しかし、それは機能します。

もう1つの戦略は、最悪の場合に最大のデータ構造を事前に割り当て、それを早期に割り当てることです。きめ細かい割り当ては必要ありませんが、万が一不足した場合に壊滅的な障害が発生する可能性があります。それはオプションです。

于 2011-05-05T05:15:25.340 に答える
1

これにはアルゴリズムの変更が必要だと思います。

私が聞いて理解したことによると、GC はメモリのパッケージ化と最適化に非常に優れています。したがって、あなたの問題は、メモリに保存するデータが多すぎるという単純な事実に起因しています。

どのくらいのデータをメモリに保持しますか?

データベースの使用について考えたことはありますか？コンパクトなもので十分かもしれません。

または、アプリを正しく実行するには、16 GB のメモリが必要であることをクライアントに伝えるだけです。アプリが 16 GB のメモリをすべて必要とする場合は、間違いなく何か問題があります。

編集:あなたの問題を別の側面から見て、あなたの編集を読んだ後、私は質問を受けました:あなたのオブジェクトはどれくらいの大きさですか? それとも、長いリストや配列が含まれていますか? それらのオブジェクトをどのくらいの頻度で削除/追加しますか?

問題は辞書自体にあるのではないかもしれませんが、大きすぎて頻繁に削除/追加されるオブジェクトです。ある種のキャッチやプールを使用すると、利益が得られる場合があります。リストを使用する場合は、それらのリストを preallocated で作成します。

また、可変クラスの代わりに不変構造体を使用すると、断片化が緩和される可能性があります。

于 2011-05-05T04:58:45.587 に答える