¿Por qué Garbage Collection solo barre el montón?

28

Básicamente, he aprendido hasta ahora que la recolección de basura borra para siempre cualquier estructura de datos a la que actualmente no se apunta. Pero esto solo verifica el montón para tales condiciones.

¿Por qué no verifica también la sección de datos (globales, constantes, etc., etc.) o la pila también? ¿Qué tiene el montón que es lo único que queremos que se recolecte la basura?

Templario oscuro
fuente
21
"barrer el montón" es más seguro que "golpear la pila" ... :-)
Brian Knoblauch

Respuestas:

62

El recolector de basura hace escanear la pila - para ver qué cosas en el montón se están utilizando actualmente (apuntado) por las cosas en la pila.

No tiene sentido que el recolector de basura considere recolectar memoria de la pila porque la pila no se administra de esa manera: todo en la pila se considera "en uso". Y la memoria utilizada por la pila se recupera automáticamente cuando regresa de las llamadas a métodos. La administración de la memoria del espacio de la pila es tan simple, barata y fácil que no querrá involucrar la recolección de basura.

(Hay sistemas, como smalltalk, donde los marcos de pila son objetos de primera clase almacenados en el montón y la basura recolectada como todos los demás objetos. Pero ese no es el enfoque popular en estos días. JVM de Java y CLR de Microsoft usan la pila de hardware y la memoria contigua .)

Jeff Grigg
fuente
77
+1 la pila siempre es completamente accesible, así que no tiene sentido barrerla
Ratchet Freak
2
+1 gracias, tomó 4 publicaciones para dar con la respuesta correcta. No sé por qué tenía que decir que todo en la pila se "considera" que está en uso, lo está usando al menos con un sentido tan fuerte como los objetos del montón que todavía están en uso, pero eso es un verdadero truco de Una muy buena respuesta.
psr
@psr que significa que todo en la pila es muy accesible y no tiene necesidad de ser recogidos hasta el método devuelve sino que (RAII) ya se ha gestionado de forma explícita
trinquete monstruo de
@ratchetfreak - Lo sé. Y solo quise decir que la palabra "considerado" probablemente no sea necesaria, está bien hacer una declaración más fuerte sin ella.
psr
55
@psr: no estoy de acuerdo. " considerado como en uso" es más correcto tanto para la pila como para el montón, por razones muy importantes. Lo que quieres es descartar lo que no se volverá a usar; lo que haces es descartar lo que no es accesible . Es posible que tenga datos accesibles que nunca necesitará; cuando estos datos crecen, tiene una pérdida de memoria (sí, son posibles incluso en lenguajes GC, a diferencia de lo que mucha gente piensa). Y uno podría argumentar que las pérdidas de pila también ocurren, el ejemplo más común es que los marcos de pila innecesarios en programas recursivos de cola se ejecutan sin eliminación de llamadas de cola (por ejemplo, en la JVM).
Blaisorblade
19

Dale la vuelta a tu pregunta. La verdadera pregunta motivadora es ¿en qué circunstancias podemos evitar los costos de la recolección de basura?

Bueno, en primer lugar, ¿cuáles son los costos de la recolección de basura? Hay dos costos principales. Primero, debes determinar qué está vivo ; eso requiere potencialmente mucho trabajo. En segundo lugar, debe compactar los agujeros que se forman cuando libera algo que se asignó entre dos cosas que aún están vivas. Esos agujeros son derrochadores. Pero compactarlos también es costoso.

¿Cómo podemos evitar estos costos?

Claramente, si puede encontrar un patrón de uso de almacenamiento en el que nunca asigne algo de larga duración, luego asigne algo de corta duración, luego asigne algo de larga duración, puede eliminar el costo de los agujeros. Si puede garantizar que para algún subconjunto de su almacenamiento, cada asignación posterior tenga una vida más corta que la anterior en ese almacenamiento, entonces nunca habrá agujeros en ese almacenamiento.

Pero si hemos resuelto el problema del agujero , también hemos resuelto el problema de la recolección de basura . ¿Tienes algo en ese almacenamiento que todavía está vivo? Sí. ¿Se asignó todo antes de que dure más? Sí, esa suposición es cómo eliminamos la posibilidad de agujeros. Por lo tanto, todo lo que necesita hacer es decir "¿está viva la asignación más reciente?" y sabes que todo está vivo en ese almacenamiento.

