algorithm - mas - ¿Existe un algoritmo de recolección de basura que cumpla con estos requisitos?

complejidad del algoritmo de floyd (6)

Estoy escribiendo un compilador para un lenguaje orientado a objetos de tipo estático. Actualmente estoy investigando algoritmos de recolección de basura para usar. Me pregunto si hay un coleccionista que es:

De código abierto y documentado, para que pueda implementarlo.
Prisa
Generacional
Global, es decir, solo hay un recopilador por proceso, a diferencia de decir uno por subproceso.
Incremental y / o concurrente, para evitar largas pausas de las principales colecciones.
Se adapta a este paradigma de programación. Un ejemplo de lo que no sería un coleccionista que se vuelve muy lento en presencia de una asignación destructiva.

Edición: para aclarar, me preguntaba si hay un algoritmo implementable que haga esto, no si hay un colector disponible.

(Prefiero dejar esto como un comentario, pero no tengo suficiente reputación).

Si estás buscando algoritmos en lugar de código , definitivamente echaría un vistazo a los artículos académicos. Me topé con las Actas de OOPSLA 2003, e inmediatamente recordé su pregunta: tuvieron dos sesiones sobre la recolección de basura:

http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-1.html
http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-2.html

La ventaja de esos momentos "big bang" para comenzar su investigación es que luego puede usar Google Scholar en cualquier artículo que parezca prometedor, y ver si hay más seguimientos actualizados, buscando un título y luego haciendo clic en en el enlace "citado por", por ejemplo:

http://scholar.google.com/scholar?cites=11437015034573374705&as_sdt=2005&sciodt=0,5&hl=en

(Ya que tienes tantos requisitos, es posible que tengas que besar muchas ranas antes de encontrar a tu colector sobre la marcha).

El Azul Garbage Collector es propietario, pero hay suficiente información disponible sobre su algoritmo para que pueda implementar algo así: http://news.ycombinator.com/item?id=2022723

Definitivamente es compatible con la colección "sin pausa", aunque la complejidad de hacer esto es una buena señal de por qué las personas generalmente no lo hacen.

El problema con el robo de un recolector como este: los recolectores de basura a menudo están relacionados con el lenguaje para el que están escritos. Los buenos coleccionistas para lenguajes funcionales tienden a actuar de manera diferente que los coleccionistas para los imperativos. Los lugares de código abierto probablemente son razones para robar:

Mono
Ocaml
Pitón
...

Esto es (obviamente) difícil de responder sin una mejor idea del lenguaje que espera alojar, pero ¿ha visto el Parrot VM ? PDD 9: Garbage Collection Subsystem analiza su GC y parece tener éxito con las palabras de moda que solicitó, y los idiomas para los que fue diseñado (Perl6 principalmente, con lua y un javascript-ish fuertemente tipado llamado winxed como segundos fuertes) definitivamente tiene una asignación destructiva y objetos.

Sin embargo, es un objetivo de VM, no un GC autónomo. Realmente dudo que encuentre un GC listo para usar (aparte de los recolectores conservadores como Boehm ) que no esté asociado con algún tipo de VM, ya que lograr que sea preciso requiere más información sobre el marco de pila que el desmontaje.

Hay un algoritmo de recolección de basura que no es en absoluto experimental y que en realidad cumple con todos sus requisitos: recuento de cuentas automático simple. En general, refcounting realmente no obtiene suficiente crédito como una opción viable, pero en realidad funciona muy bien en muchas situaciones, nunca hay grandes retrasos en los lotes, y no hay necesidad de magia complicada.

Una de las preocupaciones es la limpieza de referencias circulares, que al menos puede dejar de hacer extremadamente raramente; los desarrolladores de aplicaciones que se preocupan por la velocidad pueden romper los bucles explícitamente cuando necesitan que los objetos desaparezcan.

Una característica poco apreciada de refcounting es que es mucho más fácil de almacenar en caché que otras formas de recolección de basura. Si está ejecutando un bucle que asigna algunos objetos temporales pequeños cada vez que pasa por el bucle, un GC refcounting (o administración de memoria explícita, por supuesto) puede reutilizar la misma memoria cada vez, evitando vacíos innecesarios de caché. Cualquier otro tipo de GC solo liberaría los objetos periódicamente, dando como resultado una huella de memoria mucho mayor y, por lo tanto, lentitud.

El recuento de cuentas no es muy eficiente para sistemas con múltiples subprocesos, porque necesita adquirir bloqueos cada vez que toca el refcount. Pero si está diseñando un nuevo idioma de todos modos, hay una gran cosa que puede hacer para mejorar el rendimiento y la confiabilidad en todo su idioma: evitar que casi todos los objetos se compartan entre subprocesos. es decir. hacer que compartir sea explícito. Si lo hace, sabrá qué objetos se comparan con los no compartidos y, por lo tanto, cuáles deben bloquearse al aumentar / disminuir el refcount y cuáles pueden dejarse desbloqueados. Cuando no hay bloqueo, el rendimiento de re-conteo puede ser realmente excelente.

Probablemente podría robar el recolector de basura de mono, que es una implementación de código abierto de .Net. Recientemente lanzaron un nuevo motor GC que (creo) cumple con todos los requisitos anteriores.