garbage collection - ¿Por qué los recolectores de basura esperan antes de desasignar?

garbage-collection reference-counting

Question

Tengo un "¿por qué funciona de esa manera?" pregunta sobre la recolección de basura (cualquier / todas las implementaciones: Java, Python, CLR, etc.). Los recolectores de basura desasignan un objeto cuando ya no está en ningún ámbito; El número de referencias que lo señalan es cero. Me parece que un marco podría desasignarse tan pronto como el número de referencias llegue a cero, pero todas las implementaciones que he encontrado esperan un momento y luego desasignan muchos objetos a la vez. Mi pregunta es, ¿por qué?

Supongo que el marco mantiene un número entero para cada objeto (lo que creo que Python hace, porque debes llamar a PyINCREF y PyDECREF cuando escribes módulos de extensión para él en C; probablemente estas funciones modifican un contador real en algún lugar). Si es así, entonces no debería tomar más tiempo de CPU para eliminar el objeto en el momento en que queda fuera del alcance. Si toma x nanosegundos por objeto ahora, entonces tomaría x nanosegundos por objeto más tarde, ¿verdad?

Si mi suposición es errónea y no hay un entero asociado con cada objeto, entonces entiendo por qué espera la recolección de basura: tendría que recorrer la gráfica de referencias para determinar el estado de cada objeto, y ese cálculo lleva tiempo. Tal método consumiría menos memoria que el método explícito de recuento de referencias, pero me sorprende que sea más rápido o que sea el método preferido por otras razones. Suena como mucho trabajo.

Desde el punto de vista de la programación, sería bueno si los objetos se desasignaran inmediatamente después de que queden fuera del alcance. No solo podríamos confiar en que se ejecuten los destructores cuando queremos que lo sean (uno de los errores de Python es que __del__ no se llama en un momento predecible), sino que sería mucho más fácil __del__ un programa de perfil de memoria. Aquí hay un ejemplo de cuánta confusión causa esto. En mi opinión, los beneficios de la programación en un marco de desasignación inmediata son tan grandes que debe haber alguna buena razón para que todas las implementaciones de las que he oído hablar esperen antes de desasignar. ¿Cuál es ese beneficio?

Nota: si el recorrido sobre la gráfica de referencias solo es necesario para identificar referencias circulares (un recuento de referencias puras no puede), ¿por qué no un enfoque híbrido? Desasigne los objetos tan pronto como su recuento de referencias llegue a cero y luego realice barridos periódicos para buscar referencias circulares. Los programadores que trabajan en dicho marco tendrían una razón de rendimiento / determinismo para atenerse a las referencias no circulares en la medida de lo posible. A menudo es factible (por ejemplo, todos los datos están en forma de objetos JSON sin punteros a los padres). ¿Es así como funciona cualquier recolector de basura popular?

Answer 1

@Jim ha respondido bastante, le añadiré más.

En primer lugar, ¿qué te hace pensar que desasignar [A1] tan pronto como el recuento es 0 es una buena alternativa?

Los recolectores de basura no solo desasignan los objetos sino que también son responsables de la gestión completa de la memoria. Comenzando con la fragmentation , uno de los mayores problemas con los recolectores de basura. Si no se realiza correctamente, se producirán visitas de página innecesarias y fallas de caché. Los recolectores de basura desde el principio están diseñados para manejar este problema. Con diferentes generaciones, se vuelve más fácil manejar esto. Con A[1] , periódicamente un hilo debe configurarlo y manejarlo.

Además, resulta que borrar varios objetos es más rápido que hacerlo como en A[1] . (Piense en ello, para una habitación con arena esparcida: es más rápido eliminarlos a todos juntos en lugar de recogerlos individualmente)

En segundo lugar, para la seguridad de subprocesos en los sistemas de subprocesos múltiples, uno tendrá que mantener un bloqueo para que cada objeto aumente / disminuya el conteo, lo que es un mal rendimiento y memoria adicional. Los coleccionistas modernos tienen la capacidad de hacerlo en paralelo y no de parar. The World (Ex: Java''s ParallelGC), me pregunto cómo puede pasar esto con A[1] .

Answer 2

Creo que la razón en el rendimiento. Si crea muchos objetos en un bucle y los destruye al final de un paso de bucle, le tomará más tiempo ejecutar ese código, luego esperar hasta que el programa esté inactivo y liberar los datos de una vez. O en memoria baja de la causa.