¿Tenemos un conjunto de asignaciones de almacenamiento donde sabemos que cada asignación posterior tiene una vida más corta que la asignación anterior? ¡Sí! Los marcos de activación de los métodos siempre se destruyen en el orden opuesto al que se crearon porque siempre tienen una vida más corta que la activación que los creó.

Por lo tanto, podemos almacenar marcos de activación en la pila y saber que nunca necesitan ser recolectados. Si hay algún fotograma en la pila, el conjunto completo de fotogramas debajo tiene una vida más larga, por lo que no es necesario recopilarlos. Y serán destruidos en el orden opuesto al que fueron creados. El costo de la recolección de basura se elimina así para los marcos de activación.

Es por eso que tenemos el grupo temporal en la pila en primer lugar: porque es una manera fácil de implementar la activación del método sin incurrir en una penalización de administración de memoria.

(Por supuesto, el costo de recolección de basura de la memoria a la que se refieren las referencias en los marcos de activación todavía está allí).

Ahora considere un sistema de flujo de control en el que los marcos de activación no se destruyen en un orden predecible. ¿Qué sucede si una activación de corta duración puede dar lugar a una activación de larga duración? Como puede imaginar, en este mundo ya no puede usar la pila para optimizar la necesidad de recolectar activaciones. El conjunto de activaciones puede contener agujeros nuevamente.

C # 2.0 tiene esta característica en forma de yield return. Un método que produce un rendimiento de rendimiento se reactivará más adelante, la próxima vez que se llame MoveNext, y cuando eso suceda no es predecible. Por lo tanto, la información que normalmente estaría en la pila para el marco de activación del bloque iterador se almacena en el montón, donde se recolecta basura cuando se recopila el enumerador.

Del mismo modo, la función "async / await" que viene en las próximas versiones de C # y VB le permitirá crear métodos cuyas activaciones "ceden" y "reanudan" en puntos bien definidos durante la acción del método. Dado que los marcos de activación ya no se crean y destruyen de manera predecible, toda la información que solía almacenarse en la pila tendrá que almacenarse en el montón.

Es solo un accidente de la historia que decidimos por algunas décadas que los idiomas con marcos de activación que se crean y destruyen de manera estrictamente ordenada estaban de moda. Dado que los idiomas modernos carecen cada vez más de esta propiedad, espere ver más y más idiomas que reifiquen las continuaciones en el montón de basura recolectada, en lugar de la pila.

Eric Lippert
fuente
13

La respuesta más obvia, y quizás no la más completa, es que el montón es la ubicación de los datos de la instancia. Por datos de instancia, nos referimos a los datos que representan las instancias de clases, también conocidos como objetos, que se crean en tiempo de ejecución. Estos datos son inherentemente dinámicos y el número de estos objetos, y por lo tanto la cantidad de memoria que ocupan, solo se conoce en tiempo de ejecución. Tiene que haber algún dolor de recuperación de esta memoria o los programas de larga duración consumirían toda la memoria con el tiempo.

Es inherentemente improbable que la memoria que consumen las definiciones de clase, las constantes y otras estructuras de datos estáticas aumente sin control. Dado que solo hay una única definición de clase en la memoria por un número desconocido de instancias de tiempo de ejecución de esa clase, tiene sentido que este tipo de estructura no sea una amenaza para el uso de la memoria.

Chad
fuente
55
Pero el montón no es la ubicación de los "datos de instancia". También pueden estar en la pila.
svick
@svick Depende del idioma, por supuesto. Java solo admite objetos asignados en el montón, y Vala distingue de manera bastante explícita entre los asignados en el montón (clase) y los asignados en la pila (estructura).
esponjoso
1
@fluffy: esos son idiomas muy limitados, no se puede suponer que esto se cumple en general ya que no se precisó ningún idioma.
Matthieu M.
@MatthieuM. Ese fue mi punto de vista.
esponjoso
@fluffy: entonces, ¿por qué las clases se asignan en el montón, mientras que las estructuras se asignan en la pila?
Dark Templar
10

