収集のオーバーヘッド

オブジェクトを格納するときに余分なメモリを消費するコレクションがいくつあるのかと思いまして。 同じタイプの要素（リストとセット）のストレージを含む一般的なコレクションのオーバーヘッド測定を実行し、結果を共通のスケジュールに減らしました。 64ビットHotspot JVM（Java 1.6）の画像を次に示します。





ただし、32ビットのホットスポットの場合：



以下では、どのように測定が行われたかを説明し、写真がそのように見える理由を理解してみます。

材料と方法

測定は、通常のJava配列だけでなく、java.utilおよびjava.util.concurrentからの標準Javaコレクションに対しても行われました。 IdentityHashSetおよびConcurrentHashSetコレクションは、Collections.newSetFromMap（）メソッドを使用して、対応するマップから作成されます。 すべてのコレクションは、最初に要素の数を指定せずにデフォルトで初期化され（必要な配列を除く）、その後、addメソッドを使用してテストオブジェクトで満たされました（そして、配列に対して割り当てが実行されました）。 1から10,000までの異なる数の要素を使用して、各タイプの約500のコレクションが作成されました。要素として、ランダムな文字で構成されるランダムな長さの10,000の異なる文字列が使用されました。 原則として、要素自体はConcurrentHashSetにのみ影響し、わずかでも影響を与えるため、グラフはどのデータでも同じように見えます。



配列を埋めた後、メモリダンプがプロセスから取得され、Eclipse Memory Analyzerを使用して分析されました。これにより、オブジェクト自体は含まれず、オーバーヘッドのみが含まれる各コレクションの保持セットが非常に正確に計算されました。 たとえば、次のようになります。



それでは、Excelにコピーし、簡単な数学演算と、グラフィカルエディターで少し追加の図面を使用してプロットします。

結果の議論

各コレクションは、オーバーヘッドコストの境界が低く、要素が多いほど、コレクションに近いことが多いことがわかります。 ただし、一部のコレクションでは、オーバーヘッド関数が数学的な意味でこの境界に収束するとは言えません。 たとえば、ArrayListは8バイト（64ビットの場合）になっていますが、新しいメモリが割り当てられるたびに12バイトにジャンプし続けます。



興味深いことに、32ビットと64ビットのグラフは非常に似ています。ほとんどのコレクションでは、ConcurrentSkipListSetとLinkedListの2つの例外を除いて、グラフが半分異なります。 各コレクションを個別に検討し、そのようなスケジュールである理由を確認してください。

配列

最も単純なオプションは、要素の数が事前にわかっている配列です。 その中に、各オブジェクトへの参照が格納されます：4（8）バイト（括弧内の値は64ビットJVMの場合）、さらに、配列の長さはint、4バイトで、オブジェクト記述子は8（16）バイトです。 さらに、各オブジェクトは8バイトでアラインされるため、32ビットごとに偶数個の要素を持つ配列は4バイトを失います。 結果：オブジェクトごとに4（8）バイトと12〜24バイトの定数。



空の配列は16（24）バイトを占有します。

配列リスト

ここでは、わずかに違いはありますが、ほとんど同じです。配列内の要素の数が事前にわからないため、配列にはマージン（デフォルトでは10要素）が割り当てられ、必要に応じて1.5倍以上拡張されます。

int newCapacity = (oldCapacity * 3)/2 + 1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、グラフは6（12）バイトにジャンプします。 定数もわずかに大きくなります。40（64）バイト。配列に加えて、配列への参照、リストの実際のサイズ、および変更の数（ConcurrentModificationExceptionをスローする）を格納するArrayListオブジェクトもあります。 それでも、これは、どれだけのデータがあるか事前にわからない場合、同じタイプのデータを保存する最も経済的な方法です。



要素を持たないデフォルトの構築されたArrayListは80（144）バイトを取ります。

LinkedList

