Seguimiento de la recolección de basura

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo necesita citas adicionales para su verificación .Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Rastreando la recolección de basura» – noticias  · periódicos  · libros  · académico  · JSTOR ( Julio de 2016 )( Aprenda cómo y cuándo eliminar este mensaje ) This article's lead section may be too short to adequately summarize the key points. Please consider expanding the lead to provide an accessible overview of all important aspects of the article. (March 2024) (Learn how and when to remove this message)

En programación informática , la recolección de basura por rastreo es una forma de gestión automática de memoria que consiste en determinar qué objetos deben desasignarse ("recolección de basura") rastreando qué objetos son alcanzables por una cadena de referencias desde ciertos objetos "raíz", y considerando el resto como "basura" y recogiéndolos. El rastreo es el tipo más común de recolección de basura -tanto es así que "recolección de basura" a menudo se refiere al método de rastreo, en lugar de otros como el conteo de referencias- y hay una gran cantidad de algoritmos utilizados en la implementación.

De manera informal, un objeto es alcanzable si al menos una variable del programa hace referencia a él, ya sea directamente o a través de referencias de otros objetos alcanzables. Más precisamente, los objetos pueden ser alcanzables de solo dos maneras:

1. Un conjunto distinguido de raíces: objetos que se supone que son accesibles. Por lo general, estos incluyen todos los objetos a los que se hace referencia desde cualquier lugar de la pila de llamadas (es decir, todas las variables y parámetros locales en las funciones que se invocan actualmente) y cualquier variable global .
2. Cualquier cosa a la que se haga referencia desde un objeto alcanzable es en sí misma alcanzable; más formalmente, la alcanzabilidad es un cierre transitivo .

La definición de accesibilidad de "basura" no es óptima, en la medida en que la última vez que un programa utiliza un objeto podría ser mucho antes de que ese objeto quede fuera del ámbito del entorno. A veces se hace una distinción entre basura sintáctica , aquellos objetos que el programa no puede alcanzar, y basura semántica , aquellos objetos que el programa de hecho nunca volverá a utilizar. Por ejemplo:

Objeto x = new Foo (); Objeto y = new Bar (); x = new Quux (); /* En este punto, sabemos que el objeto Foo * originalmente asignado a x nunca será * accedido: es basura sintáctica. */           /* En el siguiente bloque, y *podría* ser basura semántica; * pero no lo sabremos hasta que x.check_something() devuelva * algún valor, si es que lo devuelve. */ if ( x . check_something ()) { x . do_something ( y ); } System . exit ( 0 );   

Se puede demostrar fácilmente que el problema de identificar con precisión la basura semántica es parcialmente decidible : un programa que asigna un objeto , ejecuta un programa de entrada arbitrario y utiliza if y only if termina requeriría un recolector de basura semántica para resolver el problema de la detención . Aunque los métodos heurísticos conservadores para la detección de basura semántica siguen siendo un área de investigación activa, esencialmente todos los recolectores de basura prácticos se centran en la basura sintáctica. ^{[ cita requerida ]}${\displaystyle X}$${\displaystyle P}$${\displaystyle X}$${\displaystyle P}$

Otra complicación con este enfoque es que, en lenguajes con tipos de referencia y tipos de valor no encapsulados , el recolector de basura necesita poder distinguir de alguna manera qué variables en la pila o campos en un objeto son valores regulares y cuáles son referencias: en la memoria, un entero y una referencia pueden parecer iguales. El recolector de basura necesita entonces saber si debe tratar el elemento como una referencia y seguirlo, o si es un valor primitivo. Una solución común es el uso de punteros etiquetados .

El recolector de basura puede recuperar únicamente objetos que no tengan referencias que apunten a ellos, ya sea directa o indirectamente, desde el conjunto raíz. Sin embargo, algunos programas requieren referencias débiles , que deberían ser utilizables mientras exista el objeto, pero no deberían prolongar su vida útil. En las discusiones sobre referencias débiles, las referencias ordinarias a veces se denominan referencias fuertes . Un objeto es elegible para la recolección de basura si no hay referencias fuertes (es decir, ordinarias) a él, aunque aún pueda haber algunas referencias débiles a él.