Vale la pena tener en cuenta la razón por la que tenemos recolección de basura: porque a veces es difícil saber cuándo desasignar la memoria. Realmente solo tienes este problema con el montón. Los datos asignados en la pila se desasignarán eventualmente, por lo que no hay realmente ninguna necesidad de recolectar basura allí. Por lo general, se supone que las cosas en la sección de datos se asignan durante la vida útil del programa.

Jason Baker
fuente
1
No solo se desasignará 'eventualmente' sino que se desasignará en el momento adecuado.
Boris Yankov
3
  1. El tamaño de estos es predecible (constante, excepto para la pila, y la pila está típicamente limitada a unos pocos MB) y típicamente muy pequeña (al menos en comparación con los cientos de MB que pueden asignar aplicaciones grandes).

  2. Los objetos asignados dinámicamente suelen tener un pequeño período de tiempo en el que son accesibles. Después de eso, no hay forma de que puedan ser referenciados nunca más. Compare eso con las entradas en la sección de datos, las variables globales y demás: con frecuencia, hay un fragmento de código que las referencia directamente (piense const char *foo() { return "foo"; }). Normalmente, el código no cambia, por lo que la referencia está ahí para quedarse y se creará otra referencia cada vez que se invoque la función (que podría ser en cualquier momento hasta donde la computadora lo sepa, a menos que resuelva el problema de detención, eso es ) Por lo tanto, no podría liberar la mayor parte de esa memoria de todos modos, ya que siempre sería accesible.

  3. En muchos lenguajes recolectados de basura, todo lo que pertenece al programa que se ejecuta se asigna en un montón. En Python, simplemente no hay ninguna sección de datos ni valores asignados a la pila (existen las referencias que son las variables locales, y está la pila de llamadas, pero tampoco hay un valor en el mismo sentido que un inten C). Cada objeto está en el montón.


fuente
"En Python, simplemente no hay ninguna sección de datos". Esto no es estrictamente hablando cierto. Ninguno, Verdadero y Falso se asignan en la sección de datos tal como lo entiendo: stackoverflow.com/questions/7681786/how-is-hashnone-calculated
Jason Baker
@JasonBaker: ¡Interesante hallazgo! Sin embargo, no tiene ningún efecto. Es un detalle de implementación y está restringido a objetos incorporados. Eso sin mencionar que no se espera que esos objetos se desasignen nunca durante la vida útil del programa de todos modos, no lo son, y también son de tamaño pequeño (menos de 32 bytes cada uno, supongo).
@delnan Como Eric Lippert le gusta señalar, para la mayoría de los idiomas la existencia de regiones de memoria separadas para la pila y el montón es un detalle de implementación. Puede implementar la mayoría de los idiomas sin usar una pila (aunque el rendimiento puede verse afectado cuando lo hace) y seguir cumpliendo con sus especificaciones
Julio
2

Como han dicho otros respondedores, la pila es parte del conjunto raíz, por lo que se escanea en busca de referencias pero no "recopilada", per se.

Solo quiero responder a algunos de los comentarios que implican que la basura en la pila no importa; lo hace, porque puede hacer que se considere más basura en el montón. Los escritores de VM y compiladores concienzudos anulan o excluyen las partes muertas de la pila del escaneo. IIRC, algunas máquinas virtuales tienen tablas que asignan rangos de PC a mapas de bits de stack-slot-liveness y otras simplemente anulan las ranuras. No sé qué técnica se prefiere actualmente.

Un término utilizado para describir esta consideración particular es seguro para el espacio .

Ryan Culpepper
fuente
Sería interesante saberlo. Lo primero que se piensa es que anular espacios es lo más realista. Atravesar un árbol de áreas excluidas puede llevar más tiempo que simplemente escanear a través de nulos. ¡Obviamente, cualquier intento de compactar la pila está lleno de peligros! Hacer que ese trabajo parezca un proceso alucinante / propenso a errores.
Brian Knoblauch
@Brian, en realidad, pensando un poco más, para una máquina virtual mecanografiada necesitas algo así de todos modos, para que puedas determinar qué ranuras son referencias en lugar de números enteros, flotantes, etc. Además, con respecto a la compactación de la pila, consulta "CONS debería No CONS sus argumentos "por Henry Baker.
Ryan Culpepper
La determinación de los tipos de ranuras y la verificación de que se usan de manera adecuada pueden y generalmente se realizan de forma estática, ya sea en tiempo de compilación (para máquinas virtuales que usan código de bytes confiable) o tiempo de carga (donde el código de bytes proviene de una fuente no confiable, por ejemplo, Java).
Jules
1