リンクリストの場合、画像は配列のようなものです。双曲線の漸近線になりがちです。 java.util.LinkedList.Entryタイプの1つのサービスオブジェクトがリストアイテムごとに作成されます。 これらの各オブジェクトには3つのリンク（リスト項目自体、前および次のエントリへ）が含まれ、32ビットでのアライメントにより4バイトが失われるため、最終的に各エントリには24（40）バイトが必要です。 定数には、LinkedListオブジェクトのハンドル、先頭のエントリとそのリンク、リストのサイズ、および変更の数が48（80）バイト含まれます。 もちろん、ここではメモリが割り当てられないため、空のリストは同じ量を占有します。

ツリーセット

一般に、使用されるすべてのセットはマップに基づいています。 場合によっては、個別の実装は多少コンパクトになる可能性がありますが、一般的なコードはもちろん重要です。



グラフは、LinkedListと配列のようにも見えます。 各要素に対して、キー、値、親、左および右の子の5つのリンクを含むjava.util.TreeMap.Entryツリーブランチが作成されます。 それらに加えて、枝の色、赤または黒を示すブール変数が保存されます（ 赤黒木を参照）。 単一のブール変数は4バイトを使用するため、レコード全体は32（64）バイトを使用します。



TreeMapの定数データは、コンパレータへの参照、ツリーのルートへの参照（LinkedListの天体エントリとは異なり、ルートは意図された目的に使用されます-セットの実際の要素を参照）、entrySetへのリンク、navigableKeySet、descendingMap（これらのオブジェクトはオンデマンドで作成されます）、変更のサイズと数。 TreeMapオブジェクト記述子を使用すると、48（80）バイトが取得されます。 TreeSet自体は、記述子とTreeMapへのリンクのみを追加します。 合計で64（104）バイトが出力されます。 空のセットの重量は同じです。 ところで、メモリ消費はツリーのバランスの程度に依存しません。

ハッシュセット

HashSetはHashMapに基づいていますが、これはTreeMapより少し複雑です。 各要素に対して、キーへのリンク、Entryに続く値（複数のエントリがハッシュテーブルの同じセルに入る場合）、およびハッシュ値自体を含むjava.util.HashMap.Entryエントリが作成されます。 全体で、エントリの重量は24（48）バイトです。



エントリに加えて、エントリへのリンクを含むハッシュテーブルもあります。このテーブルには、最初は16個の要素が含まれ、要素数がサイズの75％を超えると倍になります（75％はデフォルトのloadFactor値で、コンストラクタで指定できます）。 つまり、デフォルトで構築する場合、要素の数が12、24、48、96などを超えるとテーブルが拡大されます（2 ⁿ * 3、グラフの最後のバーストは6144要素です）。 増加直後のテーブルは、要素数の2 / 0.75 = 2.67倍です。つまり、総消費量は要素あたり約34.67（69.33）バイトです（定数はカウントしません）。 増加の直前では、テーブルは要素数の1 / 0.75 = 1.33倍であり、合計消費量は要素あたり29.33（58.67）バイトです。 メモリ使用量は、ハッシュ衝突が発生する頻度とは完全に独立していることに注意してください。



希望する人は定数コンポーネントを自分で計算できます。デフォルトで初期化された空のHashSetの重さは136（240）バイトだと言います。

LinkedHashSet

HashSetとほぼ同じです。 java.util.LinkedHashMap.Entryを使用してjava.util.HashMap.Entryを継承し、前と次の要素に2つのリンクを追加するため、グラフはHashSetより8（16）バイト高く、テーブル拡張37.33（74.67）の前に達します以降-記録42.67（85.33）。 LinkedListのように、セットの要素を参照しない先頭のエントリが格納されるため、定数も増加しました。 新しく作成されたLinkedHashSetの重量は176（320）バイトです。

IdentityHashSet（newSetFromMap経由）

IdentityHashMapは非常に興味深いものです。 キーを等しいではなく==と比較し、System.identityHashCodeを使用することにより、標準のマップコントラクトに違反します。 また、Entryのようなオブジェクトを作成せず、すべてのキーと値を1つの配列（偶数要素のキー、奇数要素の値）に単純に格納するため、興味深いものです。 衝突が発生した場合、リストは作成されませんが、オブジェクトは配列に沿った最初の空きセルに書き込まれます。 これにより、すべてのセットで記録的な低いオーバーヘッドコストが達成されます。