Una referencia débil no es simplemente cualquier puntero al objeto que no le interesa al recolector de basura. El término suele reservarse para una categoría administrada adecuadamente de objetos de referencia especiales que son seguros de usar incluso después de que el objeto desaparezca porque caducan a un valor seguro (normalmente null). Una referencia insegura que no es conocida por el recolector de basura simplemente permanecerá inactiva al seguir haciendo referencia a la dirección donde residía el objeto anteriormente. Esta no es una referencia débil.

En algunas implementaciones, las referencias débiles se dividen en subcategorías. Por ejemplo, la máquina virtual Java proporciona tres formas de referencias débiles, a saber, referencias suaves , ^[1] referencias fantasma , ^[2] y referencias débiles regulares. ^[3] Un objeto referenciado suavemente solo es elegible para recuperación si el recolector de basura decide que el programa tiene poca memoria. A diferencia de una referencia suave o una referencia débil regular, una referencia fantasma no proporciona acceso al objeto al que hace referencia. En cambio, una referencia fantasma es un mecanismo que permite al recolector de basura notificar al programa cuando el objeto referenciado se ha vuelto alcanzable fantasma . Un objeto es alcanzable fantasma si aún reside en la memoria y es referenciado por una referencia fantasma, pero su finalizador ya se ha ejecutado. De manera similar, Microsoft.NET proporciona dos subcategorías de referencias débiles, ^[4] a saber, referencias débiles largas (rastrea la resurrección) y referencias débiles cortas.

También se pueden diseñar estructuras de datos que tengan características de seguimiento débiles. Por ejemplo, las tablas hash débiles son útiles. Al igual que una tabla hash normal, una tabla hash débil mantiene una asociación entre pares de objetos, donde cada par se entiende como una clave y un valor. Sin embargo, la tabla hash en realidad no mantiene una referencia fuerte sobre estos objetos. Se produce un comportamiento especial cuando la clave o el valor o ambos se convierten en basura: la entrada de la tabla hash se elimina espontáneamente. Existen otros refinamientos, como las tablas hash que solo tienen claves débiles (las referencias de valor son referencias fuertes ordinarias) o solo valores débiles (las referencias de clave son fuertes).

Las tablas hash débiles son importantes para mantener asociaciones entre objetos, de modo que los objetos involucrados en la asociación aún pueden convertirse en basura si nada en el programa hace referencia a ellos (excepto la tabla hash asociada).

El uso de una tabla hash regular para tal propósito podría llevar a una "fuga de memoria lógica": la acumulación de datos accesibles que el programa no necesita y no utilizará.

Los recolectores de rastreo se denominan así porque rastrean el conjunto de trabajo de la memoria. Estos recolectores de basura realizan la recolección en ciclos. Es común que los ciclos se activen cuando no hay suficiente memoria libre para que el administrador de memoria satisfaga una solicitud de asignación. Pero los ciclos a menudo pueden ser solicitados directamente por el mutador o ejecutarse según un cronograma. El método original implica un marcado y barrido ingenuo en el que se toca todo el conjunto de memoria varias veces.

En el método ingenuo de marcado y barrido, cada objeto en la memoria tiene un indicador (normalmente un solo bit) reservado únicamente para la recolección de basura. Este indicador siempre se borra , excepto durante el ciclo de recolección.

La primera etapa es la etapa de marcado , que realiza un recorrido en árbol de todo el "conjunto raíz" y marca cada objeto al que apunta una raíz como "en uso". Todos los objetos a los que apuntan esos objetos, y así sucesivamente, también se marcan, de modo que cada objeto al que se puede acceder a través del conjunto raíz está marcado.

En la segunda etapa, la etapa de barrido , se escanea toda la memoria de principio a fin, examinando todos los bloques libres o usados; aquellos que no están marcados como "en uso" no son accesibles por ninguna raíz, y su memoria se libera. Para los objetos que estaban marcados como "en uso", se borra la bandera de "en uso", preparándose para el siguiente ciclo.

