He estado experimentando con el diseño del lenguaje de programación, y he llegado al punto de necesitar implementar un sistema de recolección de basura. Ahora, lo primero que se me vino a la mente fue el recuento de referencias, pero esto no manejará los bucles de referencia. La mayoría de las páginas que encuentro cuando busco algoritmos son referencias sobre cómo ajustar los recolectores de basura en idiomas existentes, como Java. Cuando encuentro algo que describa algoritmos específicos, no obtengo los detalles suficientes para la implementación. Por ejemplo, la mayoría de las descripciones incluyen "cuando su programa tiene poca memoria ...", lo cual no es probable que suceda pronto en un sistema de 4 GB con mucho intercambio. Entonces, lo que estoy buscando son algunos tutoriales con buenos detalles de implementación, como cómo ajustar cuándo iniciar el recolector de elementos no utilizados (es decir, recopilar después de X cantidad de asignaciones de memoria, o cada Y minutos, etc.).¿Qué es un algoritmo simple de recolección de basura para experimentar con un intérprete simple?
Para dar un par de detalles sobre lo que estoy tratando de hacer, empiezo escribiendo un intérprete basado en la pila similar a Postscript, y mi próximo intento será probablemente un lenguaje de expresión S basado en uno de los dialectos Lisp. Estoy implementando en línea C. Mi meta es la autoeducación y documentar las diversas etapas en un tutorial sobre "cómo diseñar y escribir un intérprete".
En cuanto a lo que he hecho hasta ahora, he escrito un intérprete simple que implementa un lenguaje imperativo de estilo C, que es analizado y procesado por una VM de estilo máquina de pila (vea lang2e.sourceforge.net). Pero este lenguaje no asigna memoria nueva al ingresar ninguna función, y no tiene ningún tipo de datos de puntero, por lo que en realidad no existía la necesidad de ningún tipo de administración de memoria avanzada. Para mi próximo proyecto, estoy pensando en comenzar a contar referencias para objetos de tipo no puntero (enteros, cadenas, etc.) y luego seguir cualquier objeto tipo puntero (que pueda generar referencias circulares) en un grupo de memoria separado. . Luego, cada vez que la agrupación crezca más de X unidades de asignación más de lo que era al final del ciclo anterior de recolección de elementos no utilizados, inicie de nuevo el recopilador.
Mi requisito es que no sea demasiado ineficiente, pero fácil de implementar y documentar claramente (recuerde, quiero desarrollar esto en un papel o libro para que otros sigan). El algoritmo que tengo actualmente en la parte delantera es el marcado tricolor, pero parece que un colector generacional sería un poco mejor, pero más difícil de documentar y comprender. Así que estoy buscando un material de referencia claro (preferiblemente disponible en línea) que incluya suficientes detalles de implementación para comenzar.
Google 'Mark and Sweep' –
Debo añadir que he visto las descripciones de varios recolectores de basura, como las variaciones en la marca y el barrido, pero la mayoría de las páginas que he encontrado no eran mucho mejores que las Artículo de Wikipedia. Por ejemplo, como mencioné en la pregunta, dicen patearlo cuando la memoria baja. Bueno, eso no es probable que suceda en los sistemas modernos durante el tiempo de ejecución de la mayoría de los scripts ligeros, y aunque lo haga, no sería bueno usar toda la memoria del sistema antes de iniciar el colector. Detalles como esos son lo que estoy buscando. –
http://doc.cat-v.org/inferno/concurrent_gc/ - debería ser más que suficiente de los detalles para implementarlo. –