¿Qué le compra la inversión de puntero en la colección de basura de marcas y barridos?

Question

Siento que me falta algo dolorosamente simple, pero estoy tratando de entender la recolección de basura según la implementación del Compilador Moderno de Andrew Appel en ML book y hay un pequeño párrafo dentro de la sección Mark and Sweep titulada Pointer Reversal (270).

En este punto creo que entiendo cómo funciona. En pocas palabras, a medida que recorre el gráfico, gira todos los punteros para que su predecesor esté dentro de su conjunto de campos. Luego, cuando haya terminado con un elemento dado, voltea los punteros hacia atrás para que apunten al lugar correcto nuevamente.

Si eso es correcto, ¿qué es exactamente lo que te compra? Appel intenta explicar esto, pero no entiendo completamente su fraseología.

Answer 1

Durante el marcado, los objetos se dividen en tres categorías:

1. objetos que no han sido marcados
2. objetos que se han marcado, pero puede apuntar a objetos no marcados
3. objetos que han sido marcados y puntos a los objetos marcados solamente

Como marcado procede, los objetos cambian de estado a partir de la categoría 1 a 2, y de la categoría 2 a la categoría 3. El recolector de basura debe realizar un seguimiento de todos los objetos en la categoría 2 para que pueda encontrar todos los objetos no marcados. Pero, ¿dónde almacena esa información? La recolección de basura puede estar ejecutándose cuando la memoria está completamente llena, por lo que no puede asignar dinámicamente una estructura de datos. Debe construir una estructura de datos que contenga objetos en la categoría 2, utilizando la memoria que ya está asignada. La inversión del puntero es un algoritmo para construir una lista vinculada de estos objetos sin asignar memoria.