IdentityHashMapは、2/3を超えるたびに配列のサイズを2倍にします（HashMapとは異なり、この係数は構成できません）。 デフォルトでは、32個の要素を持つ配列が作成されます（つまり、配列のサイズは64です）。 したがって、21、42、85、170などを超えると拡張が発生します（[2 ⁿ / 3]、グラフの最後のサージは5461です）。 拡張前の配列には、IdentityHashMapのキーの3倍、拡張後の6倍の要素が含まれています。 したがって、オーバーヘッドは要素ごとに12（24）〜24（48）バイトです。 デフォルトでは、空のセットはかなり多く-344（656）バイトかかりますが、すでに9つの要素があるため、他のすべてのセットよりも経済的になります。

ConcurrentHashSet（newSetFromMap経由）

ConcurrentHashMapは、チャートが要素自体（またはハッシュ関数）に依存する最初のコレクションです。 大まかに言うと、これは固定数のセグメント（デフォルトでは16）のセットであり、各セグメントはHashMapの同期アナログです。 変更されたハッシュコードからのビットの一部は、セグメントの選択に使用され、異なるセグメントへのアクセスは並行して発生する可能性があります。 java.util.concurrent.ConcurrentHashMap.HashEntryはjava.util.HashMap.Entryとほとんど同じであるため、制限では、オーバーヘッドはHashMap自体のオーバーヘッドと同じです。 グラフが同時に上昇しないため、セグメントのサイズの増加は独立して発生します。まず、より多くの要素があるセグメントが増加します。



このコレクションは、16個のセグメントがすぐに開始され、それぞれが16個のレコードといくつかの補助フィールドを持つテーブルを持っているため、初期サイズ-1304（2328）バイトの面でトップになりました。 ただし、10,000個の要素の場合、ConcurrentHashSetはHashSetよりも0.3％だけ大きくなります。

ConcurrentSkipListSet

ConcurrentSkipListMapを介して実装され、私の意見では、記述されたコレクションの中で最も複雑です。 アルゴリズムのアイデアはHabréで説明されているため、ここでは詳しく説明しません。 ここで得られるメモリサイズはデータに依存しませんが、収集は擬似乱数ジェネレータによって開始されるため、非決定的です。 次の擬似乱数に基づいて、インデックスエントリを追加するかどうかと、レベル数を決定します。 1つのjava.util.concurrent.ConcurrentSkipListMap.Nodeオブジェクトは、キー、値、および次のノードへの参照を含む各要素に対して必ず作成され、単純に接続されたリストを形成します。 これにより、要素ごとに24（40）バイトが得られます。 さらに、2つの要素ごとに約1つのインデックスエントリ（java.util.concurrent.ConcurrentSkipListMap.Index）が作成されます（最初のレベルでは、4番目ごとにレコードがあり、2番目には8番目ごとに、など）。 各インデックスエントリの重さはNodeと同じであり（そこには3つのリンクもあります）、合計で各要素には約36（60）バイトが必要です。 各レベル（HeadIndex）にはヘッドレコードがありますが、それらはほとんどない（ほぼ要素数の対数）ので、無視できます。



空のConcurrentSkipListSetには、1つのHeadIndexと1つの空のノードが作成されます。 デフォルトで構築後、コレクションは112（200）バイトかかります。

なんでこんなこと？

結果はほとんど予期せず、私の直感的なアイデアと矛盾していました。 そのため、競合するコレクションは通常のコレクションよりもはるかに多く、LinkedHashSetはTreeSetとHashSetの間のどこかに配置する必要があると考えました。 また、メモリ消費がオブジェクト自体に依存しないことは事実上ないことも驚くべきことでした。ツリーのバランスの度合いやハッシュテーブル内の衝突の数は何にも影響せず、競合しないコレクションの場合、オーバーヘッドのサイズを最大1バイトの精度で事前に決定できます。 さまざまなコレクションの内部構造を掘り下げることは興味深いことでした。 この研究に具体的な実際的な利点はありますか？わかりません、誰もが自分で決めてください。