Algoritmo de marcado y compactación

Un algoritmo basado en tablas fue descrito por primera vez por Haddon y Waite en 1967. ^{[ 1 ]} Preserva la ubicación relativa de los objetos activos en el montón y requiere solo una cantidad constante de sobrecarga.

La compactación se realiza desde la parte inferior del montón (direcciones bajas) hasta la superior (direcciones altas). A medida que se encuentran objetos activos (es decir, marcados), se mueven a la primera dirección baja disponible y se añade un registro a una tabla de reubicación. Para cada objeto activo, un registro en la tabla de reubicación contiene la dirección original del objeto antes de la compactación y la diferencia entre la dirección original y la nueva dirección después de la compactación. La tabla de reubicación se almacena en el montón que se está compactando, pero en un área marcada como no utilizada. Para garantizar que la compactación siempre se realice correctamente, el tamaño mínimo del objeto en el montón debe ser mayor o igual que el tamaño de un registro en la tabla de reubicación.

A medida que avanza la compactación, los objetos reubicados se copian hacia la parte inferior del montón. Eventualmente, un objeto deberá copiarse al espacio ocupado por la tabla de ruptura, que ahora debe reubicarse en otro lugar. Estos movimientos de la tabla de ruptura (denominados " rotación de la tabla" por los autores) provocan que los registros de reubicación se desordenen, lo que requiere ordenar la tabla de ruptura una vez finalizada la compactación. El costo de ordenar la tabla de ruptura es O ( n  log n ), donde n es el número de objetos activos encontrados en la etapa de marcado del algoritmo. 

Finalmente, los registros de reubicación de la tabla de rupturas se utilizan para ajustar los campos de puntero dentro de los objetos reubicados. Se examinan los objetos activos en busca de punteros, que se pueden consultar en la tabla de rupturas ordenada de tamaño n en tiempo O(log n ) si la tabla de rupturas está ordenada, para un tiempo de ejecución total de O ( n log n ). A continuación, los punteros se ajustan según la cantidad especificada en la tabla de reubicación.   

Para evitar una complejidad de O ( n  log n ), el algoritmo LISP 2 utiliza tres pasadas diferentes sobre el montón. Además, los objetos del montón deben tener una ranura de puntero de reenvío independiente que no se utilice fuera de la recolección de basura. 

Tras el marcado estándar, el algoritmo procede en las siguientes tres fases:

1. Calcular la ubicación de reenvío para los objetos activos.
   • Mantén un registro de un puntero libre y uno activo , e inicializa ambos al inicio del montón.
   • Si el puntero activo apunta a un objeto activo, actualice el puntero de reenvío de ese objeto al puntero libre actual e incremente el puntero libre según el tamaño del objeto.
   • Mueva el puntero activo al siguiente objeto.
   • Finaliza cuando el puntero activo llega al final del montón.
2. Actualizar todos los punteros
   • Para cada objeto activo, actualice sus punteros de acuerdo con los punteros de reenvío de los objetos a los que apuntan.
3. Mover objetos
   • Para cada objeto activo, mueva sus datos a su ubicación de reenvío.

Este algoritmo tiene una complejidad O ( n ) con respecto al tamaño del montón; presenta una complejidad menor que el enfoque basado en tablas, pero en este último, n representa únicamente el tamaño del espacio utilizado, no todo el espacio del montón como en el algoritmo LISP2. Sin embargo, el algoritmo LISP2 es más sencillo de implementar.

El algoritmo de compactación Compressor ^{[ 2 ]} tiene la menor complejidad entre los algoritmos de compactación conocidos actualmente. Extiende la recolección de basura de IBM para Java. ^{[ 3 ]} La versión serial de Compressor mantiene un mapa de reubicación que asigna la dirección antigua de cada objeto a su nueva dirección (es decir, su dirección antes de la compactación se asigna a su dirección después de la compactación). En una primera pasada, la asignación se calcula para todos los objetos en el montón. En una segunda pasada, cada objeto se mueve a su nueva ubicación (compactado al principio del montón) y todos los punteros dentro de él se modifican de acuerdo con el mapa de reubicación.

El cálculo del mapa de reubicación en la primera pasada puede optimizarse enormemente trabajando con tablas pequeñas que no requieren recorrer todo el montón. Esto mantiene baja la complejidad del compresor, que consta de una sola pasada sobre tablas pequeñas y otra sobre todo el montón. Esta es la complejidad más común entre los algoritmos de compactación.

El compresor también cuenta con una versión paralela en la que varios hilos de compactación pueden trabajar juntos para compactar todos los objetos en paralelo. Asimismo, dispone de una versión concurrente en la que los hilos de compactación pueden trabajar simultáneamente con el programa, permitiendo que este acceda a los objetos a medida que se mueven hacia el inicio del montón. Las versiones paralela y concurrente del compresor utilizan primitivas de memoria virtual.