haskell - recoleccion - ¿Cómo puede un recolector de basura averiguar las referencias de objetos hechas desde la pila?
recolector de basura en ingles (4)
En idiomas con recolección automática de basura como Haskell o Go, ¿cómo puede el recolector de basura averiguar qué valores almacenados en la pila son punteros a la memoria y cuáles son solo números? Si el recolector de basura simplemente escanea la pila y asume que todas las direcciones son referencias a objetos, muchos objetos podrían marcarse incorrectamente como accesibles.
Obviamente, uno podría agregar un valor a la parte superior de cada marco de pila que describiera cuántos de los valores siguientes son punteros, pero ¿eso no costaría mucho rendimiento?
¿Cómo se hace en la realidad?
Algunos coleccionistas suponen que todo en la pila es un puntero potencial (como Boehm GC). Esto resulta que no es tan malo como se podría esperar, pero es claramente subóptimo. Más a menudo en idiomas administrados, se deja algo de información de etiquetado adicional con la pila para ayudar al recolector a descubrir dónde están los punteros.
Recuerde que en la mayoría de los idiomas compilados, el diseño de un marco de pila es el mismo cada vez que ingresa a una función, por lo tanto, no es tan difícil asegurarse de etiquetar sus datos de la manera correcta.
El enfoque de "mapa de bits" es una forma de hacerlo. Cada bit del mapa de bits corresponde a una palabra en la pila. Si el bit es un 1, entonces la ubicación en la pila es un puntero, y si es un 0, la ubicación es solo un número desde el punto de vista del colector (o algo parecido a esas líneas). El tiempo de ejecución de GHC y las convenciones de llamada excepcionalmente bien escritas utilizan un diseño de una palabra para la mayoría de las funciones, de modo que unos pocos bits comunican el tamaño del marco de la pila, y el resto sirve como mapa de bits. Los marcos de pila más grandes necesitan una estructura de varias palabras, pero la idea es la misma.
El punto es que la sobrecarga es baja, ya que la información de diseño se calcula en tiempo de compilación y luego se incluye en la pila cada vez que se llama a una función.
Un enfoque aún más simple es "puntero primero", donde todos los punteros se encuentran al principio de la pila. Solo necesita incluir una longitud anterior a los punteros, o una palabra "final" especial después de ellos, para indicar qué palabras son punteros en este diseño.
Curiosamente, intentar obtener esta información de administración en la pila produce una gran cantidad de problemas relacionados con la interoperabilidad con C. Por ejemplo, es subóptimo compilar lenguajes de alto nivel en C, ya que aunque C es portátil, es difícil de transportar este tipo de informacion La optimización de los compiladores diseñados para lenguajes similares a C (GCC, LLVM) puede reestructurar el marco de pila, produciendo problemas, por lo que el backend de GHC LLVM usa su propia "pila" en lugar de la pila de LLVM que le cuesta algunas optimizaciones. De manera similar, el límite entre el código C y el código "administrado" se debe construir cuidadosamente para evitar confundir el GC.
Por esta razón, cuando creas un nuevo hilo en la JVM, en realidad creas dos pilas (una para Java, una para C).
Es importante darse cuenta de que GHC mantiene su propia pila y no usa la pila C (que no sea para llamadas FFI). No hay una forma portátil de acceder a todos los contenidos de la pila C (por ejemplo, en un SPARC, parte de ella está oculta en las ventanas de registro), por lo que GHC mantiene una pila donde tiene el control total. Una vez que mantenga su propia pila, puede elegir cualquier esquema para distinguir los punteros de los no punteros en la pila (como usar un mapa de bits).
Existen GC que suponen que cada patrón de bits que es la dirección de algo que gestiona el GC es, de hecho, un puntero (y, por lo tanto, no suelte el algo). Esto puede funcionar bastante bien, ya que los punteros de llamada suelen ser más grandes que los enteros comunes pequeños y, por lo general, tienen que estar alineados. Pero sí, esto puede hacer que la recopilación de algunos objetos se retrase. El colector Boehm para C funciona de esta manera, porque está basado en bibliotecas y, por lo tanto, no recibe ninguna ayuda específica del compilador.
También hay GC que están más estrechamente relacionados con el lenguaje en el que se usan y que realmente conocen la estructura de los objetos en la memoria. Nunca he leído específicamente sobre el manejo de cuadros de pila, pero podría registrar información para ayudar al GC si el compilador y el GC están diseñados para funcionar juntos. Un truco sería juntar todas las referencias de puntero y usar una palabra por marco de pila para registrar cuántas hay, lo que no es una sobrecarga tan grande. Si puede averiguar qué función corresponde a cada marco de pila sin agregar una palabra que lo diga, entonces podría compilar un "mapa de diseño de marco de pila" por función. Otra opción sería usar palabras etiquetadas, donde se establece el valor bajo. ordene el bit de palabras que no son punteros a 1, lo que (debido a la alineación de la dirección) nunca es necesario para los punteros, por lo que puede diferenciarlos. Eso significa que tienes que cambiar los valores sin caja para usarlos.
La pila de Haskell usa una sola palabra de memoria en cada cuadro de pila que describe (con un mapa de bits) cuáles de los valores de ese cuadro de pila son punteros y cuáles no. Para obtener más información, consulte el artículo "Diseño de la pila" y el artículo "Diseño de mapa de bits" del Comentario de GHC.
Para ser justos, una sola palabra de memoria realmente no cuesta mucho, considerando todas las cosas. Se puede pensar que solo se agrega una sola variable a cada método; eso no es tan malo