Este método tiene varias desventajas, la más notable es que todo el sistema debe suspenderse durante la recolección; no se puede permitir ninguna mutación del conjunto de trabajo. Esto puede hacer que los programas se "congelen" periódicamente (y generalmente de manera impredecible), lo que hace imposible el funcionamiento de algunas aplicaciones en tiempo real y críticas en el tiempo. Además, se debe examinar toda la memoria de trabajo, gran parte de ella dos veces, lo que puede causar problemas en los sistemas de memoria paginada .

Debido a estos problemas de rendimiento, la mayoría de los recolectores de basura de rastreo modernos implementan alguna variante de la abstracción de marcado tricolor , pero los recolectores simples (como el recolector de marcado y barrido ) a menudo no hacen explícita esta abstracción. El marcado tricolor funciona como se describe a continuación.

Se crean tres conjuntos: blanco , negro y gris :

• El conjunto blanco, o conjunto condenado , es el conjunto de objetos que son candidatos a que se recicle su memoria.
• El conjunto negro es el conjunto de objetos que se puede demostrar que no tienen referencias salientes a objetos del conjunto blanco y que se puede acceder a ellos desde las raíces. Los objetos del conjunto negro no son candidatos para la colección.
• El conjunto gris contiene todos los objetos a los que se puede acceder desde las raíces pero que aún no se han escaneado en busca de referencias a objetos "blancos". Dado que se sabe que se puede acceder a ellos desde las raíces, no se pueden recolectar como basura y terminarán en el conjunto negro después de escanearlos.

En muchos algoritmos, el conjunto negro comienza vacío, el conjunto gris es el conjunto de objetos a los que se hace referencia directamente desde las raíces y el conjunto blanco incluye todos los demás objetos. Cada objeto en la memoria está en todo momento en exactamente uno de los tres conjuntos. El algoritmo procede de la siguiente manera:

1. Elige un objeto del conjunto gris
2. Mueva cada objeto blanco al que haga referencia o al conjunto gris. Esto garantiza que ni este objeto ni ningún otro objeto al que haga referencia puedan ser recolectados como basura.
3. Mueva o al conjunto negro
4. Repita los últimos tres pasos hasta que el conjunto gris esté vacío.

Cuando el conjunto gris está vacío, el escaneo está completo; los objetos negros son accesibles desde las raíces, mientras que los objetos blancos no y pueden recolectarse como basura.

Dado que todos los objetos que no son inmediatamente accesibles desde las raíces se agregan al conjunto blanco, y los objetos solo pueden moverse de blanco a gris y de gris a negro, el algoritmo conserva una invariante importante: ningún objeto negro hace referencia a objetos blancos. Esto garantiza que los objetos blancos se puedan liberar una vez que el conjunto gris esté vacío. Esto se denomina invariante tricolor . Algunas variaciones del algoritmo no conservan esta invariante, sino que utilizan una forma modificada para la que se mantienen todas las propiedades importantes.

El método tricolor tiene una ventaja importante: se puede ejecutar "sobre la marcha", sin detener el sistema durante períodos de tiempo significativos. Esto se logra marcando los objetos a medida que se asignan y durante la mutación, manteniendo los distintos conjuntos. Al monitorear el tamaño de los conjuntos, el sistema puede realizar la recolección de basura periódicamente, en lugar de hacerlo cuando sea necesario. Además, se evita la necesidad de tocar todo el conjunto de trabajo en cada ciclo.

Una vez que se ha determinado el conjunto inalcanzable, el recolector de basura puede simplemente liberar los objetos inalcanzables y dejar todo lo demás como está, o puede copiar algunos o todos los objetos alcanzables en una nueva área de memoria, actualizando todas las referencias a esos objetos según sea necesario. Estos se denominan recolectores de basura "no móviles" y "móviles" (o, alternativamente, "no compactadores" y "compactadores"), respectivamente.

En un primer momento, un algoritmo móvil puede parecer ineficiente en comparación con uno inmóvil, ya que parecería requerirse mucho más trabajo en cada ciclo. Pero el algoritmo móvil conlleva varias ventajas de rendimiento, tanto durante el ciclo de recolección de basura como durante la ejecución del programa:

