Explicación del recolector de basura de Azul "pauseless"

Question

acabo de leer esto:

http://www.artima.com/lejava/articles/azul_pauseless_gc.html

Aunque tengo algo de experiencia con los compiladores, no he hecho nada relacionado con la recolección de basura; es una gran caja negra para mí.

He luchado para comprender los problemas mencionados en el artículo. Entiendo el problema (hay una pausa al ejecutar la mayoría de los recolectores de basura) y entiendo que afirman que su implementación no tiene ese problema. Pero no entiendo por qué/cómo ocurre el problema en primer lugar (parece que se supone que todo eso se entiende en el texto original) y, en consecuencia, no entiendo por qué su solución podría funcionar.

Puede alguien explicarme:

1. por qué los recolectores de basura tienen que hacer una pausa en general
2. qué GC de Azul no tiene ese problema?

Tiendo a comprender este tipo de cosas mejor cuando se explica gráficamente, probablemente bastaría con un pequeño esquema de memoria hecho con el editor de código.

Gracias!

Answer 1

Hablan sobre la pausa que inevitablemente se produce al compactar el montón. Verá, cuando asigna y desasigna muchos objetos de diferentes tamaños sobre la marcha, fragmenta el montón (al igual que fragmenta su disco duro). Cuando la fragmentación se vuelve demasiado extrema, tienes que limpiar/desfragmentar/compactar el montón al reservar una gran cantidad de memoria, mover todos los objetos allí (sin ninguna fragmentación) y usar sus ubicaciones anteriores como un trozo de memoria fresco sin ningún objeto en él. , es decir, sin fragmentación.

Al hacer eso, invalidará todas las referencias a todos los objetos que haya movido. Para evitar esto, debe evitar que se utilice una referencia que haga referencia a la ubicación de un objeto de precompactación. La forma más fácil de hacerlo es detener toda la aplicación, mover los objetos y luego actualizar todas las referencias. Por supuesto, esto puede incurrir en una sobrecarga significativa.

Así que la solución que propone Azul es la siguiente: Establecen una "barrera de lectura" que permite al GC interceptar la desreferenciación, y de esta manera pueden actualizar de manera lenta las referencias que realmente se usan.

Answer 2

