¿Cómo evitan los recolectores de basura el desbordamiento de la pila?

23

Así que estaba pensando en cómo funcionan los recolectores de basura y pensé en un tema interesante. Presumiblemente, los recolectores de basura tienen que atravesar todas las estructuras de la misma manera. No pueden saber el tiempo que atraviesan una lista vinculada o un árbol equilibrado o lo que sea. Tampoco pueden usar demasiada memoria en su búsqueda. Una forma posible, y la única forma en que puedo pensar en atravesar TODAS las estructuras, podría ser atravesarlas recursivamente de la misma manera que lo haría con un árbol binario. Sin embargo, esto daría un desbordamiento de pila en una lista vinculada o incluso un árbol binario mal equilibrado. Pero todos los idiomas recolectados de basura que he usado nunca parecen tener problemas para lidiar con tales casos.

En el libro de dragones usa una especie de cola "No escaneada". Básicamente, en lugar de atravesar la estructura de forma recursiva, solo agrega cosas que deben marcarse como una cola y luego, por cada cosa que no está marcada al final, se elimina. ¿Pero esta cola no se haría muy grande?

Entonces, ¿cómo atraviesan los recolectores de basura estructuras arbitrarias? ¿Cómo esta técnica transversal evita el desbordamiento?

Jake
fuente
1
GC atraviesa todas las estructuras de manera más o menos igual, pero solo en un sentido muy abstracto (ver respuesta). La forma en que realizan un seguimiento concreto de las cosas es mucho más sofisticada que la indicada en las presentaciones elementales que puedes encontrar en los libros de texto. Y no usan la recursividad. Además, con la memoria virtual, las implementaciones incorrectas se muestran como desaceleración de GC, rara vez como desbordamiento de memoria.
babou
Te preocupa el espacio necesario para el trazado. Pero, ¿qué pasa con el espacio o las estructuras necesarias para distinguir la memoria que se ha rastreado y se sabe que está en uso, de la memoria que es potencialmente recuperable? Esto puede tener un costo de memoria significativo, posiblemente proporcional al tamaño del almacenamiento dinámico.
babou
Pensé que se haría con un vector de bits en un tamaño de objeto mayor de 16 bytes, por lo que la sobrecarga sería como mínimo 1000 veces menor.
Jake
Hay muchas maneras de hacerlo (ver respuesta), y también se pueden usar para el rastreo, lo que luego respondería a su pregunta (los vectores de bits o mapas de bits se pueden usar para el rastreo, en lugar de la pila o la cola que sugiere). No puede suponer que todos los objetos son grandes, a menos que tenga la intención de desperdiciar espacio en objetos pequeños, de los cuales puede haber muchos, y luego no debe preocuparse por el espacio. Si está en la memoria virtual, el espacio suele ser mucho menos un problema y los problemas son muy diferentes.
babou

Respuestas:

13

Tenga en cuenta que no soy un experto en recolección de basura. Esta respuesta solo da ejemplos de técnicas. No pretendo que sea una descripción representativa de las técnicas de recolección de basura.

Una cola sin escanear es una opción común. La cola puede hacerse grande, potencialmente tan grande como la estructura de datos más profunda. La cola generalmente se almacena explícitamente, no en la pila del subproceso de recogida de basura.

Una vez que se han escaneado todos los hijos de un nodo menos uno, el nodo se puede eliminar de la cola no explorada. Esto es básicamente una optimización de llamada de cola. Los recolectores de basura pueden incluir heurísticas para intentar escanear el hijo más profundo de un nodo al final; por ejemplo, un GC para Lisp debe escanear el carde a consantes del cdr.

Una forma de evitar mantener una cola sin escanear es modificar los punteros en su lugar, haciendo que el niño señale temporalmente al padre. Esta es una técnica transversal de árbol de memoria constante que se utiliza en contextos distintos de los recolectores de basura. La desventaja de esta técnica es que mientras el GC atraviesa una estructura de datos, la estructura de datos no es válida, por lo que el GC tiene que detener el mundo. Esto no es un factor decisivo: muchos recolectores de basura sí incluyen una fase que detiene el mundo, además de las fases que no lo hacen pero pueden perder la basura como resultado.

Gilles 'SO- deja de ser malvado'
fuente
2
La técnica descrita en el último párrafo a menudo se llama " inversión de puntero ".
Wandering Logic
@WanderingLogic Sí, la inversión del puntero es como lo llamé en mi propia respuesta. Se debe a Deutsch, Schorr y Waite (1967). Sin embargo, es incorrecto afirmar que funciona en memoria constante: requiere bits adicionales para cada celda con punteros p , aunque esto puede reducirse mediante el uso de pilas de bits. La respuesta aceptada a la que hace referencia no es del todo correcta o completa por la misma razón. Iniciar sesión2pagspags
babou
Yo he utilizado reversión puntero en un GC personalizada sin necesidad de estos bits adicionales; El truco consistía en utilizar una representación especial en memoria de los objetos en memoria. A saber, el objeto "encabezado" estaba en el medio, con campos de puntero antes del encabezado y campos sin puntero después; Además, todos los punteros estaban alineados, y el encabezado incluía un campo con el bit menos significativo siempre establecido. Por lo tanto, durante la marcha atrás de la inversión del puntero, alcanzar el siguiente puntero y notar que habíamos terminado con un objeto podría hacerse sin ambigüedades sin los bits adicionales. Este diseño también era compatible con la herencia OOP.
Thomas Pornin
@ThomasPornin Creo que la información de bits tiene que estar en alguna parte. La pregunta es ¿dónde? ¿Podemos hablar de esto en el chat? Tengo que irme ahora, pero me gustaría llegar al fondo de esto. ¿O hay una descripción accesible en la web?
babou
1
@babou y Thomas por favor
Gilles 'SO- deja de ser malvado'
11

