Recogida de basura (informática)

El recolector de basura libera al programador de la necesidad de liberar manualmente la memoria. Esto ayuda a evitar algunos tipos de errores : ^{[ 8 ]}

• Punteros colgantes , que ocurren cuando se libera una porción de memoria mientras aún existen punteros que apuntan a ella, y uno de esos punteros se desreferencia . Para entonces, la memoria puede haber sido reasignada a otro uso, con resultados impredecibles. ^{[ 9 ]}
• Errores de doble liberación , que ocurren cuando el programa intenta liberar una región de memoria que ya ha sido liberada y, posiblemente, ya ha sido asignada de nuevo.
• Ciertos tipos de fugas de memoria , en las que un programa no logra liberar la memoria ocupada por objetos que se han vuelto inaccesibles , pueden provocar un agotamiento de la memoria. ^{[ 10 ]}

GC utiliza recursos informáticos para decidir qué memoria liberar. Por lo tanto, la penalización por la comodidad de no anotar manualmente la vida útil de los objetos en el código fuente es una sobrecarga , que puede perjudicar el rendimiento del programa. ^{[ 11 ]} Un artículo revisado por pares de 2005 concluyó que GC necesita cinco veces más memoria para compensar esta sobrecarga y funcionar tan rápido como el mismo programa utilizando una gestión de memoria explícita idealizada. Sin embargo, la comparación se realiza con un programa generado insertando llamadas de desasignación usando un oráculo , implementado mediante la recopilación de trazas de programas ejecutados bajo un perfilador , y el programa solo es correcto para una ejecución particular del programa. ^{[ 12 ]} La interacción con los efectos de la jerarquía de memoria puede hacer que esta sobrecarga sea intolerable en circunstancias que son difíciles de predecir o detectar en las pruebas rutinarias. Apple dio el impacto en el rendimiento como una razón para no adoptar la recolección de basura en iOS , a pesar de ser la característica más deseada. ^{[ 13 ]}

El momento en que se recoge la basura puede ser impredecible, lo que provoca pausas (debido a la liberación de memoria) a lo largo de la sesión . Estas pausas impredecibles pueden ser inaceptables en entornos en tiempo real , en el procesamiento de transacciones o en programas interactivos. Los recolectores de basura incrementales, concurrentes y en tiempo real abordan estos problemas, con diferentes ventajas e inconvenientes.

La recolección de basura por rastreo es el tipo más común de recolección de basura, tanto que el término "recolección de basura" a menudo se refiere a este método, en lugar de otros como el conteo de referencias . La estrategia general consiste en determinar qué objetos deben ser recolectados rastreando cuáles son accesibles mediante una cadena de referencias desde ciertos objetos raíz, y considerando el resto como basura y recolectándolos. ^{[ 14 ]} Sin embargo, existe una gran cantidad de algoritmos utilizados en la implementación, con características de complejidad y rendimiento muy variables.

La recolección de basura por conteo de referencias consiste en que cada objeto tiene un contador que indica el número de referencias que recibe. La basura se identifica por tener un contador de referencias de cero. El contador de referencias de un objeto se incrementa cuando se crea una referencia a él y se decrementa cuando se destruye una referencia. Cuando el contador llega a cero, se recupera la memoria del objeto. ^{[ 15 ]}

Al igual que con la gestión manual de la memoria, y a diferencia de la recolección de basura por rastreo, el conteo de referencias garantiza que los objetos se destruyan tan pronto como se destruya su última referencia, y generalmente solo accede a la memoria que se encuentra en las cachés de la CPU , en objetos que se van a liberar o a la que apuntan directamente estos, por lo que tiende a no tener efectos secundarios negativos significativos en el funcionamiento de la caché de la CPU y la memoria virtual .

El conteo de referencias presenta varias desventajas; esto generalmente se puede solucionar o mitigar mediante algoritmos más sofisticados:

Ciclos

Si dos o más objetos se referencian entre sí, pueden crear un ciclo en el que ninguno será recolectado ya que sus referencias mutuas nunca permiten que sus contadores de referencia lleguen a cero. Algunos sistemas de recolección de basura que utilizan el conteo de referencias (como el de CPython ) utilizan algoritmos específicos de detección de ciclos para abordar este problema. ^{[ 16 ]} Otra estrategia es usar referencias débiles para los "backpointers" que crean ciclos. Bajo el conteo de referencias, una referencia débil es similar a una referencia débil bajo un recolector de basura de rastreo. Es un objeto de referencia especial cuya existencia no incrementa el contador de referencias del objeto de referencia. Además, una referencia débil es segura en el sentido de que cuando el objeto de referencia se convierte en basura, cualquier referencia débil a él caduca , en lugar de permitirse que permanezca colgante, lo que significa que se convierte en un valor predecible, como una referencia nula.

