En informática , un algoritmo de compactación de marcas es un tipo de algoritmo de recolección de basura que se utiliza para recuperar memoria inalcanzable . Los algoritmos de compactación de marcas pueden considerarse una combinación del algoritmo de barrido de marcas y el algoritmo de copia de Cheney . Primero, se marcan los objetos alcanzables y luego un paso de compactación reubica los objetos alcanzables (marcados) hacia el comienzo del área del montón. La recolección de basura compactada es utilizada por las JVM modernas , Common Language Runtime de Microsoft y por el compilador Glasgow Haskell .
Después de marcar los objetos vivos en el montón de la misma manera que el algoritmo de marcado y barrido , el montón a menudo se fragmentará . El objetivo de los algoritmos de marcado y compactación es desplazar juntos los objetos vivos en la memoria para eliminar la fragmentación. El desafío es actualizar correctamente todos los punteros a los objetos movidos, la mayoría de los cuales tendrán nuevas direcciones de memoria después de la compactación. La cuestión de manejar las actualizaciones de punteros se maneja de diferentes maneras.
Haddon y Waite describieron por primera vez un algoritmo basado en tablas en 1967. [1] Conserva la ubicación relativa de los objetos vivos en el montón y solo requiere una cantidad constante de sobrecarga.
La compactación se lleva a cabo desde la parte inferior del montón (direcciones bajas) hasta la parte superior (direcciones altas). A medida que se encuentran objetos activos (es decir, marcados), se los mueve a la primera dirección baja disponible y se agrega un registro a una tabla de ruptura con información de reubicación. Para cada objeto activo, un registro en la tabla de ruptura consta de 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 ruptura se almacena en el montón que se está compactando, pero en un área que está marcada como no utilizada. Para garantizar que la compactación siempre se realice correctamente, el tamaño mínimo de objeto en el montón debe ser mayor o igual que un registro de la tabla de ruptura.
A medida que avanza la compactación, los objetos reubicados se copian hacia la parte inferior del montón. Finalmente, será necesario copiar un objeto al espacio ocupado por la tabla de ruptura, que ahora debe reubicarse en otro lugar. Estos movimientos de la tabla de ruptura (a los que los autores denominan " rodar la tabla ") hacen que los registros de reubicación se desordenen, lo que requiere que la tabla de ruptura se ordene una vez que se completa la compactación. El costo de ordenar la tabla de ruptura es O ( n log n ), donde n es la cantidad de objetos activos que se encontraron en la etapa de marcado del algoritmo.
Por último, los registros de reubicación de la tabla de ruptura se utilizan para ajustar los campos de puntero dentro de los objetos reubicados. Los objetos activos se examinan en busca de punteros, que se pueden buscar en la tabla de ruptura ordenada de tamaño n en un tiempo O(log n ) si la tabla de ruptura está ordenada, para un tiempo de ejecución total de O ( n log n ). Luego, los punteros se ajustan según la cantidad especificada en la tabla de reubicación.
Para evitar la complejidad O ( n log n ), el algoritmo LISP 2 utiliza tres pasadas diferentes por 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.
Después de la calificación estándar, el algoritmo continúa en los siguientes tres pasos:
Este algoritmo es O ( n ) en cuanto al tamaño del montón; tiene una mejor complejidad que el enfoque basado en tablas, pero la n del enfoque basado en tablas es solo 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 simple de implementar.
El algoritmo de compactación Compressor [2] tiene la menor complejidad entre los algoritmos de compactación conocidos en la actualidad. 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 anterior 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 comienzo 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 resultar muy eficiente si se trabaja con tablas pequeñas que no requieren una pasada por todo el montón. Esto mantiene baja la complejidad del compresor, ya que implica una pasada por tablas pequeñas y una pasada por todo el montón. Esta representa la complejidad más conocida para los algoritmos de compactación.
El compresor también tiene una versión paralela en la que varios subprocesos de compactación pueden trabajar juntos para compactar todos los objetos en paralelo. El compresor también tiene una versión concurrente en la que los subprocesos de compactación pueden trabajar simultáneamente con el programa, lo que permite que el programa acceda cuidadosamente a los objetos a medida que se mueven hacia el comienzo del montón. Las versiones paralela y concurrente del compresor utilizan primitivas de memoria virtual.