Jank Busters Parte Dos: Orinoco
En una entrada de blog anterior, presentamos el problema del jank causado por la recolección de basura, que interrumpe una experiencia de navegación fluida. En esta entrada de blog introducimos tres optimizaciones que establecen las bases para un nuevo recolector de basura en V8, llamado Orinoco. Orinoco se basa en la idea de implementar un recolector de basura mayormente paralelo y concurrente sin límites generacionales estrictos, lo que reducirá el jank de la recolección de basura y el consumo de memoria, mientras proporciona un alto rendimiento. En lugar de implementar Orinoco detrás de una bandera como un recolector de basura separado, decidimos enviar las características de Orinoco de manera incremental en la rama principal de V8 para beneficiar a los usuarios de inmediato. Las tres características discutidas en esta publicación son compactación paralela, procesamiento paralelo del conjunto recordado y asignación negra.
V8 implementa un recolector de basura generacional donde los objetos pueden moverse dentro de la generación joven, de la generación joven a la generación vieja y dentro de la generación vieja. Mover objetos es costoso, ya que la memoria subyacente de los objetos necesita ser copiada a nuevas ubicaciones y los punteros a esos objetos también están sujetos a actualización. La Figura 1 muestra las fases y cómo se ejecutaban antes de Orinoco. Esencialmente, los objetos se movían primero y luego los punteros entre esos objetos se actualizaban después, todo en un orden secuencial, lo que resultaba en jank observable.
V8 divide su memoria del montón en fragmentos de tamaño fijo, llamados páginas, que se asignan a espacios de generación joven o vieja. Los objetos se asignan inicialmente en la generación joven. Durante la recolección de basura, los objetos vivos se mueven dentro de la generación joven una vez. Los objetos que sobreviven a otra recolección de basura se promocionan a la generación vieja. Para ambas fases, que llamamos colectivamente evacuación de generación joven, paralelizamos la copia de memoria basada en páginas. Dentro de la generación joven, mover objetos siempre implica asignar memoria en páginas nuevas (y liberar las páginas antiguas), dejando un diseño de memoria compacto. En la generación vieja, este proceso ocurre de manera ligeramente diferente, ya que la memoria muerta deja agujeros inutilizables (o fragmentación). Algunos de estos agujeros pueden reutilizarse mediante listas libres, pero otros quedan sin usar, requiriendo compactación para mover objetos vivos a una página mejor empacada (potencialmente nueva). Similar a la generación joven, este proceso se paraleliza a nivel de páginas.
Dado que no hay dependencias entre la evacuación de la generación joven y la compactación de la generación vieja, Orinoco ahora realiza estas fases en paralelo, como se muestra en la Figura 2. El resultado de estas mejoras es una reducción del tiempo de compactación del 75%, de ~7 ms a menos de 2 ms en promedio.
La segunda optimización introducida por Orinoco mejora cómo la recolección de basura rastrea punteros. Cuando un objeto cambia de ubicación en el montón, el recolector de basura tiene que encontrar todos los punteros que contienen la ubicación anterior del objeto movido y actualizarlos con la nueva ubicación. Dado que iterar a través del montón para encontrar los punteros sería muy lento, V8 utiliza una estructura de datos llamada conjunto recordado para rastrear todos los punteros interesantes en el montón. Un puntero es interesante si apunta a un objeto que puede moverse durante la recolección de basura. Por ejemplo, todos los punteros de la generación vieja a la generación joven son interesantes porque los objetos de la generación joven se mueven en cada recolección de basura. Los punteros a objetos en páginas altamente fragmentadas también son interesantes porque estos objetos se moverán a otras páginas durante la compactación.
Anteriormente, V8 implementaba conjuntos recordados como arreglos de direcciones de punteros, o buffers de almacenamiento. Había un buffer de almacenamiento para la generación joven y uno para cada una de las páginas fragmentadas de la generación antigua. El buffer de almacenamiento de una página contiene direcciones de todos los punteros entrantes, como se muestra en la Figura 3. Las entradas se añaden a un buffer de almacenamiento en una barrera de escritura, que protege las operaciones de escritura en el código JavaScript. Esto puede resultar en entradas duplicadas, ya que un buffer de almacenamiento puede incluir un puntero varias veces y dos buffers de almacenamiento distintos pueden incluir el mismo puntero. Las entradas duplicadas hacen que la paralelización de la fase de actualización de punteros sea difícil debido a la carrera de datos causada por dos hilos que intentan actualizar el mismo puntero.
Orinoco elimina esta complejidad reorganizando el conjunto recordado para simplificar la paralelización y asegurarse de que los hilos obtienen conjuntos disjuntos de punteros para actualizar. En lugar de almacenar punteros entrantes interesantes en un arreglo, cada página ahora almacena los desplazamientos de los punteros interesantes que se originan de esa página en grupos de mapas de bits, como se muestra en la Figura 4. Cada grupo está vacío o apunta a un mapa de bits de longitud fija. Un bit en el mapa de bits corresponde a un desplazamiento de puntero en la página. Si un bit está establecido, entonces el puntero es interesante y está en el conjunto recordado. Usando esta estructura de datos, podemos paralelizar las actualizaciones de punteros basándonos en las páginas. La ausencia de entradas duplicadas y la representación densa de punteros también nos permitió eliminar el código complejo para manejar desbordamientos del conjunto recordado. En nuestro benchmark de gran duración de Gmail, este cambio redujo el tiempo de pausa máximo de la recolección de basura compactadora en un 45%, de 42ms a 23ms.
La tercera optimización que Orinoco introduce es asignación negra, una mejora en la fase de marcado del recolector de basura. La asignación negra (implementada en V8 5.1) es una técnica de recolección de basura en la que todos los objetos asignados en la generación antigua (por ejemplo, asignaciones pre-prioritarias u objetos promovidos por el recolector de basura) se marcan como negros inmediatamente para designarlos como "vivos". La intuición detrás de la asignación negra es que los objetos asignados en la generación antigua probablemente tengan una vida larga. Por lo tanto, los objetos que fueron asignados recientemente en la generación antigua al menos deberían sobrevivir a la próxima recolección de basura de la generación antigua, de lo contrario fueron promovidos falsamente. Después de colorear los objetos recién asignados como negros, el recolector de basura no los visitará. Aceleramos el coloreado de objetos negros asignándolos en páginas negras donde todos los objetos son negros por defecto. Otro beneficio de las páginas negras es que no tienen que ser barridas, ya que todos los objetos asignados en ellas son (por definición) vivos. La asignación negra acelera el progreso del marcado incremental ya que el trabajo de marcado no aumenta con nuevas asignaciones. El impacto de la asignación negra es claramente visible en el benchmark Octane Splay, donde la puntuación de rendimiento y latencia mejoró en aproximadamente un 30% mientras se usaba aproximadamente un 20% menos de memoria debido al progreso más rápido del marcado y menos trabajo de recolección de basura en general.
Planeamos implementar más características de Orinoco pronto. ¡Sigan atentos, seguimos experimentando!