Espacio sobrante (recuento de referencias)

El conteo de referencias requiere que se asigne espacio para cada objeto para almacenar su contador de referencias. El contador puede almacenarse adyacente a la memoria del objeto o en una tabla lateral en otro lugar, pero en cualquier caso, cada objeto con conteo de referencias requiere almacenamiento adicional para su contador de referencias. El espacio de memoria del tamaño de un puntero sin signo se usa comúnmente para esta tarea, lo que significa que se deben asignar 32 o 64 bits de almacenamiento de conteo de referencias para cada objeto. En algunos sistemas, puede ser posible mitigar esta sobrecarga usando un puntero etiquetado para almacenar el conteo de referencias en áreas no utilizadas de la memoria del objeto. A menudo, una arquitectura no permite que los programas accedan al rango completo de direcciones de memoria que podrían almacenarse en el tamaño nativo de su puntero; una cierta cantidad de bits altos en la dirección se ignora o se requiere que sea cero. Si un objeto tiene de manera confiable un puntero en una ubicación determinada, el conteo de referencias se puede almacenar en los bits no utilizados del puntero. Por ejemplo, cada objeto en Objective-C tiene un puntero a su clase al principio de su memoria; En la arquitectura ARM64 que utiliza iOS 7 , 19 bits no utilizados de este puntero de clase se utilizan para almacenar el contador de referencias del objeto. ^{[ 17 ] [ 18 ]}

Incremento/decremento de velocidad

En implementaciones ingenuas, cada asignación de una referencia y cada referencia que sale del ámbito a menudo requiere modificaciones de uno o más contadores de referencias. Sin embargo, en un caso común, cuando una referencia se copia de una variable de ámbito externo a una variable de ámbito interno, de manera que la vida útil de la variable interna está limitada por la vida útil de la externa, se puede eliminar el incremento de la referencia. La variable externa "posee" la referencia. En el lenguaje de programación C++, esta técnica se implementa fácilmente y se demuestra con el uso de constreferencias. El conteo de referencias en C++ generalmente se implementa usando " punteros inteligentes " ^{[ 19 ]} cuyos constructores, destructores y operadores de asignación administran las referencias. Un puntero inteligente se puede pasar por referencia a una función, lo que evita la necesidad de copiar un nuevo puntero inteligente (lo que aumentaría el contador de referencias al entrar en la función y lo disminuiría al salir). En cambio, la función recibe una referencia al puntero inteligente que se produce de forma económica. El método Deutsch-Bobrow de conteo de referencias aprovecha el hecho de que la mayoría de las actualizaciones del contador de referencias son generadas por referencias almacenadas en variables locales. Ignora estas referencias, solo cuenta las referencias en el montón, pero antes de que se pueda eliminar un objeto con contador de referencias cero, el sistema debe verificar con un escaneo de la pila y el registro que no exista ninguna otra referencia a él. Se puede obtener una disminución sustancial adicional en la sobrecarga en las actualizaciones del contador mediante la coalescencia de actualizaciones introducida por Levanoni y Petrank . ^{[ 20 ] [ 21 ]} Considere un puntero que en un intervalo dado de la ejecución se actualiza varias veces. Primero apunta a un objeto O1, luego a un objeto O2, y así sucesivamente hasta que al final del intervalo apunta a algún objeto On. Un algoritmo de conteo de referencias normalmente ejecutaría rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Pero la mayoría de estas actualizaciones son redundantes. Para que el contador de referencias se evalúe correctamente al final del intervalo, es suficiente con realizar rc(O1)--y rc(On)++. Levanoni y Petrank midieron una eliminación de más del 99% de las actualizaciones del contador en los benchmarks típicos de Java.

Requiere atomicidad