• No se requiere trabajo adicional para recuperar el espacio liberado por los objetos muertos; toda la región de memoria desde la que se movieron los objetos alcanzables se puede considerar espacio libre. Por el contrario, un GC que no se mueve debe visitar cada objeto inalcanzable y registrar que la memoria que ocupaba está disponible.
• De manera similar, se pueden asignar nuevos objetos muy rápidamente. Dado que las regiones contiguas de memoria grandes suelen estar disponibles mediante un GC en movimiento, se pueden asignar nuevos objetos simplemente incrementando un puntero de "memoria libre". Una estrategia sin movimiento puede, después de un tiempo, generar un montón muy fragmentado , lo que requiere una consulta costosa de "listas libres" de pequeños bloques de memoria disponibles para asignar nuevos objetos.
• Si se utiliza un orden de recorrido adecuado (como cdr-first para listas conses ), los objetos se pueden mover muy cerca de los objetos a los que hacen referencia en la memoria, lo que aumenta la posibilidad de que se ubiquen en la misma línea de caché o página de memoria virtual . Esto puede acelerar significativamente el acceso a estos objetos a través de estas referencias.

Una desventaja de un recolector de basura móvil es que solo permite el acceso a través de referencias que son administradas por el entorno de recolección de basura, y no permite la aritmética de punteros . Esto se debe a que cualquier puntero a objetos se invalidará si el recolector de basura mueve esos objetos (se convierten en punteros colgantes ). Para la interoperabilidad con el código nativo, el recolector de basura debe copiar el contenido del objeto a una ubicación fuera de la región de memoria recolectada. Un enfoque alternativo es fijar el objeto en la memoria, evitando que el recolector de basura lo mueva y permitiendo que la memoria se comparta directamente con punteros nativos (y posiblemente permitiendo la aritmética de punteros). ^[5]

Los coleccionistas no solo se diferencian en si son móviles o no, sino que también pueden clasificarse por cómo tratan los conjuntos de objetos blancos, grises y negros durante un ciclo de colección.

El método más sencillo es el colector semiespacial , que data de 1969. En este colector móvil, la memoria se divide en un "espacio de origen" y un "espacio de destino" de igual tamaño. Inicialmente, los objetos se asignan en el "espacio de destino" hasta que se llena y se activa un ciclo de recopilación. Al comienzo del ciclo, el "espacio de destino" se convierte en el "espacio de origen", y viceversa. Los objetos alcanzables desde el conjunto raíz se copian del "espacio de origen" al "espacio de destino". Estos objetos se escanean a su vez, y todos los objetos a los que apuntan se copian en el "espacio de destino", hasta que todos los objetos alcanzables se hayan copiado en el "espacio de destino". Una vez que el programa continúa la ejecución, se vuelven a asignar nuevos objetos en el "espacio de destino" hasta que se llena nuevamente y se repite el proceso.

Este enfoque es muy simple, pero como solo se utiliza un semiespacio para asignar objetos, el uso de memoria es el doble en comparación con otros algoritmos. La técnica también se conoce como stop-and-copy . El algoritmo de Cheney es una mejora del recolector de semiespacio.

Un recolector de basura de marcado y barrido conserva uno o dos bits con cada objeto para registrar si es blanco o negro. El conjunto gris se conserva como una lista separada o utilizando otro bit. A medida que se recorre el árbol de referencia durante un ciclo de recolección (la fase de "marcado"), el recolector manipula estos bits. Luego, un "barrido" final de las áreas de memoria libera los objetos blancos. La estrategia de marcado y barrido tiene la ventaja de que, una vez que se determina el conjunto condenado, se puede seguir una estrategia de recolección en movimiento o inmóvil. Esta elección de estrategia se puede realizar en tiempo de ejecución, según lo permita la memoria disponible. Tiene la desventaja de "inflar" los objetos en una pequeña cantidad, como en el caso de que cada objeto tenga un pequeño costo de memoria oculta debido a la lista/bit adicional. Esto se puede mitigar en cierta medida si el recolector también maneja la asignación, ya que entonces podría usar bits no utilizados en las estructuras de datos de asignación. O bien, esta "memoria oculta" se puede eliminar utilizando un puntero etiquetado , intercambiando el costo de memoria por tiempo de CPU. Sin embargo, la estrategia de marcar y barrer es la única que coopera fácilmente con los asignadores externos en primer lugar.

