Hardware Assisted Garbage Collection

Question

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.

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

¿Pensamientos? ¿Objeciones? Discutir.

Answer 1

Debido a Generational Collection, tengo que decir que el seguimiento y la copia son no grandes cuellos de botella para GC.

Lo que ayudaría, son las barreras LEAD asistidas por hardware que eliminan la necesidad de pausas '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 Ofrecieron una presentación en JavaOne sobre cómo sus modificaciones de hardware permitieron GC sin pausa.

Otra mejora serían las barreras de escritura asistidas por hardware para realizar un seguimiento de los conjuntos recordados.

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 CUALQUIERA vez que el mutador (palabra de lujo para el "programa real") establece un puntero, también tiene que poner una entrada en el conjunto apropiado recordado. 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.

Answer 2

¿Por qué "aceleraría las cosas"? ¿Qué debería hacer exactamente el hardware? Todavía tiene que atravesar todas las referencias entre objetos, lo que significa que tiene que pasar por 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é cree que necesita recogida 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.

Answer 3

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.

Answer 4

Una solución obvia era tener punteros de memoria que son más grandes que su 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). El Oberon machines en el ETH Zurich usó 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 proporciona 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 podría no ser posible tener esa cantidad de RAM alguna vez). Esto significa que puede usar un par de bits en las máquinas de hoy si la VM puede indicarle al sistema operativo cómo mapear la memoria.

Answer 5

Probablemente la información más relevante que se necesita aquí es, ¿cuánto tiempo (porcentaje de tiempo de CPU) se 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á jugando 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.

Mire lo que acaba de aparecer ... in another post ... Mirando el registro de GC de java.

Answer 6

Ha habido an article on lambda the ultimate que describe cómo necesita un administrador de memoria virtual compatible con GC para tener un GC realmente eficiente, y la asignación de VM se realiza principalmente por hardware en estos días. Aquí está :)

Answer 7

Sí. Mira las secciones de trabajo relacionados de estos 2 documentos:

https://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/index.htm http://www.filpizlo.com/papers/pizlo-ismm2007-stopless.pdf

O al este:

http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon12StallFree.pdf

Answer 8

que reúnen el mayor problema es registros de la CPU y la pila. Una de las cosas que tiene que hacer durante GC es atravesar 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 los 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.

Answer 9

Los sistemas sparc 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 ahora un nodo molesta etiquetar cosas.

comentarios de runT1mes acerca de hardware asistido generacional GC vale la pena leer.

teniendo en cuenta una matriz de compuertas suficientemente grande (me viene a la mente vertex-III) podría ser posible una MMU mejorada que admitiera las actividades de GC.

Answer 10

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 libre disponible en http://www.opencores.org/

La recolección de basura se puede implementar como una tarea en segundo plano, ya está prevista para el funcionamiento paralelo.

Pete

Answer 11

Varios grandes mentes en el MIT en los años 80 crearon el chip SCHEME-79, que interpreta directamente un dialecto del Esquema, fue diseñado con una SL de LISP, y habían hardware-gc incorporado.