Cuando se utilizan en un entorno multihilo , estas modificaciones (incremento y decremento) pueden necesitar ser operaciones atómicas como comparar e intercambiar , al menos para cualquier objeto que sea compartido, o potencialmente compartido entre múltiples hilos. Las operaciones atómicas son costosas en un multiprocesador, y aún más costosas si tienen que ser emuladas con algoritmos de software. Es posible evitar este problema agregando contadores de referencias por hilo o por CPU y accediendo al contador de referencias global solo cuando los contadores de referencias locales se vuelven o dejan de ser cero (o, alternativamente, usando un árbol binario de contadores de referencias, o incluso renunciando a la destrucción determinista a cambio de no tener ningún contador de referencias global), pero esto agrega una sobrecarga de memoria significativa y, por lo tanto, tiende a ser útil solo en casos especiales (se usa, por ejemplo, en el conteo de referencias de los módulos del kernel de Linux). La coalescencia de actualizaciones de Levanoni y Petrank ^{[ 20 ] [ 21 ]} puede usarse para eliminar todas las operaciones atómicas de la barrera de escritura. Los contadores nunca son actualizados por los hilos del programa durante su ejecución. Solo los modifica el recolector, que se ejecuta como un hilo adicional sin sincronización. Este método puede utilizarse como mecanismo de detención global para programas paralelos, así como con un recolector de conteo de referencias concurrente.

No es en tiempo real.

Las implementaciones simples de conteo de referencias generalmente no ofrecen un comportamiento en tiempo real, ya que cualquier asignación de puntero puede provocar la liberación recursiva de un número de objetos limitado únicamente por el tamaño total de la memoria asignada, mientras el hilo no puede realizar otras tareas. Es posible evitar este problema delegando la liberación de objetos sin referencias a otros hilos, aunque esto conlleva una sobrecarga adicional.

El análisis de escape es una técnica de compilación que permite convertir las asignaciones de memoria dinámica (heap) en asignaciones de memoria estática (stack) , reduciendo así la cantidad de recolección de basura necesaria. Este análisis determina si un objeto asignado dentro de una función es accesible fuera de ella. Si se detecta que una asignación local a una función es accesible desde otra función o hilo, se dice que la asignación "escapa" y no puede realizarse en la pila. De lo contrario, el objeto puede asignarse directamente en la pila y liberarse cuando la función finaliza, evitando así el heap y los costos de administración de memoria asociados. ^{[ 22 ]}

BASIC y Logo a menudo han utilizado la recolección de basura para tipos de datos de longitud variable, como cadenas y listas, para no sobrecargar a los programadores con detalles de administración de memoria. En el Altair 8800 , los programas con muchas variables de cadena y poco espacio para cadenas podían causar largas pausas debido a la recolección de basura. ^{[ 25 ]} De manera similar, el algoritmo de recolección de basura del intérprete Applesoft BASIC escanea repetidamente los descriptores de cadena para encontrar la cadena con la dirección más alta con el fin de compactarla hacia la memoria alta, lo que resulta en${\displaystyle O(n^{2})}$rendimiento ^{[ 26 ]} y pausas de unos pocos segundos a unos pocos minutos. ^{[ 27 ]} Un recolector de basura de reemplazo para Applesoft BASIC por Randy Wigginton identifica un grupo de cadenas en cada pasada sobre el montón, reduciendo drásticamente el tiempo de recolección. ^{[ 28 ]} BASIC.SYSTEM, lanzado con ProDOS en 1983 proporciona un recolector de basura de ventana para BASIC que es muchas veces más rápido. ^{[ 29 ]}

C nunca ha ofrecido soporte oficial para la recolección de basura. C++ añadió soporte para la recolección de basura en C++11 a la biblioteca estándar; sin embargo, esto se eliminó en C++23 debido a que ningún compilador implementó soporte para la característica. ^{[ 30 ]} Las características que formaban parte de esto estaban relacionadas con la seguridad de los punteros. ^{[ 31 ]}

Aunque se eliminó la compatibilidad con la recolección de basura en la biblioteca estándar, todavía se pueden usar algunos recolectores de basura como el recolector de basura Boehm (para C y C++). Boehm GC utiliza la recolección de basura con rastreo . También se puede usar en modo de detección de fugas, donde la administración de memoria sigue siendo manual, pero se pueden detectar y reportar fugas y errores de doble liberación. Su uso se puede llamar desde el encabezado <gc.h>.

En C++, aún se pueden abstraer las destrucciones manuales de objetos mediante el uso del patrón " adquisición de recursos es inicialización " (RAII) y punteros inteligentes . std::unique_ptrvincula la vida útil a la propiedad, mientras que std::shared_ptrutiliza el conteo de referencias para determinar la vida útil. std::weak_ptrse puede usar para obtener un puntero sin aumentar el contador de referencias. A diferencia de la recolección de basura, RAII es determinista.