Un recolector de basura de marca y no barrido , como el de marca y barrido, mantiene un bit con cada objeto para registrar si es blanco o negro; el conjunto gris se mantiene como una lista separada o utilizando otro bit. Aquí hay dos diferencias clave. Primero, negro y blanco significan cosas diferentes a las que significan en el recolector de marca y barrido. En un recolector de "marca y no barrido", todos los objetos alcanzables son siempre negros. Un objeto se marca como negro en el momento en que se asigna, y seguirá siendo negro incluso si se vuelve inalcanzable. Un objeto blanco es memoria sin usar y puede ser asignada. Segundo, la interpretación del bit negro/blanco puede cambiar. Inicialmente, el bit negro/blanco puede tener el sentido de (0=blanco, 1=negro). Si una operación de asignación no logra encontrar memoria disponible (blanca), eso significa que todos los objetos están marcados como usados ​​(negros). El sentido del bit negro/blanco se invierte entonces (por ejemplo, 0=negro, 1=blanco). Todo se vuelve blanco. Esto rompe momentáneamente la invariancia de que los objetos alcanzables son negros, pero inmediatamente sigue una fase de marcado completa para marcarlos nuevamente en negro. Una vez que esto se hace, toda la memoria inalcanzable es blanca. No es necesaria ninguna fase de "barrido".

La estrategia de marcar y no barrer requiere la cooperación entre el asignador y el recolector, pero es increíblemente eficiente en términos de espacio, ya que solo requiere un bit por puntero asignado (que es lo que la mayoría de los algoritmos de asignación requieren de todos modos). Sin embargo, esta ventaja se mitiga un poco, ya que la mayoría de las veces, grandes porciones de memoria se marcan erróneamente en negro (usadas), lo que dificulta devolver recursos al sistema (para que los usen otros asignadores, subprocesos o procesos) en momentos de bajo uso de memoria.

Por lo tanto, la estrategia de marcar y no barrer puede verse como un compromiso entre las ventajas y desventajas de las estrategias de marcar y barrer y las de detener y copiar.

Se ha observado empíricamente que en muchos programas, los objetos creados más recientemente son también los que tienen más probabilidades de volverse inalcanzables rápidamente (lo que se conoce como mortalidad infantil o hipótesis generacional ). Un recolector de basura generacional (también conocido como recolector de basura efímero) divide los objetos en generaciones y, en la mayoría de los ciclos, colocará solo los objetos de un subconjunto de generaciones en el conjunto blanco inicial (condenado). Además, el sistema en tiempo de ejecución mantiene el conocimiento de cuándo las referencias cruzan generaciones al observar la creación y sobrescritura de referencias. Cuando se ejecuta el recolector de basura, puede usar este conocimiento para demostrar que algunos objetos en el conjunto blanco inicial son inalcanzables sin tener que recorrer todo el árbol de referencias. Si se cumple la hipótesis generacional, esto da como resultado ciclos de recolección mucho más rápidos y, al mismo tiempo, recupera la mayoría de los objetos inalcanzables.

Para implementar este concepto, muchos recolectores de basura generacionales utilizan regiones de memoria separadas para diferentes edades de objetos. Cuando una región se llena, se rastrean los objetos que contiene, utilizando las referencias de las generaciones anteriores como raíces. Esto generalmente da como resultado que se recopilen la mayoría de los objetos de la generación (por la hipótesis), y se deja que se utilice para asignar nuevos objetos. Cuando una colección no recopila muchos objetos (la hipótesis no se cumple, por ejemplo, porque el programa ha calculado una gran colección de nuevos objetos que desea conservar), algunos o todos los objetos supervivientes a los que se hace referencia desde regiones de memoria más antiguas se promueven a la siguiente región más alta, y luego se puede sobrescribir toda la región con objetos nuevos. Esta técnica permite una recolección de basura incremental muy rápida, ya que la recolección de basura de una sola región a la vez es todo lo que normalmente se requiere.

