Quali sono i vantaggi e gli svantaggi di avere i bit contrassegnati insieme e separati per la Garbage Collection

Question

Stavo guardando un video Google IO 2008 - Componenti interni della macchina virtuale Dalvik per capire come funziona Dalvik VM e perché queste persone hanno preferito Dalvik VM a JVM per Android.Ho scoperto che Android utilizza una memoria separata per le informazioni di Garbage sugli oggetti, al contrario della JVM in cui abbiamo bit di contrassegno (bit che indicano se l'oggetto è in grado di raccogliere o meno i rifiuti) insieme agli oggetti.

Qualcuno può dirmi in dettaglio quali sono i vantaggi e gli svantaggi di avere una memoria separata per i bit dei contrassegni e di non avere memoria separata per i bit dei contrassegni?

Non sono riuscito a ottenere questa differenza guardando il video.

Answer 1

Alcuni vantaggi di una bitmap separata:

• Molto più denso.Un tipico GC necessita forse di otto bit di metadati GC, ma a causa dell'allineamento un'intestazione nell'oggetto potrebbe arrotondare questa memoria fino a 32 bit.
• Alcune operazioni, in particolare quelle di spazzamento, diventano più veloci.Ciò è in parte dovuto al fatto che la bitmap più densa (vedi sopra) significa meno traffico di memoria e un migliore utilizzo della cache, ma anche perché alcune operazioni (ad es.azzerando tutti i bit dei contrassegni) può essere vettorizzato in questo formato.(Altre parti del GC devono essere progettate per sfruttare tale capacità.)
• Se tu fork() su un sistema Unix, un bitmark separato fa un uso migliore della copia su scrittura:Le pagine contenenti oggetti potrebbero rimanere condivise.

Alcuni vantaggi dei bit di contrassegno nell'oggetto:

• A seconda dello schema utilizzato per associare gli oggetti alle bitmap, ottenere il bit di contrassegno per un oggetto e viceversa può essere piuttosto complicato e/o lento.Un'intestazione in-oggetto, d'altra parte, è banale da accedere.
• Gestione della memoria più semplice:Non è necessario creare un'allocazione separata della giusta dimensione e mantenerla sincronizzata.
• Molti schemi veloci per trovare bitmap per oggetti e viceversa sono piuttosto restrittivi sotto altri aspetti.Ad esempio, se crei una bitmap per ogni pagina e memorizzi il puntatore bitmap all'inizio della pagina, avrai problemi a memorizzare oggetti più grandi di una pagina.

Answer 2

I bit di contrassegno separati funzionano avendo una matrice di bit in cui ciascun bit rappresenta un indirizzo nell'heap che può avviare un oggetto.Ad esempio, supponiamo che l'heap sia di 65536 byte e che tutti gli oggetti siano allineati su limiti di 16 byte, quindi nell'heap sono presenti 4096 indirizzi che possono essere l'inizio di un oggetto.Ciò significa che l'array deve contenere 4096 bit, che possono essere archiviati in modo efficiente come 512 byte o 64 interi senza segno di dimensione 64 bit.

I bit di contrassegno nell'oggetto funzionano impostando un bit di ciascuna intestazione di ciascun oggetto su 1 se l'oggetto è contrassegnato e su 0 altrimenti.Tieni presente che ciò richiede che ciascun oggetto abbia un'area di intestazione dedicata.I runtime come JVM e .NET aggiungono tutti intestazioni agli oggetti in modo da ottenere essenzialmente lo spazio per il bit di contrassegno gratuitamente.

Ma non funziona per i collezionisti conservatori che non hanno il pieno controllo dell'ambiente in cui corrono, come ad esempio Boehm GC.Possono identificare erroneamente gli interi come puntatori, quindi per loro modificare qualsiasi cosa nell'heap dei dati dei mutatori è rischioso.

La raccolta dei rifiuti Mark & ​​Sweep è divisa in due fasi:marcatura e spazzamento.Contrassegnare utilizzando i bit di contrassegno nell'oggetto è semplice (pseudo-codice):

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

Utilizzando un array separato per memorizzare i bit dei contrassegni, dobbiamo convertire l'indirizzo e la dimensione degli oggetti in indici nell'array di bit e impostare i bit corrispondenti su 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)

Quindi nel nostro esempio, se un oggetto è lungo 128 byte, nell'array di bit verranno impostati 8 bit.Chiaramente, usare i bit di contrassegno nell'oggetto è molto più semplice.

Ma i bit di marcatura separati guadagnano un po' di slancio durante lo spazzamento.Lo spazzamento implica la scansione dell'intero mucchio e la ricerca di regioni continue di memoria che non sono contrassegnate e quindi possono essere recuperate.Utilizzando i bit di contrassegno nell'oggetto, il risultato sarebbe più o meno questo:

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)

Nota come l'iterazione salta da un oggetto all'altro nel file iter += iter.size() linee.Ciò significa che il tempo di esecuzione della fase di scansione è proporzionale al numero totale di oggetti attivi e spazzatura.

Usando bit di marcatura separati, faresti più o meno lo stesso ciclo, tranne per il fatto che grandi fasce di oggetti spazzatura verrebbero sorvolate senza "fermarsi" su ciascuno di essi.

Consideriamo nuovamente l'heap 65536.Supponiamo che contenga 4096 oggetti che sono tutti spazzatura.Iterare i 64 interi a 64 bit nell'array mark bits e vedere che sono tutti 0 è ovviamente molto veloce.Pertanto la fase di scansione può essere potenzialmente molto più veloce con bit di marcatura separati.

Ma c'è un'altra ruga!In qualsiasi raccoglitore di marcatura e spazzata, il tempo di esecuzione è dominato dalla fase di marcatura e non dalla fase di spazzata che di solito è molto veloce.Quindi la sentenza è ancora fuori.Alcuni preferiscono bit di marcatura separati, altri preferiscono quelli interni all'oggetto.Per quanto ne so, nessuno è ancora riuscito a dimostrare quale approccio sia superiore all’altro.