2

私はビデオGoogle IO 2008 - Dalvik Virtual Machine Internalsを見ていました. オブジェクトと一緒にマークビット（オブジェクトがガベージコレクションを実行できるかどうかを示すビット）を持つJVMとは対照的に、Androidはオブジェクトに関するガベージ情報に別のメモリを使用することがわかりました。

マークビット用に別のメモリを持ち、マークビット用に別のメモリを持たないことの利点と欠点を詳しく教えてください。

動画を見てもこの違いはわかりませんでした。

4

2 に答える 2

1

個別のマーク ビットは、各ビットがオブジェクトを開始できるヒープ内のアドレスを表すビットの配列を持つことによって機能します。たとえば、ヒープが 65536 バイトで、すべてのオブジェクトが 16 バイト境界で整列されているとします。この場合、ヒープにはオブジェクトの開始となる可能性がある 4096 個のアドレスがあります。これは、配列が 4096 ビットを含む必要があることを意味します。これは、512 バイトまたは 64 個の 64 ビット サイズの符号なし整数として効率的に格納できます。

オブジェクト内マーク ビットは、オブジェクトがマークされている場合は各オブジェクトの各ヘッダーの 1 ビットを 1 に設定し、それ以外の場合は 0 に設定することで機能します。これには、各オブジェクトに専用のヘッダー領域が必要であることに注意してください。JVM や .NET などのランタイムはすべてオブジェクトにヘッダーを追加するため、基本的にマーク ビット用のスペースを無料で取得できます。

ただし、 Boehm GCなど、実行中の環境を完全に制御できない保守的なコレクターには機能しません。整数をポインターと誤認する可能性があるため、ミューテーター データ ヒープ内の何かを変更することは危険です。

マーク & スイープ ガベージ コレクションは、マーキングとスイープの 2 つのフェーズに分かれています。オブジェクト内マーク ビットを使用したマーキングは簡単です (疑似コード)。

if not obj.is_marked():
    obj.mark()
    mark_stack.append(obj)

マーク ビットを格納する別の配列を使用して、オブジェクトのアドレスとサイズをビット配列のインデックスに変換し、対応するビットを 1 に設定する必要があります。

obj_bits = obj.size_in_bytes() / 16
bit_idx = (obj - heap.start_address()) / 16
if not bitarr.bit_set(bit_idx):
    bitarr.set_range(bit_idx, obj_bits)
    mark_stack.append(obj)

この例では、オブジェクトの長さが 128 バイトの場合、8 ビットがビット配列に設定されます。明らかに、オブジェクト内マーク ビットを使用する方がはるかに簡単です。

しかし、個別のマーク ビットは、スイープ時にいくらかの勢いを増します。スイープには、ヒープ全体をスキャンし、マークされていないため再利用できるメモリの連続領域を見つけることが含まれます。オブジェクト内のマーク ビットを使用すると、おおよそ次のようになります。

iter = heap.start_address()
while iter < heap.end_address():
    # Scan til the next unmarked object
    while iter.is_marked():
        iter.unmark()
        iter += iter.size()
        if iter == heap.end_address():
            return
    # At an unmarked block
    start = iter
    # Scan til the next marked object
    while iter < heap.end_address() and not iter.is_marked():
        iter += iter.size()
    size = iter - start
    # Reclaim the block
    heap.reclaim(start, size)

反復が行内のオブジェクトからオブジェクトへとジャンプする方法に注意してくださいiter += iter.size()。これは、スイープ フェーズの実行時間がライブ オブジェクトとガベージ オブジェクトの合計数に比例することを意味します。

個別のマーク ビットを使用すると、ほぼ同じループを実行できますが、ガベージ オブジェクトの大きな範囲がそれぞれで「停止」せずに飛び越えます。

65536 ヒープをもう一度考えてみましょう。すべてガベージである 4096 個のオブジェクトが含まれているとします。マーク ビット配列内の 64 個の 64 ビット整数を反復し、それらがすべて 0 であることを確認するのは、明らかに非常に高速です。したがって、個別のマーク ビットを使用すると、スイープ フェーズを大幅に高速化できる可能性があります。

しかし、別のしわがあります！どのマーク アンド スイープ コレクターでも、実行時間は通常非常に速いスイープ フェーズではなく、マーク フェーズによって支配されます。したがって、判決はまだ出ていません。個別のマーク ビットを好むものもあれば、オブジェクト内のものを好むものもあります。私の知る限り、どちらのアプローチが他のアプローチよりも優れているかを示すことができた人はまだ誰もいません。

于 2016-12-09T18:02:29.703 に答える