Was sind die Vor- und Nachteile der Zusammenlegung und Trennung von Markierungsbits für die Garbage Collection?

Question

Ich habe mir ein Video angesehen Google IO 2008 – Interna der virtuellen Dalvik-Maschine um zu verstehen, wie Dalvik VM funktioniert und warum diese Leute Dalvik VM gegenüber JVM für Android bevorzugen.Ich habe festgestellt, dass Android einen separaten Speicher für Garbage-Informationen zu den Objekten verwendet, im Gegensatz zur JVM, wo wir Markierungsbits (Bits, die angeben, ob das Objekt für die Garbagfe-Sammlung geeignet ist oder nicht) zusammen mit Objekten haben.

Kann mir jemand im Detail sagen, welche Vor- und Nachteile es hat, einen separaten Speicher für Markierungsbits zu haben und keinen separaten Speicher für Markierungsbits zu haben?

Ich konnte diesen Unterschied nicht erkennen, indem ich mir ein Video ansah.

Answer 1

Einige Vorteile einer separaten Bitmap:

• viel dichter. Ein typischer GC benötigt möglicherweise acht Bits von GC-Metadaten, aber aufgrund der Ausrichtung kann ein In-Objekt-Header diesen Speicher bis zu 32 Bit umrunden.
• Einige Operationen, insbesondere um Fegen, werden schneller. Dies ist zum Teil darauf zurückzuführen, dass der dichter (siehe oben genannte) Bitmap weniger Speicherverkehr und eine bessere Cache-Verwendung bedeutet, sondern auch, da einige Operationen (z. B. auf Nullwechsel aller Markbits) in diesem Format vectorisiert werden können. (Andere Teile des GC müssen so gestaltet sein, dass diese Fähigkeit nutzt.)
• Wenn Sie mit einem separaten Bitmark ein separates Bitmark verwenden, nutzen Sie eine separate Bitmark, um Copy-on-Write besser zu verwenden: Seiten, die Objekte enthalten, können möglicherweise gemeinsam genutzt werden.

Einige Vorteile von In-Objekt-Zeichenbits:

• Abhängig von dem Schema, das zum Associate von Objekten mit Bitmaps verwendet wird, kann das Markierungsbit für ein Objekt erhalten und umgekehrt ziemlich kompliziert und / oder langsam sein. Ein In-Objekt-Header dagegen ist trivial, um darauf zuzugreifen.
• einfacher Speicherverwaltung: Sie müssen keine separate Zuteilung der richtigen Größe erstellen und synchronisieren.
• Viele schnelle Schemata zum Finden von Bitmaps für Objekte und umgekehrt sind in anderen Gängen recht restriktiv. Wenn Sie beispielsweise eine Bitmap für jede Seite erstellen, und den Bitmap-Zeiger am Start der Seite speichern, haben Sie ein Problem mit dem Problem, dass Objekte größer als eine Seite gespeichert sind.

Answer 2

Separate Markierungsbits funktionieren, indem sie über ein Array von Bits verfügen, wobei jedes Bit eine Adresse im Heap darstellt, die ein Objekt starten kann.Angenommen, der Heap ist 65536 Byte groß und alle Objekte sind an 16-Byte-Grenzen ausgerichtet, dann gibt es 4096 Adressen im Heap, die der Anfang eines Objekts sein können.Das bedeutet, dass das Array 4096 Bit enthalten muss, die effizient als 512 Byte oder 64 vorzeichenlose Ganzzahlen mit einer Größe von 64 Bit gespeichert werden können.

In-Objekt-Markierungsbits funktionieren, indem ein Bit jedes Headers jedes Objekts auf 1 gesetzt wird, wenn das Objekt markiert ist, andernfalls auf 0.Beachten Sie, dass hierfür jedes Objekt einen eigenen Header-Bereich haben muss.Laufzeitumgebungen wie JVM und .NET fügen alle Header zu Objekten hinzu, sodass Sie den Platz für das Markierungsbit im Wesentlichen kostenlos erhalten.

Aber es funktioniert nicht für konservative Sammler, die nicht die volle Kontrolle über die Umgebung haben, in der sie laufen, wie zum Beispiel Boehm GC.Sie können ganze Zahlen fälschlicherweise als Zeiger identifizieren, daher ist es für sie riskant, irgendetwas im Datenheap des Mutators zu ändern.

Die Mark & ​​Sweep-Garbage Collection ist in zwei Phasen unterteilt:Markieren und Fegen.Die Markierung mithilfe von objektinternen Markierungsbits ist unkompliziert (Pseudocode):

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

Unter Verwendung eines separaten Arrays zum Speichern von Markierungsbits müssen wir die Objektadresse und -größe in Indizes im Bitarray umwandeln und die entsprechenden Bits auf 1 setzen:

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)

Wenn also in unserem Beispiel ein Objekt 128 Bytes lang ist, werden 8 Bits im Bit-Array gesetzt.Offensichtlich ist die Verwendung von objektinternen Markierungsbits viel einfacher.

Aber einzelne Markierungsbits gewinnen beim Sweepen etwas an Dynamik.Beim Sweeping wird der gesamte Heap durchsucht und kontinuierliche Speicherbereiche gefunden, die nicht markiert sind und daher wiederhergestellt werden können.Unter Verwendung von objektinternen Markierungsbits würde es ungefähr so ​​aussehen:

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)

Beachten Sie, wie die Iteration von Objekt zu Objekt springt iter += iter.size() Linien.Dies bedeutet, dass die Laufzeit der Sweep-Phase proportional zur Gesamtzahl der Live- und Garbage-Objekte ist.

Unter Verwendung separater Markierungsbits würden Sie ungefähr die gleiche Schleife ausführen, mit der Ausnahme, dass große Schwaden von Müllobjekten überflogen würden, ohne bei jedem von ihnen „anzuhalten“.

Betrachten Sie noch einmal den Heap 65536.Angenommen, es enthält 4096 Objekte, die allesamt Müll sind.Die 64 64-Bit-Ganzzahlen im Markierungsbit-Array zu iterieren und festzustellen, dass sie alle 0 sind, geht offensichtlich sehr schnell.Daher kann die Wobbelphase mit separaten Markierungsbits möglicherweise viel schneller sein.

Aber es gibt noch eine weitere Falte!Bei jedem Mark-and-Sweep-Kollektor wird die Laufzeit von der Mark-Phase dominiert und nicht von der Sweep-Phase, die normalerweise sehr schnell ist.Das Urteil steht also noch aus.Einige bevorzugen separate Markierungsbits, andere bevorzugen objektinterne Markierungsbits.Meines Wissens nach konnte noch niemand zeigen, welcher Ansatz dem anderen überlegen ist.