En pocas palabras : los recolectores de basura no utilizan la recursividad. Simplemente controlan el seguimiento al realizar un seguimiento de esencialmente dos conjuntos (que pueden combinarse). El orden de rastreo y procesamiento de celdas es irrelevante, lo que brinda una considerable libertad de implementación para representar los conjuntos. Por lo tanto, hay muchas soluciones que en realidad son muy baratas en el uso de la memoria. Esto es esencial ya que el GC se llama precisamente cuando el montón se queda sin memoria. Las cosas son un poco diferentes con grandes memorias virtuales, como las nuevas páginas se pueden asignar fácilmente, y el ennemy no es la falta de espacio, pero la falta de datos de localización .

Supongo que está considerando rastrear recolectores de basura, no un recuento de referencias para el cual su pregunta no parece aplicarse.

La pregunta se centra en el costo de memoria del rastreo para realizar un seguimiento de un conjunto: el conjunto (para no rastreado) de celdas de memoria accesibles que aún contienen punteros que aún no se han rastreado. Esto es solo la mitad del problema de memoria para la recolección de basura. El GC también debe realizar un seguimiento de otro conjunto: el conjunto V (para visitado) de todas las celdas que se ha encontrado que son accesibles, para reclamar todas las otras celdas al final del proceso. Discutir uno y no el otro tiene un sentido limitado, ya que pueden tener un costo similar, usar soluciones similares e incluso combinarse.UV

Lo primero a tener en cuenta es que todos los GC de seguimiento siguen el mismo modelo abstracto, basado en la exploración sistemática del gráfico dirigido de celdas en la memoria accesible desde el programa, donde las celdas de memoria son vértices y los punteros son los bordes dirigidos. Utiliza para eso los siguientes conjuntos:

  • VVV=UT

  • U

  • T

  • H

VUUT

UV

UdoVUdoUT

UUV=TVH-VV

VUUT

También omito detalles sobre qué es una celda, si vienen en un tamaño o muchos, cómo encontramos punteros en ellos, cómo se pueden compactar y una serie de otros problemas técnicos que puede encontrar en libros y encuestas sobre recolección de basura. .

U

Donde las implementaciones conocidas difieren es en la forma en que estos conjuntos están realmente representados. Muchas técnicas se han utilizado realmente:

  • mapa de bits: se conserva algo de espacio de memoria para un mapa que tiene un bit para cada celda de memoria, que se puede encontrar utilizando la dirección de la celda. El bit está activado cuando la celda correspondiente está en el conjunto definido por el mapa. Si solo se utilizan mapas de bits, solo necesita 2 bits por celda.

  • alternativamente, puede tener espacio para un bit de etiqueta especial (o 2) en cada celda para marcarlo.

  • Iniciar sesión2pagspags

  • Puede probar un predicado sobre el contenido de la celda y sus punteros.

  • puede reubicar la celda en una parte libre de la memoria destinada a todas las celdas pertenecientes al conjunto representado.

  • VTTU

  • En realidad, puede combinar estas técnicas, incluso para un solo conjunto.

Como se dijo, todo lo anterior ha sido utilizado por un recolector de basura implementado, por extraño que parezca. Todo depende de las diversas limitaciones de la implementación. Y pueden ser bastante baratos en el uso de la memoria, posiblemente ayudados por el procesamiento de políticas de pedidos que se pueden elegir libremente para ese propósito, ya que no importan para el resultado final.

Lo que puede parecer el más extraño, la transferencia de celdas en una nueva área, en realidad es muy común: se llama colección de copias. Se utiliza principalmente con memoria virtual.

Claramente no hay recursión, y la pila del algoritmo mutador no tiene que ser utilizada.

Otro punto importante es que muchos GC modernos se implementan para grandes memorias virtuales . Entonces, obtener espacio para implementar y una lista o pila adicional no es un problema, ya que las páginas nuevas se pueden asignar fácilmente. Sin embargo, en grandes recuerdos virtuales, el enemigo no es la falta de espacio sino la falta de localidad . Luego, la estructura que representa los conjuntos, y su uso, debe orientarse a preservar la localidad de la estructura de datos y de la ejecución del GC. El problema no es el espacio sino el tiempo. Las implementaciones inadecuadas tienen más probabilidades de mostrar una desaceleración inaceptable que el desbordamiento de memoria.

