recolector que collector collection basura functional-programming garbage-collection hardware

functional programming - que - Recolección de basura asistida por hardware



garbage collection que es (11)

Estaba pensando en formas en que los lenguajes funcionales podrían estar más atados directamente a su hardware y me preguntaba sobre cualquier implementación de hardware de la recolección de basura.

Esto aceleraría significativamente las cosas, ya que el hardware manejaría implícitamente toda la colección, en lugar del tiempo de ejecución de algún entorno.

¿Es esto lo que hicieron LISP Machines? ¿Ha habido más investigación sobre esta idea? ¿Esto también es específico del dominio?

¿Pensamientos? ¿Objeciones? Discutir.

¿Por qué "acelerar las cosas"? ¿Qué debería hacer exactamente el hardware? Todavía tiene que atravesar todas las referencias entre los objetos, lo que significa que tiene que atravesar una gran cantidad de datos en la memoria principal, que es la razón principal por la que lleva tiempo. ¿Qué ganarías con esto? ¿Qué operación en particular es la que cree que podría hacerse más rápido con soporte de hardware? La mayor parte del trabajo en un recolector de basura es solo seguir punteros / referencias, y de vez en cuando copiar objetos en vivo de un montón a otro. ¿En qué se diferencia esto de las instrucciones que una CPU ya admite?

Dicho esto, ¿por qué crees que necesitamos una recolección de basura más rápida? Un GC moderno ya puede ser muy rápido y eficiente, hasta el punto de que es básicamente un problema resuelto.

Entiendo que el mayor problema son los registros de la CPU y la pila. Una de las cosas que debe hacer durante GC es recorrer todos los indicadores en su sistema, lo que significa saber cuáles son esos indicadores. Si uno de esos punteros se encuentra actualmente en un registro de la CPU, debe atravesarlo también. Del mismo modo, si tiene un puntero en la pila. Por lo tanto, cada cuadro de pila debe tener algún tipo de mapa que indique qué es un puntero y qué no, y antes de hacer un recorrido de GC, debe sacar cualquier puntero a la memoria.

También tiene problemas con cierres y continuaciones, porque de repente su pila deja de ser una estructura LIFO simple.

La forma obvia es nunca mantener punteros en la pila de la CPU o en los registros. En su lugar, tiene cada marco de pila como un objeto que apunta a su predecesor. Pero eso mata el rendimiento.

Estoy bastante seguro de que algunos prototipos deberían existir. Pero desarrollar y producir características específicas de hardware es muy costoso. Tomó mucho tiempo implementar MMU o TLB a nivel de hardware, que son bastante fáciles de implementar.

GC es demasiado grande para ser implementado eficientemente en el nivel de hardware.

Hubo un artículo sobre lambda que describe cómo se necesita un administrador de memoria virtual compatible con GC para tener un GC realmente eficiente, y el mapeo de VM se hace principalmente por hardware en estos días. Aquí estás :)

Debido a Generational Collection, tendría que decir que el rastreo y la copia no son grandes obstáculos para GC.

Lo que ayudaría, son las barreras LEER asistidas por hardware que eliminan la necesidad de pausas para ''detener el mundo'' cuando se hacen escaneos de pila y se marca el montón.

Azul Systems ha hecho esto: http://www.azulsystems.com/products/compute_appliance.htm. Hicieron una presentación en JavaOne sobre cómo sus modificaciones de hardware permitieron GC sin pausa.

Otra mejora sería barreras de escritura asistida por hardware para realizar un seguimiento de los conjuntos recordados.

Los GC generacionales, y más aún para G1 o Garbage First, reducen la cantidad de almacenamiento que tienen que escanear solo escaneando una partición, y manteniendo una lista de conjuntos recordados para punteros de partición cruzada.

El problema es que CUALQUIER momento en que el mutador (palabra de fantasía para el "programa real") establezca un puntero, también tiene que poner una entrada en el conjunto de recordatorios apropiado. Así que tienes (pequeña) sobrecarga incluso cuando no estás haciendo GC. Si puede reducir esto, reduciría los tiempos de pausa necesarios para GCing y el rendimiento general del programa.

Los sistemas Sparc más antiguos tenían memoria etiquetada (33 bits) que se podía usar para marcar direcciones. No está equipado hoy?

Esto vino de su herencia LISP IIRC.

Uno de mis amigos construyó un GC generacional etiquetado robando un poco de primitivos. Funcionó mejor.

Por lo tanto, sí se puede hacer, pero un nodo molesta etiquetar cosas nunca más.

Los comentarios de runT1mes sobre el GC generacional asistido por hardware merecen la pena ser leídos.

Dado un arreglo de compuertas suficientemente grande (los resortes de vértice III vienen a la mente), sería posible una MMU mejorada que soportara las actividades de GC.

Una solución obvia era tener punteros de memoria que son más grandes que la RAM disponible, por ejemplo, punteros de 34 bits en una máquina de 32 bits. O utilice los 8 bits superiores de una máquina de 32 bits cuando solo tenga 16 MB de RAM (2 ^ 24). Las máquinas Oberon en el ETH Zurich usaron un esquema de este tipo con mucho éxito hasta que RAM se volvió demasiado barato. Eso fue alrededor de 1994, por lo que la idea es bastante antigua.

Esto le da un par de bits donde puede almacenar el estado del objeto (como "este es un objeto nuevo" y "acabo de tocar este objeto"). Al hacer el GC, prefiera objetos con "esto es nuevo" y evite "solo tocar".

Esto realmente podría ver un renacimiento porque nadie tiene 2 ^ 64 bytes de RAM (= 2 ^ 67 bits; hay alrededor de 10 ^ 80 ~ 2 ^ 240 átomos en el universo, por lo que es posible que no se pueda tener tanta RAM ) Esto significa que podría usar un par de bits en las máquinas de hoy en día si la VM puede decirle al sistema operativo cómo mapear la memoria.

Eres un estudiante de posgrado, suena como un buen tema para una beca de investigación para mí. Mire en el diseño de FPGA y la arquitectura de la computadora hay un montón de diseño de procesador disponible en http://www.opencores.org/

La recolección de basura se puede implementar como una tarea en segundo plano, ya está diseñada para funcionar en paralelo.

Pete

Varias grandes mentes en el MIT en los años 80 crearon el chip SCHEME-79 , que interpretaba directamente un dialecto de Scheme, se diseñó con LISP DSL y tenía hardware-gc integrado.

Probablemente la información más relevante que se necesita aquí es, ¿cuánto tiempo (porcentaje de tiempo de CPU) está gastando actualmente en la recolección de basura? Puede ser un no problema.

Si vamos después de esto, tenemos que considerar que el hardware está engañando con la memoria "detrás de nuestra espalda". Supongo que esto sería "otro hilo", en lenguaje moderno. Algunos recuerdos podrían no estar disponibles si se estuvieran examinando (quizás se puedan solucionar con la memoria de doble puerto), y ciertamente si el HWGC va a mover cosas, entonces tendría que bloquear los otros procesos para que no interfiera con ellos. . Y hágalo de una manera que se ajuste a la arquitectura y el / los idioma (s) en uso. Entonces, sí, dominio específico.

Mira lo que acaba de aparecer ... en otra publicación ... Mirando el registro de GC de Java.