language agnostic - que - Aprendiendo la teoría de la recolección de basura.

garbage collection que es (7)

Quiero aprender la teoría detrás de la recolección de basura. ¿Cómo lo hago?

También soy un dabbler interesado en la recolección de basura (hasta el punto de que escribí mi propia máquina de recolección de basura llamada VM llamada HLVM ). Aprendí leyendo tantos trabajos de investigación sobre recolección de basura como pude y jugando con las ideas yo mismo, tanto en bruto en mi máquina virtual como también escribiendo simulaciones de alto nivel con memoria segura.

La respuesta obvia es: un compilador de texto ... La pregunta es, ¿es necesario aprender el análisis léxico, el análisis y otras cosas que generalmente preceden a la recolección de basura en un texto?

El análisis léxico, el análisis y otras cosas no son relevantes para la recolección de basura. Es posible que obtenga un resumen general desactualizado de la recolección de basura de un libro de compilación, pero necesita leer los trabajos de investigación para obtener una vista actualizada, por ejemplo, con respecto al multinúcleo.

En resumen, ¿cuáles son los requisitos previos para aprender sobre la teoría de la recolección de basura?

Debe conocer la teoría básica de grafos, punteros, pilas, subprocesos y (si está interesado en subprocesos múltiples) primitivas de concurrencia de bajo nivel, como los bloqueos.

La recolección de basura se trata de determinar la accesibilidad. Cuando un programa ya no puede obtener una referencia a un valor porque ese valor se ha vuelto inalcanzable, el GC puede reciclar la memoria que ocupa ese valor. La accesibilidad se determina atravesando el montón a partir de un conjunto de "raíces globales" (variables globales y punteros en las pilas del hilo y en los registros del núcleo)

El diseño de GC tiene muchas facetas, pero puede comenzar con los cuatro algoritmos principales de recolección de basura:

Marcar y barrer (McCarthy, 1960)
Mark-and-compact (Haddon y Waite, 1967)
Detener y copiar (Cheney, 1970)
Mark-region (McKinley et al. , 2007)

Quizás la evolución más notable de estas ideas básicas es la recolección de basura generacional, que fue el diseño estándar de facto durante muchos años.

Mi opinión personal es que parte del trabajo oscuro sobre la recolección de basura transmite tanta información útil, por lo que también lo recomiendo altamente:

Caminadora de Baker (una hermosa GC en tiempo real).
VCGC (un esquema de marcado tricolor completamente diferente).

También te gustaría estudiar los tres tipos de barrera de escritura (Dijkstra, Steele y Yuasa) y observar las técnicas de marcación de cartas y conjuntos recordados.

También le gustaría examinar las decisiones de diseño reales que algunos implementadores eligieron para implementaciones de lenguaje como Java y .NET, así como el compilador SML / NJ para Standard ML, el compilador OCaml, el compilador Glasgow Haskell y otros. ¡Las diferencias entre las técnicas adoptadas son tan grandes como las similitudes entre ellas!

También hay algunos excelentes documentos relacionados tangencialmente, como la recolección de basura precisa de Henderson en un entorno no cooperativo . Utilicé esa técnica para evitar tener que escribir un apilador para HLVM.

El memorymanagement.org web memorymanagement.org es un recurso invaluable, particularmente el glosario de términos relacionados con GC.

Quiero aprender la teoría detrás de la recolección de basura. ¿Cómo lo hago? La respuesta obvia es: un compilador de texto ... La pregunta es, ¿es necesario aprender el análisis léxico, el análisis y otras cosas que generalmente preceden a la recolección de basura en un texto?

En resumen, ¿cuáles son los requisitos previos para aprender sobre la teoría de la recolección de basura?

PD: sí sé cuál es el propósito del análisis, el análisis léxico, etc. Simplemente no cómo se implementan.

Comenzaría leyendo este documento: Una teoría unificada de la recolección de basura, Bacon, Cheng y Rajan, Conferencia de la ACM sobre Programación Orientada a Objetos, Sistemas, Idiomas y Aplicaciones, Vancouver, BC, Canadá, páginas 50-68, 2004 .

El Capítulo 9, "Administración de memoria", de Object Oriented Software Construction, 2ª edición de Bertrand Meyer es bastante informativo.