El clásico buscador de generaciones de Ungar tiene dos generaciones. Divide la generación más joven, llamada "espacio nuevo", en un gran "edén" en el que se crean nuevos objetos y dos "espacios supervivientes" más pequeños, el espacio superviviente pasado y el espacio superviviente futuro. Los objetos de la generación anterior que pueden hacer referencia a objetos del nuevo espacio se guardan en un "conjunto recordado". En cada búsqueda, los objetos del nuevo espacio se rastrean desde las raíces del conjunto recordado y se copian al espacio superviviente futuro. Si el espacio superviviente futuro se llena, los objetos que no encajan se promueven al espacio antiguo, un proceso llamado "titularidad". Al final de la búsqueda, algunos objetos residen en el espacio superviviente futuro, y el edén y el espacio superviviente pasado están vacíos. Luego, el espacio superviviente futuro y el espacio superviviente pasado se intercambian y el programa continúa, asignando objetos en el edén. En el sistema original de Ungar, el edén es 5 veces más grande que cada espacio superviviente.

La recolección de basura generacional es un enfoque heurístico y algunos objetos inalcanzables pueden no ser recuperados en cada ciclo. Por lo tanto, ocasionalmente puede ser necesario realizar una recolección de basura completa de marcado y barrido o copia para recuperar todo el espacio disponible. De hecho, los sistemas de tiempo de ejecución para lenguajes de programación modernos (como Java y .NET Framework ) generalmente utilizan algún híbrido de las diversas estrategias que se han descrito hasta ahora; por ejemplo, la mayoría de los ciclos de recolección pueden considerar solo algunas generaciones, mientras que ocasionalmente se realiza un marcado y barrido, e incluso más raramente se realiza una copia completa para combatir la fragmentación. Los términos "ciclo menor" y "ciclo mayor" a veces se utilizan para describir estos diferentes niveles de agresión del recolector.

Los recolectores de basura simples del tipo "detener el mundo" detienen por completo la ejecución del programa para ejecutar un ciclo de recolección, garantizando así que no se asignen nuevos objetos y que los objetos no se vuelvan repentinamente inalcanzables mientras el recolector se está ejecutando.

Esto tiene la desventaja de que el programa no puede realizar ningún trabajo útil mientras se ejecuta un ciclo de recolección (a veces llamado la "pausa embarazosa" ^[6] ). Por lo tanto, la recolección de basura de parada del mundo es principalmente adecuada para programas no interactivos. Su ventaja es que es más simple de implementar y más rápida que la recolección de basura incremental.

Los recolectores de basura incrementales y concurrentes están diseñados para reducir esta interrupción intercalando su trabajo con la actividad del programa principal. Los recolectores de basura incrementales realizan el ciclo de recolección de basura en fases discretas, y se permite la ejecución del programa entre cada fase (y, a veces, durante algunas fases). Los recolectores de basura concurrentes no detienen la ejecución del programa en absoluto, excepto quizás brevemente cuando se escanea la pila de ejecución del programa. Sin embargo, la suma de las fases incrementales tarda más en completarse que un pase de recolección de basura por lotes, por lo que estos recolectores de basura pueden producir un rendimiento total menor.

Es necesario un diseño cuidadoso con estas técnicas para garantizar que el programa principal no interfiera con el recolector de basura y viceversa; por ejemplo, cuando el programa necesita asignar un nuevo objeto, el sistema de ejecución puede necesitar suspenderlo hasta que se complete el ciclo de recolección o notificar de alguna manera al recolector de basura que existe un nuevo objeto accesible.

Algunos recolectores pueden identificar correctamente todos los punteros (referencias) en un objeto; estos se denominan recolectores precisos (también exactos o exactos ), siendo el opuesto un colector conservador o parcialmente conservador . Los recolectores conservadores asumen que cualquier patrón de bits en la memoria podría ser un puntero si, interpretado como un puntero, apuntara a un objeto asignado. Los recolectores conservadores pueden producir falsos positivos, donde la memoria no utilizada no se libera debido a una identificación incorrecta del puntero. Esto no siempre es un problema en la práctica a menos que el programa maneje una gran cantidad de datos que podrían identificarse fácilmente como un puntero. Los falsos positivos son generalmente menos problemáticos en sistemas de 64 bits que en sistemas de 32 bits porque el rango de direcciones de memoria válidas tiende a ser una fracción minúscula del rango de valores de 64 bits. Por lo tanto, es poco probable que un patrón arbitrario de 64 bits imite a un puntero válido. Un falso negativo también puede ocurrir si los punteros están "ocultos", por ejemplo, utilizando una lista enlazada XOR . Si un colector preciso es práctico generalmente depende de las propiedades de seguridad de tipos del lenguaje de programación en cuestión. Un ejemplo para el cual se necesitaría un recolector de basura conservador es el lenguaje C , que permite que los punteros tipados (no nulos) se conviertan en punteros no tipados (nulos), y viceversa.