Answer 3

Donde me he encontrado con los sistemas GC, esperan hasta que necesiten ejecutarse, de modo que la reubicación de los objetos que todavía están en uso se puede hacer una vez, en lugar de muchas veces.

Considere una serie de objetos asignados secuencialmente en la memoria:

Object 1
Object 2
Object 3
Object 4
Object 5

Si el objeto 2 puede ser desasignado y el GC opera de inmediato, todos los objetos 3,4 y 5 deberán moverse.

Ahora considere que el objeto 4 se puede desasignar, GC moverá el Objeto 5 al lado del Objeto 3. El Objeto 5 se ha movido dos veces

Sin embargo, si GC espera un poco, ambos Objetos2 y 4 pueden eliminarse al mismo tiempo, lo que significa que el Objeto 5 se mueve una vez y se mueve más.

Multiplique el número de objetos por, digamos, 100 y podrá ver un ahorro considerable de tiempo con este enfoque.

Answer 4

La recolección de basura mediante el conteo de referencias es muy lenta, especialmente en un entorno de subprocesos.

Realmente recomiendo este post por Brian Harry .

Allí se proporciona un ejemplo de código que es más que suficiente para convencerme (C #):

public interface IRefCounted : IDisposable
{
        void AddRef();
}

// ref counted base class.
class RefCountable : IRefCountable
{
        private m_ref;
        public RefCountable()
        {
                m_ref = 1;
        }
        public void AddRef()
        {
                Interlocked.Increment(ref m_ref);
        }
        public void Dispose()
        {
                if (Interlocked.Decrement(ref m_ref) == 0)
                        OnFinalDispose();
        }
        protected virtual void OnFinalDispose()
        {
        }
}

Interlocked.Increment(ref m_ref) es una operación atómica que requiere cientos de ciclos de memoria.

Answer 5

Para comprender la recolección de basura, diríjase a una bolera y observe cómo el colocador de bolos elimina los alfileres caídos después de rodar la primera bola. En lugar de identificar y eliminar los pasadores caídos individuales, el mecanismo del generador de bolos recoge todos los pasadores que aún están en pie, los eleva a la seguridad y luego ejecuta una barra barredora a través del carril sin tener en cuenta la cantidad de pasadores que se encuentran allí o dónde están ubicados. . Una vez hecho esto, los pasadores que estaban de pie se colocan de nuevo en el carril. Muchos sistemas de recolección de basura funcionan de manera muy parecida: tienen que hacer una cantidad de trabajo no trivial para cada objeto vivo para garantizar que no se destruya, pero los objetos muertos se destruyen al por mayor sin siquiera ser observados o notados.

Apéndice

Un recolector de basura que siempre tiene que actuar en cada elemento vivo para garantizar que su conservación pueda ser lenta cuando hay muchos elementos vivos; Es por esto que los recolectores de basura, históricamente, han recibido una mala reputación. El intérprete BASIC en el Commodore 64 (que, por cierto, fue escrito por Microsoft en los días anteriores a MS-DOS) tomaría muchos segundos para realizar una recolección de basura en un programa que tenía una serie de unos pocos cientos de cadenas. El rendimiento puede mejorarse enormemente si los elementos que sobreviven a su primera recolección de basura pueden ignorarse hasta que muchos elementos hayan sobrevivido a su primera recolección de basura, y aquellos que hayan participado y sobrevivido a dos recolecciones de basura (tenga en cuenta que no tendrán que participar en su segunda la colección hasta que muchos otros objetos hayan sobrevivido a su primer) puede ignorarse hasta que muchos otros objetos también hayan participado y sobrevivido en su segundo. Este concepto se puede implementar parcialmente fácilmente (incluso en el Commodore 64, uno podría forzar a todas las cadenas que existen en un momento dado a estar exentas de la recolección de basura futura, lo que podría ser útil si en el inicio un programa creara grandes conjuntos de cadenas que nunca cambiar) pero se vuelve más poderoso con un poco de soporte de hardware adicional.

Si se da cuenta de que un recolector de basura intentará empaquetar los objetos que se mantendrán tan cerca del final de la memoria como sea posible, el soporte generacional solo requiere hacer un seguimiento del rango de memoria (contiguo) que se usa. Por objetos de cada generación. Todos los objetos de cada generación se deben escanear para asegurarse de que todos los objetos vivos de las generaciones más recientes se encuentren y se conserven, pero los objetos de las generaciones anteriores no tienen que moverse, ya que la memoria que ocupan no corre el riesgo de ser eliminada por completo. Este enfoque es muy simple de implementar y puede ofrecer algunas mejoras de rendimiento significativas en comparación con un GC no generacional, pero incluso la fase de escaneo de un GC puede ser costosa si hay muchos objetos vivos.

La clave para acelerar una recolección de basura "de nueva generación" es observar que si un objeto "Fred" no se ha escrito desde la última recolección de basura en la que participó, no puede contener ninguna referencia a ningún objeto que haya sido creado desde entonces. En consecuencia, ninguno de los objetos a los que tiene referencias estaría en peligro de eliminación hasta que Fred sea elegible para su eliminación. Por supuesto, si las referencias a objetos más nuevos se han almacenado en Fred desde el último GC de nivel inferior, esas referencias deben ser escaneadas. Para lograr esto, los recolectores de basura avanzados configuran las trampas de hardware que se activan cuando se escriben partes del montón de generación anterior. Cuando se dispara una trampa de este tipo, agrega los objetos en esa región a una lista de objetos de generaciones anteriores que deberán ser escaneados, y luego desactiva la trampa asociada con esa región. En los casos en los que los objetos de generaciones más antiguas suelen tener referencias a objetos más nuevos almacenados en ellos, esta contabilidad adicional puede afectar el rendimiento, pero en la mayoría de los casos termina siendo una gran ganancia de rendimiento.

Answer 6

Para empezar, un punto de terminología: "recolección de basura" significa diferentes cosas para diferentes personas, y algunos esquemas GC son más sofisticados que otros. Algunas personas consideran que el recuento de referencias es una forma de GC, pero personalmente considero que "GC verdadero" es distinto del recuento de referencias.

Con refcounts, hay un número entero que rastrea el número de referencias, y puede activar la desasignación inmediatamente cuando el refcount llega a cero. Aquí se explica cómo funciona la implementación de CPython y cómo funcionan la mayoría de los punteros inteligentes de C ++. La implementación de CPython agrega un GC de marca / barrido como respaldo, por lo que es muy parecido al diseño híbrido que describe.

Pero refcounting es en realidad una solución bastante terrible, ya que incurre en una escritura de memoria (relativamente) costosa (más una barrera de memoria y / o bloqueo, para garantizar la seguridad del subproceso) cada vez que se pasa una referencia, lo que sucede bastante. En lenguajes imperativos como C ++ es posible (simplemente difícil) administrar la propiedad de la memoria mediante macros y convenciones de codificación, pero en lenguajes funcionales como Lisp es prácticamente imposible, ya que la asignación de memoria usualmente ocurre implícitamente debido a la captura de variables locales en un cierre.

Por lo tanto, no debería sorprender que el primer paso hacia un GC moderno fue inventado para Lisp. Fue llamado el "dosificador de espacio" o "colector de dos espacios" y funcionó exactamente como suena: dividió la memoria asignable (el "montón") en dos espacios. Cada nuevo objeto fue asignado fuera del primer espacio hasta que se llenó demasiado, en el cual la asignación de puntos se detendría y el tiempo de ejecución recorrería el gráfico de referencia y copiaría solo los objetos vivos (aún referenciados) al segundo espacio. Después de copiar los objetos vivos, el primer espacio se marcaría vacío, y la asignación se reanudaría, asignando nuevos objetos desde el segundo espacio, hasta que se llenara demasiado, momento en el que los objetos vivos se copiarían al primer espacio y al El proceso comenzaría de nuevo.

La ventaja del colector de dos espacios es que, en lugar de hacer trabajo O(N) , donde N es el número total de objetos de basura, solo haría trabajo O(M) , donde M es el número de objetos que no eran basura . Como en la práctica, la mayoría de los objetos se asignan y luego se desasignan en un corto período de tiempo, esto puede llevar a una mejora sustancial del rendimiento.

Además, el colector de dos espacios también permitió simplificar el lado del asignador. La mayoría de las implementaciones de malloc() mantienen lo que se llama una "lista libre": una lista de los bloques que aún están disponibles para ser asignados. Para asignar un nuevo objeto, malloc() debe escanear la lista libre en busca de un espacio vacío que sea lo suficientemente grande. Pero el asignador de dos espacios no se molestó en eso: solo asignó objetos en cada espacio como una pila, simplemente empujando un puntero hacia arriba por el número deseado de bytes.

Así que el coleccionista de dos espacios era mucho más rápido que malloc() , lo cual era genial porque los programas Lisp harían muchas más asignaciones que los programas en C. O, para decirlo de otra manera, los programas Lisp necesitaban una forma de asignar memoria como una pila pero con un tiempo de vida que no estaba limitado a la pila de ejecución; en otras palabras, una pila que podría crecer infinitamente sin que el programa se quede sin memoria . Y, de hecho, Raymond Chen sostiene que así es como la gente debería pensar en GC. Recomiendo encarecidamente su serie de publicaciones de blog que comienzan con Todo el mundo piensa en la recolección de basura de forma incorrecta .

Pero el colector de dos espacios tenía un defecto importante, que es que ningún programa podría usar más de la mitad de la RAM disponible: la otra mitad siempre se desperdiciaba. Así que la historia de las técnicas de GC es la historia de los intentos de mejorar el colector de dos espacios, generalmente mediante el uso de heurísticas del comportamiento del programa. Sin embargo, los algoritmos de GC implican inevitablemente concesiones, generalmente prefiriendo desasignar objetos en lotes en lugar de individualmente, lo que inevitablemente conduce a retrasos en los que los objetos no se desasignan inmediatamente.

Edición: para responder a su pregunta de seguimiento, los GC modernos generalmente incorporan la idea de la recolección de basura generacional , donde los objetos se agrupan en diferentes "generaciones" basadas en la vida útil, y un objeto de una generación se "promociona" a otra generación una vez que se vive. Tiempo suficiente. A veces, una pequeña diferencia en la vida útil del objeto (por ejemplo, en un servidor controlado por solicitudes, el almacenamiento de un objeto durante más de una solicitud) puede llevar a una gran diferencia en la cantidad de tiempo que se tarda antes de que el objeto se desasigne, ya que causa que se convierta en un objeto. más "titular".

Observa correctamente que un verdadero GC tiene que operar "por debajo" del nivel de malloc() y free() . (Como nota al margen, vale la pena conocer cómo se implementan malloc() y free() , ¡tampoco son mágicos!) Además, para un GC efectivo, también debes ser conservador (como el Boehm GC) y nunca mueva objetos, y compruebe cosas que podrían ser punteros, o de lo contrario necesita algún tipo de "puntero opaco", que Java y C # llaman "referencias". Los punteros opacos son realmente excelentes para un sistema de asignación, ya que significa que siempre puede mover objetos actualizando los punteros a ellos. En un lenguaje como C donde interactúas directamente con direcciones de memoria sin formato, nunca es realmente seguro mover objetos.

Y hay múltiples opciones para los algoritmos de GC. El tiempo de ejecución estándar de Java contiene no menos de cinco recopiladores (Young, Serial, CMS antiguo, nuevo CMS y G1, aunque creo que me estoy olvidando de uno) y cada uno tiene un conjunto de opciones que son configurables.

Sin embargo, los GCs no son mágicos. La mayoría de los GC simplemente están explotando el intercambio de tiempo-espacio del trabajo por lotes, lo que significa que las ganancias en velocidad generalmente se pagan en un mayor uso de la memoria (en comparación con la administración de memoria manual o el recuento de cuentas). Pero la combinación de un mayor rendimiento del programa y un mayor rendimiento del programador, en comparación con el bajo costo de RAM en la actualidad, hace que la compensación generalmente valga la pena.

Esperemos que eso ayude a aclarar las cosas!

Answer 7

Sus pensamientos son generalmente muy perspicaces y bien considerados. Sólo te falta información básica.

Los recolectores de basura desasignan un objeto cuando ya no está en ningún ámbito

Eso es completamente incorrecto en general. Los recolectores de basura trabajan en tiempo de ejecución en una representación en la que la noción de alcance se ha eliminado hace mucho tiempo. Por ejemplo, la inclusión y las aplicaciones del análisis de vida destruyen el alcance.

El rastreo de los recolectores de basura recicla el espacio en algún momento después de que desaparece la última referencia. El análisis de Lively puede tener referencias en el marco de pila sobrescritas con otras referencias, incluso si la variable todavía está dentro del alcance porque el análisis de Lively determinó que la variable nunca se volverá a utilizar y, por lo tanto, ya no es necesaria.

Me parece que un marco podría desasignarse tan pronto como el número de referencias llegue a cero, pero todas las implementaciones que he encontrado esperan un momento y luego desasignan muchos objetos a la vez. Mi pregunta es, ¿por qué?

Actuación. Puede hacer referencia al recuento en el nivel de las entradas y registros de la pila, pero el rendimiento es absolutamente terrible. Todos los recuentos prácticos de referencia que cuentan los recolectores de basura aplazan los decrementos hasta el final del alcance para lograr un rendimiento razonable ( pero aún así malo ). Los recolectores de basura de última generación cuentan con referencias de última generación que aplazan los decrementos para agruparlos y allegedly pueden alcanzar un rendimiento competitivo.

Supongo que el marco mantiene un número entero para cada objeto

No necesariamente. Por ejemplo, OCaml utiliza un solo bit.

Desde el punto de vista de la programación, sería bueno si los objetos se desasignaran inmediatamente después de que queden fuera del alcance.

Desde el punto de vista de la programación, sería bueno si el código se ejecutara 10 veces más rápido sin esfuerzo.

Tenga en cuenta que los destructores inhiben la eliminación de llamadas de cola, que son invaluables en la programación funcional.

Me sorprende que sea más rápido o que sea el método preferido por otras razones. Suena como mucho trabajo.

Considere un programa que resuelva el problema de las n-reinas manipulando listas de coordenadas del tablero de ajedrez. La entrada es un solo entero. La salida es una lista que contiene algunas coordenadas del tablero. Los datos intermedios son una gran pila de espaguetis de nodos de listas vinculadas. Si codificó esto asignando previamente una pila lo suficientemente grande de nodos de la lista enlazada, manipulándolos para obtener la respuesta, copie la respuesta (pequeña) y luego llame free una vez a toda la pila, entonces estará haciendo casi exactamente el Lo mismo que hace un recolector de basura generacional. En particular, solo copiaría ~ 6% de sus datos y asignaría al otro ~ 94% con una sola llamada free .

Ese fue un escenario perfecto para un feliz día para un recolector de basura generacional que se adhiere a la hipótesis de que "la mayoría de los objetos mueren los objetos jóvenes y viejos rara vez se refieren a un nuevo objeto". Un ejemplo patológico de contador donde la lucha de los recolectores de basura generacionales es llenar una tabla hash con objetos recién asignados. La columna vertebral de la tabla hash es una gran matriz que sobrevive, por lo que estará en la generación anterior. Cada nuevo objeto insertado en él es un backpointer de la generación anterior a la generación nueva. Cada nuevo objeto sobrevive. Así que los recolectores de basura generacionales asignan rápidamente pero luego marcan todo, copian todo y actualizan los punteros a todo y, por lo tanto, ejecutan ~ 3x más lento de lo que lo haría una simple solución C o C ++.

No solo podríamos confiar en que se ejecuten los destructores cuando queremos que lo sean (una de las trampas de Python es que del no se llama en un momento predecible), sino que sería mucho más fácil crear un perfil de memoria para un programa.

Tenga en cuenta que los destructores y la recolección de basura son conceptos ortogonales. Por ejemplo, .NET proporciona destructores en forma de IDisposable .

FWIW, en unos 15 años de usar idiomas de recolección de basura, he usado perfiles de memoria tal vez 3 veces.

¿Por qué no un enfoque híbrido? Desasigne los objetos tan pronto como su recuento de referencias llegue a cero y luego realice barridos periódicos para buscar referencias circulares. Los programadores que trabajan en dicho marco tendrían una razón de rendimiento / determinismo para atenerse a las referencias no circulares en la medida de lo posible. A menudo es factible (por ejemplo, todos los datos están en forma de objetos JSON sin punteros a los padres). ¿Es así como funciona cualquier recolector de basura popular?

CPython hace eso, creo. Mathematica y Erlang restringen el montón a ser un DAG por diseño para que puedan usar el conteo de referencias solo. Los investigadores de GC han propuesto técnicas relacionadas, como la eliminación de ensayos, como un algoritmo auxiliar para detectar ciclos.

Tenga en cuenta también que el recuento de referencias es teóricamente asintóticamente más rápido que el rastreo de la recolección de basura, ya que su rendimiento es independiente del tamaño del montón (en vivo). En la práctica, el rastreo de la recolección de basura es aún mucho más rápido incluso con pilas de 100 GB.