yugioh recolector example collector collection basura garbage-collection

garbage-collection - recolector - garbage collector yugioh



Explicación del recolector de basuras "sin pausa" de Azul (4)

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

Los GC funcionan mediante el rastreo de bloques de pila accesibles a partir de un conjunto de raíces globales (variables globales, pilas de hilos 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 totalmente instantáneos alcanzan 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 una instantánea GC, pero utiliza una barrera de escritura para mantener informado al recopilador de los cambios en la topología del montón. Staccato fue el primer GC paralelo, concurrente y en tiempo real del mundo, pero aún agrupa algunas operaciones para retener la eficiencia de la asignación de stack.

¿Por qué el gc de Azul 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.

Acabo de leer esto:

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

Aunque tengo cierta 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 esa pausa en general
  2. ¿Por qué el gc de Azul no tiene ese problema?

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

¡Gracias!


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

Los GC funcionan mediante el rastreo de bloques de pila accesibles a partir de un conjunto de raíces globales (variables globales, pilas de hilos 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.

El seguimiento no es "por qué los recolectores de basura tienen esa pausa en general", hay razones más importantes para hacer una pausa: la reubicación del objeto es la dominante.

Pero hasta el punto de los trazadores sobre la marcha y 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 en el comienzo. El mismo documento al que se refiere al describir [VCGC] clasifica al coleccionista anterior sin generación Pausaless de Azul como un trazador preciso de frente de onda [3]:

"... La mayoría de los coleccionistas prácticos utilizan abstracciones conservadoras del frente de onda en lugar de la definición precisa 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 se ha utilizado recientemente en el hardware coleccionista asistido para el servidor Azul Java, que tiene un bit "no marcado a través" en cada puntero [2] ".

El C4 de Azul comparte esta calidad, pero lo logra utilizando una barrera de lectura LVB de software puro y autocuración.

Los GC totalmente instantáneos alcanzan 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.

Un trazador de frente de onda preciso es tan eficiente (desde el punto de vista de "no perder tiempo en objetos innecesarios" discutido en el documento) como un rastreador de detener el mundo, que por definición también tiene un frente de onda recise. En 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é el gc de Azul 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.

Como se señaló, si "el problema" fue la ineficiencia debido al comportamiento sobre la marcha frente a la captura de instantáneas, entonces C4 no lo tiene porque es un marcador de frente de onda preciso. 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 estableció 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 objetos implícita) lo 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 solo 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 recopilador de compactación continuamente concurrente" http://dl.acm.org/citation.cfm?id=1993491&dl=ACM&coll=DL&CFID=85063603&CFTOKEN=84074207 [2]: "El algoritmo de GC sin pausa" http://static.usenix.org/events/vee05/full_papers/p46-click.pdf [3]: "Corrección de preservación de correción de algoritmos de recolección concurrente de basura" www.srl.inf.ethz.ch/papers/pldi06-cgc. pdf

(Graham Thomas, Gerente Técnico de EMEA, Azul Systems)


Hablan sobre la pausa que inevitablemente ocurre 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.

Cuando haces eso, invalidas todas las referencias a todos los objetos que moviste. 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.

Entonces, la solución que Azul propone 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.


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