Permítanme señalar algunas ideas falsas fundamentales que usted y muchos otros se equivocaron:

"¿Por qué Garbage Collection solo barre el montón?" Es al revés. Solo los recolectores de basura más simples, conservadores y lentos barren el montón. Por eso son tan lentos.

Los recolectores de basura rápidos solo barren la pila (y opcionalmente algunas otras raíces, como algunas globales para punteros FFI y los registros para punteros vivos), y solo copian los punteros accesibles por los objetos de pila. El resto se descarta (es decir, se ignora), no se escanea en absoluto en el montón.

Dado que el montón es aproximadamente 1000 veces más grande que la (s) pila (s), dicho GC de escaneo de pila suele ser mucho más rápido. ~ 15 ms frente a 250 ms en montones de tamaño normal. Dado que está copiando (moviendo) los objetos de un espacio a otro, en su mayoría se llama un colector de copia semiespacio, necesita 2x de memoria y, por lo tanto, no se puede usar en dispositivos muy pequeños, como teléfonos con poca memoria. Es compacta, por lo que es muy amigable con el caché más adelante, a diferencia de los escáneres de montón de barrido y marcado simple.

Como se trata de punteros en movimiento, FFI, la identidad y las referencias son difíciles. La identidad generalmente se resuelve con identificadores aleatorios, referencias a través de punteros de reenvío. FFI es complicado, ya que los objetos extraños no pueden contener punteros al espacio anterior. Los punteros FFI generalmente se mantienen en una arena de montón separada, por ejemplo, con un colector estático de marca y barrido lento. O malloc trivial con recuento. Tenga en cuenta que malloc tiene una gran sobrecarga y un recuento aún mayor.

La implementación de Mark & ​​Sweep es trivial, pero no debe usarse en programas reales, y especialmente no debe enseñarse como el recopilador estándar. El más famoso de estos colectores de copiado con escaneo rápido de pila se llama Cheney Two-finger collector .

rurban
fuente
La pregunta parece ser más sobre qué partes de la memoria se recolectan basura, en lugar de algoritmos específicos de recolección de basura. La última oración implica especialmente que el OP está usando "barrido" como sinónimo genérico de "recolección de basura", en lugar de un mecanismo específico para implementar la recolección de basura. Teniendo en cuenta eso, su respuesta parece decir que solo los recolectores de basura más simples recolectan el montón, y los recolectores de basura rápidos en su lugar recolectan la pila y la memoria estática, dejando que el montón crezca y crezca hasta que se quede sin memoria.
8bittree
No, la pregunta era muy específica e inteligente. Las respuestas no son así. Los GC de marca lenta y barrido tienen dos fases, el paso de marca escanea las raíces en la pila y la fase de barrido escanea el montón. Los GC de copia rápida solo tienen una fase, escanear la pila. Tan fácil como eso. Como aparentemente nadie sabe aquí acerca de los recolectores de basura adecuados, la pregunta debe ser respondida. Tu interpretación es descabellada.
rurban
0

¿Qué se asigna en la pila? Variables locales y direcciones de retorno (en C). Cuando una función regresa, sus variables locales se descartan. No es necesario, incluso perjudicial, barrer la pila.

Muchos lenguajes dinámicos, y también Java o C # se implementan en un lenguaje de programación del sistema, a menudo en C. Se podría decir que Java se implementa con funciones C y utiliza variables locales C y, por lo tanto, el recolector de basura de Java no necesita barrer la pila.

Hay una excepción interesante: el recolector de basura de Chicken Scheme barre la pila (de alguna manera), porque su implementación usa la pila como un espacio de primera generación para la recolección de basura: ver Wikipedia de Chicken Scheme Design .

finalmente
fuente