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

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?

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 .)

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.

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.

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.

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.

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 .

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 .

¿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 .