Hay un libro completo sobre recolección de basura, y bastante bueno, si puedo agregar:

Richard Jones y Rafael Lins, recolección de basura, Wiley and Sons (1996), ISBN 0471941484

Richard Jones también mantiene un buen sitio que recolecta recursos de recolección de basura .

La mayoría de los primeros papeles de recolección de basura son eminentemente legibles. Puede comenzar con la encuesta de Paul Wilson sobre "Técnicas de recolección de basura de un procesador" (1992, LNCS vol. 637) y luego profundizar en la literatura original sobre temas que suenan interesantes.

Lee estos papeles en orden. Están en orden progresivo de materia / dificultad (no cronológico).

Lista tomada directamente de la página del curso de Gestión de la Memoria de la Prof. Kathryn McKinley aquí , donde encontrará enlaces a todos los artículos.

Tomé el curso el semestre pasado, así que leí todo esto y tengo que decir que aprendí lo que me propuse aprender.

Procesamiento de listas en tiempo real en una computadora en serie , Baker, CACM, 21 (4) 280--294, 1978.
Un algoritmo de compactación de lista no recursiva , Cheney, CACM, 13 (11): 677--678, 1970.
Un recolector de basura en tiempo real basado en la vida útil de los objetos , Lieberman & Hewitt, CACM, 26 (6): 419--429, 1983.
Recuperación de generación: Un algoritmo de recuperación de almacenamiento de alto rendimiento sin interrupciones , Ungar, Procedimientos del primer ACM SIGSOFT / SIGPLAN Software Engineering Symposium sobre entornos prácticos de desarrollo de software, 1984, páginas 157–167.
Recolección de basura generacional simple y asignación rápida , Appel, Software - Práctica y experiencia 19 (2): 171-183, febrero de 1989.
Recolección de basura basada en la edad , D. Stefanovic, KS McKinley, JEB Moss, Conferencia ACM sobre sistemas de programación orientados a objetos, lenguajes y aplicaciones. (OOPSLA), pp. 370--381. Denver CO, noviembre de 1999.
Recolección de basura más antigua en la práctica: evaluación en una máquina virtual Java , D. Stefanovic, M. Hertz, SM Blackburn, KS McKinley y JEB Moss, Performance System, Berlín, Alemania, páginas 175–184, junio de 2002 .
Beltway: Cómo desplazarse Recolección de basura Gridlock , SM Blackburn, R. Jones, KS McKinley y JEB Moss, Conferencia ACM sobre diseño e implementación de lenguajes de programación, Berlín, Alemania, pp. 153--164, junio de 2002.
Un procedimiento eficiente e independiente de la máquina para la recolección de basura en varias estructuras de listas , Schorr & Waite, CACM, 10 (8): 501--506, 1967.
Comparación de algoritmos de compactación para recolección de basura , Cohen & Nicolau, ACM Transactions en Lenguajes y Sistemas de Programación (TOPLAS), Volumen 5, Número 4, páginas 532 a 553, octubre de 1983.
MC2: Recolección de basura de alto rendimiento para entornos con limitaciones de memoria , Sachindran, Berger & Moss, Conferencia ACM sobre sistemas de programación orientados a objetos, lenguajes y aplicaciones, pp. 81-96, Vancouver, BC, octubre de 2004.
Immix: Un recolector de basura de Mark-Region con eficiencia de espacio, recolección rápida y rendimiento de mutadores , Blackburn & McKinley, Conferencia ACM sobre diseño e implementación de lenguajes de programación, páginas 22–32, Tucson, AZ, junio de 2008.
Un recolector de basura automático incremental eficiente , Deutsch & Bobrow, CACM, 19 (9): 522--526, septiembre de 1976.
Recuento de referencias posteriores: Recolección rápida de basura sin la espera , SM Blackburn y KS McKinley, Actas de la Conferencia SIGPLAN de ACM 2003 sobre sistemas de programación orientados a objetos, lenguajes y aplicaciones, pp. 344-359, Annehiem, CA, octubre de 2003.
Seguimiento del ciclo: Recolección eficiente de ciclos de barrido de barrido , Frampton y Blackburn, 2009. (En envío a ISMM).
Recolección de basura de compactación multiproceso , Guy L. Steele, Jr., CACM 18 (9): 495-508, 1975.
Recolección de basura sobre la marcha: un ejercicio en cooperación , EW Dijkstra, L. Lamport, AJ Martin, CS Scholten y EFM Steffens, Comunicaciones de la ACM, 21 (11): 966-975, noviembre de 1978.
Derivación de la corrección y conservación de los algoritmos de recolección de basura concurrentes , Vechev, Yahav y Bacon, Conferencia ACM sobre diseño e implementación del lenguaje de programación, Ottawa, Ontario, pp. 341-353, 2006.
Un recolector de basura en tiempo real con baja sobrecarga y uso constante , Bacon, Cheng y Rajan, ACM Simposio sobre Principios de Lenguajes de Programación, Nueva Orleans, Louisiana, págs. 285-298, 2003.
Impuestos y gastos: programación democrática para la recolección de basura en tiempo real , Auerbach, Bacon, Cheng, Grove, Biron, Gracie, McCloskey, Micic y Sciampacone, Conferencia Internacional ACM sobre Software Embebido, Atlanta, GA, pp. 245-254 , 2008.
Recolección de basura en un entorno no cooperativo , H. Boehm y M. Weiser, Software Practice and Experience, 18 (9): 807-820, 1988.
Hoard: Asignador de memoria escalable para aplicaciones multiproceso , ED Berger, KS McKinley, RD Blumofe y PR Wilson, La novena conferencia internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos, Cambridge, MA, pp. 117–128, noviembre de 2000 .
Corcho: Detección de fugas de memoria dinámica para idiomas recolectados en basura , Jump & McKinley, En envío a ACM Transactions on Software Practice & Experience, 2009. (La versión abreviada aparece en la Conferencia ACM sobre lenguajes de programación, Niza, Francia, enero de 2009).
Leak Pruning , Bond & McKinley, Conferencia ACM sobre soporte de arquitectura para lenguajes de programación y sistemas operativos, Washington, DC, marzo de 2009. (Para aparecer).
Free-me: Un análisis estático para la recuperación de objetos individuales , Guyer & McKinley, Conferencia ACM sobre diseño e implementación del lenguaje de programación, Ottawa, Canadá, pp. 364-375, junio de 2006.
La recolección de basura puede ser más rápida que la asignación de pila , Appel, Information Processing Letters 25 (4): 275-279, 17 de junio de 1987.
La ventaja de la recolección de basura: Mejorando la ubicación del programa Huang, Blackburn, McKinley, Moss, Wang y Cheng, Conferencia ACM sobre sistemas de programación orientados a objetos, lenguajes y aplicaciones, Vancouver, BC, pp. 69-80, octubre de 2004.
Magia desmitificadora: Programación de alto nivel de bajo nivel , Daniel Frampton, Stephen M. Blackburn, Perry Cheng, Robin Garner, David P. Grove, J. Eliot B. Moss y Sergey I. Salishev. Conferencia Internacional ACM sobre Entornos de Ejecución Virtual, Washington DC, marzo de 2009. (Para aparecer).
Mitos y realidades: el impacto en el rendimiento de la recolección de basura , SM Blackburn, P. Cheng y KS McKinley, Conferencia ACM SIGMETRICS sobre sistemas informáticos de medición y modelado, págs. 25--36, Nueva York, NY, junio de 2004.
Una teoría unificada de la recolección de basura , Bacon, Cheng y Rajan, Conferencia ACM sobre Programación Orientada a Objetos, Sistemas, Lenguajes y Aplicaciones, Vancouver, BC, Canadá, pp. 50-68, 2004.

No conozco ningún libro de texto sobre compiladores que también explique las recolecciones de basura, ya que, como usted mismo ha dicho, los dos no tienen ninguna relación.

En realidad, me gusta mucho el artículo de Wikipedia como una explicación introductoria con muchos buenos punteros. Definitivamente uno de los mejores artículos de CS en Wikipedia.

También es posible que desee echar un vistazo a Squeak: Open Personal Computing , que cubre el recolector de basura Squeak Smalltalk, entre otros problemas de diseño de ST. También debería echar un vistazo a Squeak en sí mismo : está casi completamente escrito en Smalltalk, y toda la fuente, incluido el GC, está disponible de forma gratuita y es fácil de estudiar con los navegadores Smalltalk.