¿Hay algún algoritmo de recolección de basura que cumpla con estos requisitos?

Question

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

• Código abierto y documentado, para que pueda implementarlo.
• acurrate
• generacional
• global, es decir que sólo hay un colector por proceso, en lugar de decir uno por cada hilo.
• Incremental y/o concurrente, para evitar largas pausas de colecciones importantes.
• 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.

Editar: Para aclarar, me preguntaba si hay un algoritmo implementable que hace esto, no si hay un colector off-the-shelf.

Answer 1

(yo prefiero dejar esto como un comentario, pero no tienen suficiente rep.)

Si está buscando algoritmos en lugar de código, yo definitivamente echar un vistazo en artículos académicos. Me tropezado con las Actas de OOPSLA 2003, e inmediatamente me acordé de su pregunta --- tenían 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 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 el enlace "citado por", para ejemplo:

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

(Puesto que usted tiene tantos requisitos, puede que tenga que besar muchas ranas antes de encontrar su colector en la marcha.)

Answer 2

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

Answer 3

El problema con el robo de un coleccionista como este: los recolectores de basura a menudo están vinculados con el idioma para el que están escritos. Los buenos coleccionistas de lenguajes funcionales tienden a actuar de manera diferente a los coleccionistas para los imperativos. El código abierto sitúa probablemente hay razón para robar a:

• Mono
• Ocaml
• Python
• ...

Answer 4

Esta es (obviamente) difícil de responder sin alguna idea mejor del idioma que espera alojar, pero ¿ha mirado el Parrot VM? PDD 9: Garbage Collection Subsystem discute su GC y parece golpear las palabras de moda que usted solicitó, y los lenguajes para los que fue diseñado (Perl6 principalmente, con lua y una cosa javascript-ish fuertemente tipada llamada winxed como segundos fuertes) definitivamente tienen asignación destructiva y Objetos.

Es un objetivo de máquina virtual, no es un GC independiente. Realmente dudo que encuentres un GC fuera de la plataforma (que no sean recolectores conservadores como Boehm) que no esté asociado con algún tipo de VM, ya que para ser preciso se necesita más información sobre el marco de la pila que el desmontaje.

Answer 5

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

Una preocupación sigue siendo la limpieza de referencias circulares, que al menos puede dejar de hacer con muy poca frecuencia; Los desarrolladores de aplicaciones que se preocupan por la velocidad pueden simplemente romper los bucles explícitamente cuando necesitan que los objetos se vayan.

Una característica poco apreciada de refcounting es que es mucho más amigable con el caché que otras formas de recolección de basura.Si está ejecutando un bucle que asigna algunos pequeños objetos temporales en todo momento a través del bucle, un GC de recuento (o gestión de memoria explícita, por supuesto) puede reutilizar la misma memoria cada vez, evitando descargas de caché innecesarias. Cualquier otro tipo de GC solo liberaría los objetos periódicamente, lo que daría como resultado una memoria mucho más grande y, por lo tanto, lentitud.

El recuento de contaje no es muy eficiente para los sistemas de múltiples subprocesos, ya que debe adquirir bloqueos cada vez que toca el recuento. 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: evite que casi todos los objetos se compartan entre subprocesos. es decir. hacer que compartir sea explícito Si lo haces, sabrás cuáles son los objetos que no son compartidos, y por lo tanto cuáles deben bloquearse al aumentar/disminuir el recuento y que pueden dejarse desbloqueados. Cuando no hay ningún bloqueo, el rendimiento de recuento puede ser realmente excelente.

Answer 6

El Azul recolector de basura es propietario, pero no hay suficiente información disponible acerca de su algoritmo que debe ser capaz de implementar algo parecido: http://news.ycombinator.com/item?id=2022723

Definitivamente apoya colección "pauseless", a pesar de la complejidad de hacer esto es una buena señal de por qué las personas generalmente no lo hacen.