¿Cuáles son las ventajas y desventajas de tener bits de marca juntos y separados para la recolección de basura?

Question

estaba viendo el vídeo Google IO 2008: componentes internos de la máquina virtual Dalvik para comprender cómo funciona Dalvik VM y por qué esas personas han preferido Dalvik VM a JVM para Android.Descubrí que Android usa memoria separada para la información de basura sobre los objetos, a diferencia de la JVM donde tenemos bits de marca (bits que indican si el objeto puede recolectar basura o no) junto con los objetos.

¿Alguien puede decirme en detalle cuáles son las ventajas y desventajas de tener memoria separada para bits de marcas y no tener memoria separada para bits de marcas?

No pude obtener esta diferencia viendo el video.

Answer 1

Algunas ventajas de un mapa de bits separado:

• mucho más denso. Un GC típico necesita tal vez ocho bits de metadatos GC, pero debido a la alineación, un encabezado en objeto podría redondear esta memoria hasta 32 bits.
• Algunas operaciones, en particular alrededor de barrido, se vuelven más rápidas. Esto se debe en parte a que el mapa de bits más denso (ver más arriba) significa menos tráfico de memoria y un mejor uso de la memoria caché, pero también porque algunas operaciones (por ejemplo, a cero, todos los bits de marca) se pueden dibujar cuando se encuentran en este formato. (Otras partes del GC deben diseñarse para hacer uso de esa capacidad).
• Si geneacodicEtAcodio en un sistema UNIX, un bitmark separado hace un mejor uso de copiar-en escribir: las páginas que contienen objetos pueden permanecer compartidas.

Algunas ventajas de los bits de marca en el objeto:

• Dependiendo del esquema utilizado para asociar objetos con mapas de bits, obtener la broca de marca para un objeto y viceversa puede ser bastante complicado y / o lento. Un encabezado en objeto, por otro lado, es trivial de acceso.
• Gestión de memoria más fácil: No es necesario crear una asignación separada del tamaño correcto y mantenerlo en sincronización.
• Muchos esquemas rápidos para encontrar mapas de bits para objetos y viceversa son bastante restrictivos en otros aspectos. Por ejemplo, si crea un mapa de bits para cada página y almacena el puntero de mapa de bits al inicio de la página, tiene un problema almacenando objetos más grande que una página.

Answer 2

Los bits de marca separados funcionan al tener una matriz de bits donde cada bit representa una dirección en el montón que puede iniciar un objeto.Por ejemplo, supongamos que el montón tiene 65536 bytes y todos los objetos están alineados en límites de 16 bytes, entonces hay 4096 direcciones en el montón que pueden ser el inicio de un objeto.Esto significa que la matriz debe contener 4096 bits, que se pueden almacenar de manera eficiente como 512 bytes o 64 enteros sin signo de 64 bits.

Los bits de marca en el objeto funcionan estableciendo un bit de cada encabezado de cada objeto en 1 si el objeto está marcado y en 0 en caso contrario.Tenga en cuenta que esto requiere que cada objeto tenga un área de encabezado dedicada.Los tiempos de ejecución como JVM y .NET agregan encabezados a los objetos, por lo que básicamente obtienes el espacio para el bit de marca de forma gratuita.

Pero no funciona para coleccionistas conservadores que no tienen control total del entorno en el que operan, como el Boehm GC.Pueden identificar erróneamente números enteros como punteros, por lo que para ellos modificar cualquier cosa en el montón de datos de los mutadores es arriesgado.

La recolección de basura de Mark & ​​Sweep se divide en dos fases:marcar y barrer.El marcado utilizando bits de marca en el objeto es sencillo (pseudocódigo):

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

Usando una matriz separada para almacenar bits de marca, tenemos que convertir la dirección y el tamaño de los objetos en índices en la matriz de bits y establecer los bits correspondientes en 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)

Entonces, en nuestro ejemplo, si un objeto tiene 128 bytes de largo, se establecerán 8 bits en la matriz de bits.Claramente, usar bits de marca en el objeto es mucho más sencillo.

Pero los bits de marcas separados ganan algo de impulso al realizar el barrido.El barrido implica escanear todo el montón y encontrar regiones continuas de memoria que no estén marcadas y, por lo tanto, puedan recuperarse.Usando bits de marca en el objeto, se vería más o menos así:

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)

Observe cómo la iteración salta de un objeto a otro en el iter += iter.size() líneas.Esto significa que el tiempo de ejecución de la fase de barrido es proporcional al número total de objetos vivos y basura.

Usando bits de marca separados, haría aproximadamente el mismo bucle excepto que grandes franjas de objetos de basura serían sobrevolados sin "detenerse" en cada uno de ellos.

Considere nuevamente el montón 65536.Supongamos que contiene 4096 objetos que son todos basura.Iterar los 64 enteros de 64 bits en la matriz de bits de marca y ver que todos son 0 es obviamente muy rápido.Por lo tanto, la fase de barrido puede ser potencialmente mucho más rápida con bits de marca separados.

¡Pero hay otra arruga!En cualquier recopilador de marcas y barridos, el tiempo de ejecución está dominado por la fase de marcas y no por la fase de barrido, que suele ser muy rápida.Así que el veredicto aún no se ha pronunciado.Algunos prefieren bits de marcas separados, otros prefieren los que están dentro del objeto.Hasta donde yo sé, nadie ha podido demostrar todavía qué enfoque es superior al otro.