¿Cómo funciona la compactación en pila?

Question

Dicen que la compactación de recolectores de basura es más rápida que la administración de memoria tradicional porque solo tienen que recolectar objetos en vivo, y al reorganizarlos en la memoria para que todo esté en un bloque contiguo, terminas sin fragmentación de pila. ¿Pero cómo se puede hacer eso rápidamente? Me parece que eso es equivalente al problema del empaquetamiento de contenedores, que es NP-hard y no puede completarse en un período de tiempo razonable en un gran conjunto de datos dentro de los límites actuales de nuestro conocimiento sobre el cálculo. ¿Qué me estoy perdiendo?

Answer 1

Compactación significa mover objetos en la RAM para que se eliminen algunos objetos (los objetos muertos, que se supone que el GC debe reclamar) y todos los objetos restantes se vuelven contiguos en la RAM.

La mayoría de las compactaciones de GC funcionan asignando objetos dentro de un único, área contigua obtenida del sistema operativo. La compactación es como quitar los objetos muertos y luego empujar todos los objetos vivos restantes "hacia la izquierda", exprimiendo los agujeros. Si el GC funciona por compactación, entonces la asignación es simplemente una cuestión de mover hacia arriba el puntero de "fin del área asignada". Sintéticamente, dentro del área de asignación, hay un puntero tal que el área libre consta de los bytes después de ese puntero. Para asignar espacio para un objeto, el puntero simplemente se mueve hacia arriba por el nuevo tamaño del objeto. Ocasionalmente, el GC decide que es hora de correr, detecta el objeto muerto, exprime los agujeros y, por lo tanto, reduce el puntero de asignación.

Las mejoras en el rendimiento de un GC compactación provienen de varias fuentes:

• Para la asignación, no hay necesidad de encontrar un "agujero" adecuada: por la construcción, el espacio libre es, en todo momento, una sola , área grande, y basta con mover un puntero hacia arriba.
• No hay fragmentación: la compactación mueve todos los objetos vivos juntos, pero esto se puede ver moviendo todos los agujeros juntos en un único espacio libre grande.
• Localidad mejorada. Al mover objetos vivos a áreas adyacentes, se mejora el comportamiento con respecto a la memoria caché. En particular, los algoritmos de compactación tienden a mantener los objetos en su orden de asignación respectivo (los objetos se deslizan pero no se intercambian) que se ha informado que son heurísticamente buenos para la mayoría de las aplicaciones.

Si el sistema operativo se niega a dar una sola área de la asignación, en lugar de ceder varios bloques, entonces las cosas se vuelven un poco más complejo, y podría empezar a parecerse al problema de bin-embalaje, debido a que el GC compactar a continuación, tiene que decidir en qué bloque va cada objeto vivo. Sin embargo, la complejidad del bin-packing se trata de encontrar el partido "perfecto" en el caso general; una solución aproximada ya es lo suficientemente buena para un asignador de memoria.

La dificultad algorítmica en un algoritmo de compactación consiste en actualizar todos los punteros, de modo que apunten a la nueva ubicación del objeto. A través de una tipificación estricta, la máquina virtual .NET puede decidir inequívocamente si cada palabra en la RAM es un puntero o no, pero actualizar todos los punteros de manera eficiente sin utilizar demasiada RAM extra puede ser complicado. H.B.M. Jonkers ha descrito un algoritmo maravillosamente inteligente para eso, en "Un algoritmo de compactación rápida de basuras" (Information Processing Letters, Volumen 9, Número 1, 1979, pp. 26-30). No pude encontrar una copia de ese documento en Vast Internet, pero el algoritmo se describe en el libro "Garbage Collection" de Jones and Lins (sección 5.6). Recomiendo encarecidamente ese libro a cualquiera que esté interesado en entender a los recolectores de basura. El algoritmo de Jonkers requiere dos pasos lineales en los objetos en vivo y resulta fácil de implementar (unas pocas docenas de líneas de código, nada más, la parte más difícil es entender por qué funciona).

La complejidad adicional proviene de colectores generacionales que intentan, la mayoría de las veces, dejar la mayoría de los objetos intactos, trabajando preferentemente solo con objetos jóvenes. Aquí, esto significa compactar solo el final del montón; la compactación completa se aplica solo en raras ocasiones. El punto aquí es que una compactación completa, aunque lineal, aún podría inducir una pausa notable. Generational GC intenta hacer tales pausas más raras. Una vez más, el libro de Jones y Lins es una lectura obligada.