マークビットをまとめてガベージコレクションに分離するという利点と短所は何ですか

Question

私はビデオを見ていました Google IO 2008 - Dalvik仮想マシン内部 Dalvik VMは、Android用のJVM上でDalvik VMを望んでいる理由となぜ。Androidは、マークビットがあるJVMとは反対、オブジェクトに関するガベージ情報に別々のメモリを使用していることを発見しました。

誰かが私に詳述することができますマークビットのための別々のメモリを持ち、マークビットのための別々のメモリを持たないという利点と短所は何ですか？

ビデオを見ることでこの違いを得ることができませんでした。

Answer 1

別のビットマップのいくつかの利点：

• はるかに密集しています。一般的なGCは8ビットのGCメタデータを必要とするかもしれませんが、アライメントのアライメントのために、インオブジェクトヘッダーはこのメモリを最大32ビットまで丸める可能性があります。
• 特に掃除の周りの操作によっては速くなります。これは部分的にはより低いビットマップで、メモリトラフィックとより良いキャッシュ使用を意味するためですが、いくつかの操作（すべてのマークビットをゼロにする）をこの形式でベクトル化できます。 （GCの他の部分はその能力を利用するように設計される必要があります。）
• UNIXシステムでfork()の場合、個別のビットマークがコピーオンライトを使用すると、オブジェクトを含むページが共有されている場合があります。

オブジェクト内マークビットのいくつかの利点：

• オブジェクトをビットマップに関連付けるために使用される方式に応じて、オブジェクトのマークビットを取得し、その逆もまた/または遅くなる可能性があります。一方、オブジェクト内ヘッダーはアクセスするのが簡単です。
• メモリ管理を容易にする：正しいサイズの別の割り当てを作成し、それを同期させる必要はありません。
• オブジェクトのビットマップを見つけるための多くの高速なスキームは、他の点に関してかなり制限があります。たとえば、ページごとにビットマップを作成し、ページの先頭にビットマップポインタを保存する場合は、ページよりも大きいオブジェクトを記憶する問題があります。

Answer 2

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

オブジェクト内マークビットは、オブジェクトがマークされていれば、各オブジェクトの各ヘッダのビットを1に設定することで動作します。これには、各オブジェクトが専用のヘッダー領域を持つことが必要です。 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)

.

soこの例では、オブジェクトが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であることを確認しても明らかに非常に速いです。したがって、掃引段階は別々のマークビットではるかに速くなる可能性があります。

しかし、もう一つのしわがあります！任意のマークおよびスイープコレクタでは、ランニングタイムはマークフェーズによって支配され、通常は非常に速いスイープフェーズではありません。だから評決はまだ出ています。別のマークビット、その他のオブジェクト内のものを好むものがあります。私の知る限りでは、どちらがどちらのアプローチが一方に優れているかを示すことができませんでした。