Un problema relacionado con esto es el de los punteros internos , o punteros a campos dentro de un objeto. Si la semántica de un lenguaje permite punteros internos, entonces puede haber muchas direcciones diferentes que puedan hacer referencia a partes del mismo objeto, lo que complica la determinación de si un objeto es basura o no. Un ejemplo de esto es el lenguaje C++ , en el que la herencia múltiple puede hacer que los punteros a objetos base tengan direcciones diferentes. En un programa optimizado estrictamente, el puntero correspondiente al objeto en sí puede haberse sobrescrito en su registro, por lo que es necesario escanear dichos punteros internos.

El rendimiento de los recolectores de basura de rastreo (tanto la latencia como el rendimiento) depende significativamente de la implementación, la carga de trabajo y el entorno. Las implementaciones ingenuas o el uso en entornos con mucha memoria restringida, en particular los sistemas integrados, pueden dar como resultado un rendimiento muy bajo en comparación con otros métodos, mientras que las implementaciones sofisticadas y el uso en entornos con mucha memoria pueden dar como resultado un rendimiento excelente. ^{[ cita requerida ]}

En términos de rendimiento, el rastreo por su naturaleza requiere una cierta sobrecarga de tiempo de ejecución implícita , aunque en algunos casos el costo amortizado puede ser extremadamente bajo, en algunos casos incluso menor que una instrucción por asignación o recopilación, superando la asignación de pila. ^[7] La ​​administración manual de memoria requiere sobrecarga debido a la liberación explícita de memoria, y el conteo de referencias tiene sobrecarga por incrementar y decrementar los conteos de referencias y verificar si el conteo se ha desbordado o ha caído a cero.

En términos de latencia, los recolectores de basura simples de tipo stop-the-world pausan la ejecución del programa para la recolección de basura, lo que puede ocurrir en momentos arbitrarios y tomar un tiempo arbitrario, lo que los hace inutilizables para la computación en tiempo real , en particular los sistemas integrados, y no son adecuados para el uso interactivo, o cualquier otra situación donde la baja latencia sea una prioridad. Sin embargo, los recolectores de basura incrementales pueden proporcionar garantías estrictas de tiempo real, y en sistemas con tiempos de inactividad frecuentes y suficiente memoria libre, como las computadoras personales, la recolección de basura se puede programar para tiempos de inactividad y tener un impacto mínimo en el rendimiento interactivo. La administración manual de memoria (como en C++) y el conteo de referencias tienen un problema similar de pausas arbitrariamente largas en caso de desasignar una estructura de datos grande y todos sus hijos, aunque estos solo ocurren en momentos fijos, no dependiendo de la recolección de basura.

Asignación manual de montón

• buscar el bloque mejor/primero adecuado de tamaño suficiente
• mantenimiento de listas gratuito

Recolección de basura

• localizar objetos alcanzables
• Copiar objetos alcanzables para recolectores en movimiento
• Barreras de lectura y escritura para recolectores incrementales
• Búsqueda de bloques con el mejor ajuste y mantenimiento gratuito de listas para coleccionistas que no se mueven

Es difícil comparar los dos casos directamente, ya que su comportamiento depende de la situación. Por ejemplo, en el mejor caso para un sistema de recolección de basura, la asignación solo incrementa un puntero, pero en el mejor caso para la asignación manual de montón, el asignador mantiene listas libres de tamaños específicos y la asignación solo requiere seguir un puntero. Sin embargo, esta segregación de tamaño generalmente causa un gran grado de fragmentación externa, que puede tener un impacto adverso en el comportamiento de la caché. La asignación de memoria en un lenguaje de recolección de basura se puede implementar utilizando la asignación de montón detrás de escena (en lugar de simplemente incrementar un puntero), por lo que las ventajas de rendimiento enumeradas anteriormente no necesariamente se aplican en este caso. En algunas situaciones, más notablemente los sistemas integrados , es posible evitar tanto la recolección de basura como la sobrecarga de administración del montón al preasignar grupos de memoria y usar un esquema personalizado y liviano para la asignación/desasignación. ^[8]

