algorithm - why - instagram hashtags on comments or caption

¿Cómo funciona la compactación del montón rápidamente?

Question

Dicen que compactar los recolectores de basura son más rápidos que la administración de memoria tradicional porque solo tienen que recopilar objetos vivos, y al reorganizarlos en la memoria para que todo esté en un bloque contiguo, no hay fragmentación en el montón. Pero, ¿cómo se puede hacer eso rápidamente? Me parece que eso es equivalente al problema de empaquetado de contenedores, que es NP-hard y no se puede completar en un tiempo razonable en un gran conjunto de datos dentro de los límites actuales de nuestro conocimiento sobre computación. ¿Qué me estoy perdiendo?

Answer 1

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

La mayoría de los trabajos de compactación de GC asignan objetos dentro de un área contigua y única obtenida del sistema operativo. La compactación es como quitar los objetos muertos y luego empujar todos los objetos vivos restantes "hacia la izquierda", apretando los agujeros. Si el GC funciona por compactación, entonces la asignación es simplemente una cuestión de subir el puntero del "final del área asignada". Sintéticamente, dentro del área de asignación, hay un puntero tal que el área libre consiste en 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. De vez en cuando, el GC decide que es hora de correr, detecta el objeto muerto, exprime los orificios y, por lo tanto, baja el puntero de asignación.

Las ganancias de rendimiento de un GC de compactación provienen de varias fuentes:

• Para la asignación, no hay necesidad de encontrar un "agujero" adecuado: por construcción, el espacio libre es, en todo momento, un área grande y única, y es suficiente simplemente mover un puntero hacia arriba.
• No hay fragmentación: la compactación mueve todos los objetos vivos juntos, pero esto puede verse como un movimiento de todos los agujeros en un solo espacio libre grande.
• Se mejora la localidad. 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 reportado como heurísticamente buenos para la mayoría de las aplicaciones.

Si el sistema operativo se niega a dar un área de asignación única, en lugar de eso da como resultado varios bloques, entonces las cosas se vuelven un poco más complejas y podrían comenzar a parecerse al problema de empaquetamiento de contenedores, porque el GC de compactación debe decidir a qué bloque va cada uno. objeto vivo Sin embargo, la complejidad del empaquetado de contenedores consiste en encontrar la coincidencia "perfecta" 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, para que apunten a la nueva ubicación del objeto. A través de la escritura estricta, la máquina virtual .NET puede decidir sin ambigüedades 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. HBM Jonkers ha descrito un algoritmo maravillosamente inteligente para eso, en "Un algoritmo rápido de compactación de basura" (Information Processing Letters, Volume 9, Number 1, 1979, pp. 26-30). No pude encontrar una copia de ese documento en Vast Internet, pero el algoritmo se describe en el libro "Recolección de basura" de Jones and Lins (sección 5.6). Recomiendo encarecidamente ese libro a cualquiera que esté interesado en comprender a los recolectores de basura. El algoritmo de Jonkers requiere dos pasadas lineales sobre los objetos vivos y resulta fácil de implementar (unas docenas de líneas de código, no más; la parte más difícil es entender por qué funciona).

La complejidad adicional proviene de los coleccionistas generacionales que, la mayoría de las veces, intentan 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. GC generacional intenta hacer tales pausas más raras. Una vez más, el libro de Jones y Lins es una lectura obligada.