Aunque Objective-C tradicionalmente no tenía recolección de basura, con el lanzamiento de OS X 10.5 en 2007, Apple introdujo la recolección de basura para Objective-C  2.0, utilizando un recolector de tiempo de ejecución desarrollado internamente. ^{[ 32 ]} Sin embargo, con el lanzamiento de OS X 10.8 en 2012 , la recolección de basura quedó obsoleta en favor del contador de referencias automático (ARC) de LLVM , que se introdujo con OS X 10.7 . ^{[ 33 ]} Además, desde mayo de 2015, Apple incluso prohibió el uso de la recolección de basura para las nuevas aplicaciones de OS X en la App Store . ^{[ 34 ] [ 35 ]} Para iOS , la recolección de basura nunca se ha introducido debido a problemas en la capacidad de respuesta y el rendimiento de las aplicaciones; ^{[ 13 ] [ 36 ]} en su lugar, iOS utiliza ARC. ^{[ 37 ] [ 38 ]} 

La recolección de basura rara vez se utiliza en sistemas embebidos o en tiempo real debido a la necesidad habitual de un control muy estricto sobre el uso de recursos limitados. Sin embargo, se han desarrollado recolectores de basura compatibles con muchos entornos limitados. ^{[ 39 ]} Microsoft .NET Micro Framework , .NET nanoFramework ^{[ 40 ]} y Java Platform, Micro Edition son plataformas de software embebido que, al igual que sus versiones más grandes, incluyen recolección de basura.

Los recolectores de basura disponibles en la máquina virtual (JVM) de Java OpenJDK incluyen:

• De serie
• Paralelo
• CMS (Barrido de Marcas Concurrente)
• G1 (Primero la basura)
• ZGC (Recolector de basura Z)
• Épsilon
• Shenandoah
• GenZGC (Generación ZGC)
• GenShen (Shenandoah generacional)
• Metrónomo de IBM (solo en IBM OpenJDK)
• SAP (solo en SAP OpenJDK)
• Azul C4 (Recolector de compactación concurrente continua) ^{[ 41 ]} (solo en Azul Systems OpenJDK)

La recolección de basura en tiempo de compilación es una forma de análisis estático que permite reutilizar y recuperar la memoria basándose en invariantes conocidas durante la compilación.

Esta forma de recolección de basura se ha estudiado en el lenguaje de programación Mercury , ^{[ 42 ]} y tuvo un mayor uso con la introducción del contador de referencias automático (ARC) de LLVM en el ecosistema de Apple (iOS y OS X) en 2011. ^{[ 37 ] [ 38 ] [ 34 ]} 

Se han desarrollado recolectores de basura incrementales, concurrentes y en tiempo real, por ejemplo por Henry Baker y por Henry Lieberman . ^{[ 43 ] [ 44 ] [ 45 ]}

En el algoritmo de Baker, la asignación se realiza en una de las dos mitades de una única región de memoria. Cuando esta se llena a la mitad, se ejecuta una recolección de basura que mueve los objetos activos a la otra mitad, mientras que los objetos restantes se desasignan implícitamente. El programa en ejecución (el "mutador") debe verificar que cualquier objeto al que haga referencia se encuentre en la mitad correcta y, de no ser así, moverlo a la otra mitad, mientras una tarea en segundo plano busca todos los objetos. ^{[ 46 ]}

Los esquemas de recolección de basura generacional se basan en la observación empírica de que la mayoría de los objetos mueren jóvenes. En la recolección de basura generacional, se mantienen dos o más regiones de asignación (generaciones), separadas según la antigüedad del objeto. Los objetos nuevos se crean en la generación "joven", que se recolecta regularmente, y cuando una generación está llena, los objetos que aún se referencian desde regiones más antiguas se copian a la siguiente generación más antigua. Ocasionalmente, se realiza un escaneo completo.

Algunas arquitecturas informáticas de lenguajes de alto nivel incluyen soporte de hardware para la recolección de basura en tiempo real.

La mayoría de las implementaciones de recolectores de basura en tiempo real utilizan rastreo . Dichos recolectores de basura en tiempo real cumplen con las estrictas restricciones de tiempo real cuando se utilizan con un sistema operativo en tiempo real. ^{[ 47 ]}