Es más probable que la sobrecarga de las barreras de escritura se note en un programa de estilo imperativo que frecuentemente escribe punteros en estructuras de datos existentes que en un programa de estilo funcional que construye datos solo una vez y nunca los cambia.

Algunos avances en la recolección de basura pueden entenderse como reacciones a problemas de rendimiento. Los primeros recolectores eran recolectores de tipo stop-the-world, pero el rendimiento de este enfoque distraía en aplicaciones interactivas. La recolección incremental evitaba esta interrupción, pero a costa de una menor eficiencia debido a la necesidad de barreras. Las técnicas de recolección generacional se utilizan tanto con recolectores de tipo stop-the-world como con recolectores incrementales para aumentar el rendimiento; la contrapartida es que parte de la basura no se detecta como tal durante más tiempo de lo normal.

• El seguimiento de la recolección de basura no es determinante en cuanto al momento de finalización del objeto. Un objeto que se vuelve elegible para la recolección de basura generalmente se limpiará en algún momento, pero no hay garantía de cuándo (o incluso si) eso sucederá. Esto es un problema para la corrección del programa cuando los objetos están vinculados a recursos que no son de memoria, cuya liberación es un comportamiento del programa visible externamente, como cerrar una conexión de red, liberar un dispositivo o cerrar un archivo. Una técnica de recolección de basura que proporciona determinismo en este sentido es el conteo de referencias .
• La recolección de basura puede tener un impacto no determinista en el tiempo de ejecución, al introducir potencialmente pausas en la ejecución de un programa que no están correlacionadas con el algoritmo que se está procesando. En el caso de la recolección de basura basada en rastreo, la solicitud para asignar un nuevo objeto a veces puede regresar rápidamente y en otras ocasiones desencadenar un ciclo de recolección de basura extenso. En el caso del conteo de referencias, mientras que la asignación de objetos suele ser rápida, la disminución de una referencia es no determinista, ya que una referencia puede llegar a cero, lo que desencadena una recursión para disminuir los conteos de referencias de otros objetos que contiene ese objeto.

Si bien la recolección de basura generalmente no es determinista, es posible usarla en sistemas de tiempo real estricto . Un recolector de basura en tiempo real debe garantizar que, incluso en el peor de los casos, dedicará una cierta cantidad de recursos computacionales a los subprocesos mutadores. Las restricciones impuestas a un recolector de basura en tiempo real generalmente se basan en el trabajo o en el tiempo. Una restricción basada en el tiempo se vería así: dentro de cada ventana de tiempo de duración , se debe permitir que los subprocesos mutadores se ejecuten al menos durante el tiempo. Para el análisis basado en el trabajo, MMU (utilización mínima del mutador) ^[9] generalmente se usa como una restricción en tiempo real para el algoritmo de recolección de basura.${\displaystyle T}$${\displaystyle T_{m}}$

Una de las primeras implementaciones de recolección de basura en tiempo real estricta para la JVM se basó en el algoritmo Metronome, ^[10] cuya implementación comercial está disponible como parte de IBM WebSphere Real Time . ^[11] Otro algoritmo de recolección de basura en tiempo real estricta es Staccato, disponible en la JVM J9 de IBM , que también proporciona escalabilidad a grandes arquitecturas multiprocesador, al tiempo que aporta varias ventajas sobre Metronome y otros algoritmos que, por el contrario, requieren hardware especializado. ^[12]

Uno de los principales desafíos de la recolección de basura en tiempo real en las arquitecturas modernas de múltiples núcleos es diseñar una recolección de basura concurrente sin bloqueos, sin dejar que los subprocesos concurrentes se bloqueen entre sí y creen pausas impredecibles. Un estudio de algoritmos que permiten la recolección de basura concurrente en tiempo real sin bloqueos aparece en un artículo de Pizlo et al. en Microsoft Research. ^[13]

• Eliminación de código muerto
• Algoritmo Mark-Compact