¿Por qué un recolector de basura no simplemente mprotect(region_it's_working_on, PROT_READ) e implementa un controlador SIGSEGV que actualiza todos los punteros al objeto accedido? Sí, tendrías que seguir todos los punteros a un objeto, por supuesto.

Answer 3

¿por qué los recolectores de basura tienen esa pausa en general?

Los GC funcionan mediante el rastreo de bloques de pila alcanzables a partir de un conjunto de raíces globales (variables globales, pilas de subprocesos y registros de CPU). Los GC se encuentran en una escala móvil desde instantánea a sobre la marcha. Los GC de instantáneas funcionan a partir de una instantánea de las raíces globales y la topología de montón. Los GCs sobre la marcha actualizan de forma incremental su interpretación del montón a medida que se ejecutan los mutadores.

Los GC de instantáneas completas logran un alto rendimiento porque el recolector funciona casi por completo independientemente de los mutadores pero tiene una alta latencia porque tomar una instantánea provoca una pausa.Los GC completamente sobre la marcha alcanzan una baja latencia porque todo se hace de forma incremental pero con un rendimiento bajo debido a la comunicación de grano fino entre los mutadores y GC.

En la práctica, todos los GC se encuentran en algún lugar entre estos dos extremos. VCGC es principalmente un GC instantánea sino que utiliza una barrera de escritura para mantener el colector al tanto de los cambios en la topología montón. Staccato fue el primer GC en tiempo real paralelo y concurrente y del mundo pero aún lotes de hasta algunas operaciones con el fin de mantener la eficiencia de la asignación de pila.

¿por qué Azul's gc no tiene ese problema?

Todavía tienen este problema, pero lo redujeron al implementar una barrera de lectura en el hardware. Las barreras de lectura se habían propuesto antes, pero las barreras de lectura de software degradan demasiado el rendimiento porque las lecturas de los indicadores son mucho más comunes que las escrituras.

Answer 4

por qué los recolectores de basura tienen que hacer una pausa en general?

trabajo GCs mediante el trazado de bloques de montón alcanzables a partir de un conjunto de raíces globales (variables globales, pilas hilos y registros de la CPU). Los GC se encuentran en una escala móvil desde instantánea a sobre la marcha. Los GC Snapshot funcionan a partir de una instantánea de las raíces globales y la topología de montón. On-the-fly GCs actualiza incrementalmente su interpretación del montón a medida que se ejecutan los mutadores.

rastreo no es "¿por qué los recolectores de basura tienen que hacer una pausa en general", hay razones más grandes para hacer una pausa: reubicación objeto que está siendo el dominante.

Pero hasta el punto de los trazadores sobre la marcha frente a los trazadores de instantáneas y su eficiencia relativa: el trazado sobre la marcha puede ser más eficiente que los trazadores de instantáneas al comienzo. El mismo documento al que se refiere al describir [VCGC] clasifica al coleccionista Pauseless anterior, no generacional de Azul, como un trazador preciso de frente de onda [3]:

"... La mayoría de los colectores prácticos usan abstracciones conservadoras del frente de onda en lugar del preciso definición es aquí. Es decir, el frente de onda se rastrea en una granularidad de objetos. Sin embargo, el frente de onda preciso no es meramente teórico y ha sido utilizado recientemente en el colector asistido por hardware para el servidor Azul Java, que tiene un "no marcado" "Mordió en cada puntero [2]".

Azul's C4 comparte esta calidad, pero la logra usando una barrera de lectura de LVB de software puro y autocuración.

enteramente instantánea GCs alcanzar un alto rendimiento debido a que el colector se extiende casi por completo independientemente de los mutators pero tienen alta latencia porque la toma de una instantánea incurre en una pausa. totalmente de la marcha GC lograr una baja latencia porque todo se hace de forma incremental, pero baja rendimiento debido a la comunicación de grano fino entre los mutadores y GC.

un trazador de frente de onda precisa es tan eficiente (desde el punto de vista discutido en el documento "no gastar tiempo en los objetos que no sean necesarios") como trazador stop-el-mundo, que por definición tienen también un recise frente de ondaEn comparación con los enfoques basados ​​en instantáneas, el escaneo preciso del frente de onda no reduce el rendimiento de ninguna manera ni requiere más comunicación entre el colector y el mutador. Tiene un rendimiento tan bueno o mejor, ya que su precisión asegura que nunca tenga que repetir ningún trabajo de rastreo.

¿por qué Azul's gc no tiene ese problema?

Todavía tienen este problema, pero lo redujeron al implementar una barrera de lectura en el hardware. Las barreras de lectura se habían propuesto anteriormente, pero las barreras de lectura de software degradan demasiado el rendimiento porque las lecturas del puntero son mucho más comunes que las escrituras.

Como se ha señalado, si el "problema" era debido a la ineficiencia en la marcha contra el comportamiento instantánea, C4 no tiene porque es un trazador de frente de onda precisa. Además, el colector C4 de Azul no necesita ni usa una barrera de lectura de hardware, ya que funciona en sistemas vanilla x86 y Linux, y logra un mejor rendimiento en ese hardware que los colectores de seguimiento basados ​​en instantáneas (ver comparaciones de rendimiento en [1]).

Sin embargo, "el problema" en la pregunta se expresó como "¿por qué los recolectores de basura tienen esa pausa en general?" La precisión del frente de onda (o no) tiene poco que ver con las pausas dominantes en los recolectores de basura. Los marcadores concurrentes y mayormente concurrentes (incluso si son menos eficientes que C4) sí existen, pero sus recolectores aún hacen una pausa. El problema es que el rastreo es solo una parte de la recopilación. El rastreo solo te dice qué está vivo y dónde está. No le devuelve ningún recuerdo, y ciertamente no elimina el fragmento de la memoria fragmentada. Ese tema se discute en profundidad en varios documentos académicos (ver un montón de referencias de C4 papel [1]).

Es la compactación (y la reubicación de objeto implícita) que parece ser el talón de Aquiles de los colectores de envío actualmente en las JVM del servidor, y lo que provoca inherentemente que tomen pausas [grandes]. El simple acto de reubicar incluso un único objeto de un lugar a otro significa que tiene que REPARAR todas las referencias que apuntan a ese objeto antes de que el programa las use. Para la mayoría de los coleccionistas de envío comercial, esto significa una pausa mundial que evita que la aplicación se ejecute mientras se reparan las referencias.

C4 aprovecha la barrera autocompactante LVB (un nuevo tipo de barrera de lectura introducida en [2] y utilizada en gran medida en [1] en forma de software) para evitar tener que arreglar referencias antes de que la aplicación pueda ejecutarse . Así es como evita la pausa que otros coleccionistas terminan teniendo que tomar. La calidad de autorreparación reduce el costo dinámico de las barreras de lectura en varios órdenes de magnitud en comparación con las barreras previas que no se autorreparan (como la barrera al estilo de los riachuelos utilizada en otros compactadores concurrentes en trabajos académicos, y en algunos casos reales). coleccionistas de tiempo). El resultado de este costo de barrera de lectura dramáticamente menor es que es práctico para su uso en la recopilación generacional y en las JVM a escala de servidor.

[1]: "C4: el colector de compactación continuamente concurrente" http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL&CFID=85063603&CFTOKEN=84074207 [2]: "El Pauseless GC Algoritmo" http://static.usenix.org/events/vee05/full_papers/p46-click.pdf [3]: "Derivación de Algoritmos recolección de basura concurrentes corrección-Preservar" www.srl. inf.ethz.ch/papers/pldi06-cgc.pdf

(Graham Thomas, director técnico de la EMEA, Azul Systems)