No di referencias a los muchos algoritmos específicos, como resultado de varias combinaciones de estas técnicas, ya que esto parece lo suficientemente largo.

babou
fuente
4

La forma estándar de evitar un desbordamiento de la pila es usar una pila explícita (almacenada como una estructura de datos en el montón). Eso también funciona para estos fines. Los recolectores de basura a menudo tienen una lista de trabajo de elementos que necesitan ser examinados / recorridos, lo que cumple esta función. Por ejemplo, su cola "Sin escanear" es un ejemplo de exactamente este tipo de patrón. La cola puede ser potencialmente grande, pero no causa un desbordamiento de la pila, ya que no está almacenada en el segmento de la pila. En cualquier caso, nunca será más grande que la cantidad de objetos vivos en el montón.

DW
fuente
Cuando se llama al GC, el montón suele estar lleno. Otro punto es que sucede que la pila y el montón crecen desde ambos extremos del mismo espacio de memoria ..
babou
4

En las descripciones "clásicas" de la recolección de basura (por ejemplo, Mark Wilson, " Técnicas de recolección de basura uniprocesador ", Taller internacional sobre administración de memoria , 1992, ( enlace alternativo ), o la descripción en Implementación del compilador moderno de Andrew Appel (Cambridge University Press, 1998)), los coleccionistas se clasifican como "Marcar y barrer" o "Copiar".

Los coleccionistas Mark y Sweep evitan la necesidad de espacio adicional mediante la inversión de puntero, como se describe en la respuesta de @ Gilles. Appel dice que Knuth atribuye el algoritmo de inversión del puntero a Peter Deutsch, y a Herbert Schorr y WM Waite.

Los recolectores de basura de copia utilizan lo que a menudo se llama el algoritmo de Cheyney para realizar un recorrido de la cola sin necesidad de espacio adicional. Este algoritmo se introdujo en CJ Cheyney, "Un algoritmo de compactación de listas no recursivas", Comm. ACM , 13 (11): 677-678, 1970.

En un recolector de basura de copiado, tiene una porción de memoria que está tratando de recolectar, llamada from-space , y una porción de memoria que está utilizando para las copias llamadas to-space . El espacio al está organizado como una cola con un scanpuntero que apunta al registro más antiguo copiado pero sin escanear, y un freepuntero que apunta a la siguiente posición libre en el espacio. La imagen de esto del artículo de Wilson es:

Ejemplo de algoritmo de Cheyney

A medida que escanea cada elemento en el espacio, copia sus elementos freesecundarios desde el espacio al puntero en espacio, y luego cambia el puntero al elemento secundario desde el espacio a la nueva copia del elemento secundario en el espacio. Hay un truco adicional que debe usar cuando sus estructuras de datos no son árboles (cuando un niño puede tener más de un padre). En ese caso, cuando copie un elemento secundario de espacio a espacio, deberá sobrescribir la versión anterior del elemento secundario con un puntero de reenvío a la nueva copia del elemento secundario. Luego, si alguna vez escanea otro puntero a la versión anterior del niño, se dará cuenta de que ya se ha copiado y no vuelva a copiar.

Lógica Errante
fuente
En realidad, como se explicó en mi respuesta, tanto Mark + Sweep como Copy Collection son el mismo algoritmo gráfico abstracto. MS y la colección de copias difieren solo en la forma en que se implementan los conjuntos utilizados por el algoritmo abstracto, y ambas familias se incluyen, con muchas variantes, en alguna combinación de las técnicas de implementación de conjuntos que describo en mi respuesta. Algunas variantes de GC en realidad mezclan MS y Copy en el mismo GC. La separación de MS y Copy es vista por algunos como una forma conveniente de estructurar libros, pero es una visión arbitraria, y creo que obsoleta.
babou
@babou: si se usa un algoritmo de copia en el que se copiará todo lo que se visita (lento, pero puede ser útil en plataformas pequeñas donde el conjunto de trabajo nunca es tan grande), algunos algoritmos pueden simplificarse un poco ya que uno puede usar la memoria anteriormente ocupada por un objeto reubicado como un bloc de notas. También se puede obtener una capacidad limitada para que otros subprocesos realicen accesos de solo lectura a los objetos durante la recopilación, siempre que se verifique la validez del objeto antes y después de cada lectura, y siga el puntero de reenvío si un objeto se ha movido.
supercat
@supercat No estoy seguro de lo que estás tratando de decir, cuál es tu intención. Algunas de sus declaraciones parecen correctas. Pero no entiendo cómo puede usar desde el espacio antes de que finalice el ciclo GC (contiene punteros de reenvío). ¿Y sería un bloc de notas para qué? ¿Cómo simplificar el algoritmo? Con respecto a los múltiples hilos de mutadores ejecutados mientras se lleva a cabo GC, este es en gran medida un problema ortogonal, aunque puede afectar severamente la implementación. No intentaría abordar eso en los comentarios. Debería plantear menos problemas en el acceso de solo lectura, pero el diablo está en los detalles.
babou