2

したがって、Javolution が機能しないため (ここを参照)、単純な使用法で効率的でガベージを生成しない Java Map 実装が必要です。java.util.Mapキーを追加および削除すると、ガベージが生成されます。Trove と Guava を確認しましたが、 Set<E> 実装がないようです。のシンプルで効率的な代替手段はどこにありjava.util.Mapますか?

EJP の編集:

エントリ オブジェクトは、エントリを追加すると割り当てられ、削除すると GC に解放されます。:(

   void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
4

4 に答える 4

7

文字通り、キーの追加および削除時にガベージをまったく生成しない Map または Set の既存の実装を認識していません。

実際、技術的に可能である唯一の方法 (Java では、定義されているMapおよびSetAPI を使用) は、エントリ数に厳密な上限を設定することです。実用的な Map および Set の実装には、保持する要素の数に比例する追加の状態が必要です。この状態はどこかに保存する必要があり、現在の割り当てを超えた場合は、そのストレージを拡張する必要があります。Java では、新しいノードを割り当てる必要があることを意味します。

（わかりました、古い役に立たないノードを永久に保持するデータ構造クラスを設計したため、収集可能なガベージは生成されませんでしたが、それでもガベージが生成されています。）

では、実際にこれについて何ができるでしょうか...生成されるゴミの量を減らすために。HashMap例として見てみましょう：

  • エントリを削除すると、ガベージが作成されます。ハッシュ チェーンを、チェーン エントリを表すノードを解放しない実装に置き換えない限り、これは避けられません。（そして、それは悪い考えです...空きノードプールのサイズが常に小さいことを保証できない限り。それが悪い考えである理由については、以下を参照してください。）

  • メインのハッシュ配列のサイズが変更されると、ガベージが作成されます。これは、いくつかの方法で回避できます。

    • HashMap コンストラクターで 'capacity' 引数を指定して、最初のハッシュ配列のサイズを、サイズを変更する必要がない十分な大きさに設定できます。(しかし、それはスペースを無駄にする可能性があります...特に、 がどれだけ大きくなるかを正確に予測できない場合HashMap)。

    • 「負荷係数」引数にばかげた値を指定して、HashMap のサイズが決して変更されないようにすることができます。(しかし、その結果、ハッシュチェーンが制限されていない HashMap になり、O(N)ルックアップ、挿入、削除などの動作になります。

実際、ガベージを作成することは必ずしもパフォーマンスに悪いわけではありません。実際、ガベージ コレクターがノードを収集しないようにノードにハングアップすると、実際にはパフォーマンスが低下する可能性があります。

GC 実行のコスト (最新のコピー コレクターを想定) は、主に次の 3 つの領域にあります。

  • ガベージではないノードを見つける。
  • それらの非ガベージ ノードを「to-space」にコピーします。
  • 「to-space」内のオブジェクトを指すように、他の非ガベージ ノード内の参照を更新します。

(一時停止の少ないコレクターを使用している場合は、他のコストもかかります...一般に、ガベージ以外の量に比例します。)

ガベージの量に実際に依存する GC の作業の唯一の部分は、ガベージ オブジェクトがかつて占有していたメモリをゼロにして再利用できるようにすることです。そして、これは「from-space」全体に対する単一の呼び出しで実行できますbzero...または仮想メモリのトリックを使用します。

ガベージの作成を避けるために、アプリケーション/データ構造がノードにハングアップするとします。ここで、GC が実行されると、これらの余分なノードをすべてトラバースし、それらに有用な情報が含まれていなくても、それらを「to-space」にコピーするために余分な作業を行う必要があります。さらに、これらのノードはメモリを使用しています。つまり、アプリケーションの残りの部分がガベージを生成すると、ガベージを保持するスペースが少なくなり、GC をより頻繁に実行する必要があります。

また、弱/ソフト参照を使用して GC がデータ構造からノードを取り戻せるようにしている場合、それは GC にとってさらに多くの作業になります...そしてそれらの参照を表すスペース。

注: オブジェクト プーリングが常にパフォーマンスを低下させると主張しているわけではありません。特にプールが予想外に大きくなった場合は、パフォーマンスが低下することがよくあります。

そしてもちろん、それが HashMap や同様の汎用データ構造クラスがオブジェクト プーリングを行わない理由です。もしそうなら、プログラマーが予期していない状況でパフォーマンスが大幅に低下します...そして、本当に壊れてしまうでしょう、IMO.

最後に、HashMap を調整して、同じキーを追加した直後に削除してもガベージが生成されないようにする簡単な方法があります (保証されます)。「追加」された最後のエントリをキャッシュし、次のエントリが追加されたときにのみput実際に実行する Map クラスにラップします。HashMapもちろん、これは汎用ソリューションではありませんが、以前の質問のユースケースに対応しています。

于 2012-03-22T03:32:40.713 に答える
4

オープン アドレッシングを使用するバージョンの HashMap が必要だと思いますが、リニア プローブよりも優れたものが必要になるでしょう。とはいえ、具体的な推奨事項はわかりません。

于 2012-03-22T16:20:55.957 に答える
4

http://sourceforge.net/projects/high-scale-lib/には、キーの追加または削除時にガベージを作成しない Set および Map の実装があります。この実装では、キーと値が交互になる単一の配列を使用するため、put(k,v) は Entry オブジェクトを作成しません。

ここで、いくつかの注意事項があります。

  • Rehash はガベージ b/c を作成し、基になる配列を置き換えます
  • 全体のサイズが安定している場合でも、このマップは、十分にインターリーブされた put および delete 操作があれば再ハッシュされると思います。(墓石の値を収集するため)
  • エントリセットを要求すると、このマップは Entry オブジェクトを作成します (反復時に一度に 1 つずつ)。

クラスは NonBlockingHashMap と呼ばれます。

于 2012-03-23T08:10:20.063 に答える
0

1 つのオプションは、エントリのプールを使用するように HashMap 実装を修正することです。私はそれをしました。:)そこで実行できる速度の最適化は他にもあります。私はあなたに同意します.Javolution FastMapの問題は気が遠くなるようなものです. :(

于 2012-03-22T03:03:40.043 に答える