Jank Busters Partie Deux : Orinoco

Dans un article de blog précédent, nous avons introduit le problème du jank causé par la collecte des déchets interrompant une expérience de navigation fluide. Dans cet article, nous présentons trois optimisations qui posent les bases d'un nouveau ramasse-miettes dans V8, nommé Orinoco. Orinoco repose sur l'idée qu'implémenter un ramasse-miettes majoritairement parallèle et concurrent sans frontières générationnelles strictes réduira le jank causé par la collecte des déchets et la consommation mémoire tout en fournissant un haut débit. Au lieu d'implémenter Orinoco derrière un drapeau comme un ramasse-miettes distinct, nous avons décidé de déployer les fonctionnalités d'Orinoco de manière incrémentale dans la version principale de V8 pour en faire bénéficier immédiatement les utilisateurs. Les trois fonctionnalités discutées dans cet article sont le compactage parallèle, le traitement parallèle de l'ensemble mémorisé, et l'allocation en noir.

V8 implémente un ramasse-miettes générationnel où les objets peuvent être déplacés à l'intérieur de la jeune génération, de la jeune génération vers la vieille génération, et au sein de la vieille génération. Déplacer des objets est coûteux puisque la mémoire sous-jacente des objets doit être copiée vers de nouvelles emplacements et les pointeurs vers ces objets doivent également être mis à jour. La Figure 1 montre les phases et comment elles étaient exécutées avant Orinoco. Essentiellement, les objets étaient d'abord déplacés puis les pointeurs entre ces objets étaient mis à jour ensuite, le tout dans un ordre séquentiel, entraînant un jank observable.

V8 divise sa mémoire gérée en morceaux de taille fixe, appelés pages, qui sont attribués à des espaces de génération jeune ou vieille. Les objets sont initialement alloués dans la jeune génération. Lors de la collecte des déchets, les objets vivants sont déplacés une fois à l'intérieur de la jeune génération. Les objets qui survivent à une autre collecte des déchets sont promus à la vieille génération. Pour les deux phases, que nous appelons collectivement évacuation générationnelle jeune, nous parallélisons la copie de mémoire basée sur les pages. À l'intérieur de la jeune génération, déplacer des objets implique toujours d'allouer de la mémoire sur de nouvelles pages (et de libérer les anciennes pages), laissant derrière une disposition mémoire compacte. Dans la vieille génération, ce processus diffère légèrement, car la mémoire morte laisse des trous inutilisables (ou fragmentation). Certains de ces trous peuvent être réutilisés via des listes libres, mais d'autres restent comme tels, nécessitant un compactage pour déplacer les objets vivants vers une page mieux arrangée (potentiellement nouvelle). Similairement à la jeune génération, ce processus est parallélisé au niveau des pages.

Puisqu'il n'y a pas de dépendances entre l'évacuation générationnelle jeune et le compactage de la vieille génération, Orinoco effectue maintenant ces phases en parallèle, comme illustré dans la Figure 2. Le résultat de ces améliorations est une réduction du temps de compactage de 75 %, passant d'environ 7ms à moins de 2ms en moyenne.

La deuxième optimisation introduite par Orinoco améliore la façon dont la collecte des déchets suit les pointeurs. Lorsqu'un objet change d'emplacement dans le tas, le ramasse-miettes doit trouver tous les pointeurs contenant l'ancien emplacement de l'objet déplacé et les mettre à jour avec le nouvel emplacement. Puisqu'itérer dans le tas pour trouver les pointeurs serait très lent, V8 utilise une structure de données appelée ensemble mémorisé (remembered set) pour suivre tous les pointeurs intéressants dans le tas. Un pointeur est intéressant s'il pointe à un objet susceptible de bouger pendant la collecte des déchets. Par exemple, tous les pointeurs de la vieille génération vers la jeune génération sont intéressants car les objets de la jeune génération bougent à chaque collecte des déchets. Les pointeurs vers des objets dans des pages fortement fragmentées sont également intéressants car ces objets se déplaceront vers d'autres pages pendant le compactage.

Auparavant, V8 implémentait des ensembles mémorisés comme des tableaux d'adresses de pointeurs, ou tampons de stockage. Il y avait un tampon de stockage pour la jeune génération et un pour chacune des pages fragmentées de l'ancienne génération. Le tampon de stockage d'une page contient les adresses de tous les pointeurs entrants, comme le montre la Figure 3. Les entrées sont ajoutées à un tampon de stockage dans une barrière d'écriture, qui sécurise les opérations d'écriture dans le code JavaScript. Cela peut entraîner des entrées en double puisque qu'un tampon de stockage peut inclure un pointeur plusieurs fois et que deux tampons de stockage différents peuvent inclure le même pointeur. Les entrées en double compliquent la parallélisation de la phase de mise à jour des pointeurs en raison de la concurrence de données causée par deux threads essayant de mettre à jour le même pointeur.

Orinoco élimine cette complexité en réorganisant l'ensemble mémorisé pour simplifier la parallélisation et s'assurer que les threads obtiennent des ensembles disjoints de pointeurs à mettre à jour. Au lieu de stocker les pointeurs entrants intéressants dans un tableau, chaque page stocke désormais les décalages des pointeurs intéressants provenant de cette page dans des blocs de bitmaps, comme le montre la Figure 4. Chaque bloc est soit vide, soit pointe vers un bitmap d'une longueur fixe. Un bit dans le bitmap correspond à un décalage de pointeur dans la page. Si un bit est activé, le pointeur est intéressant et fait partie de l'ensemble mémorisé. Grâce à cette structure de données, nous pouvons paralléliser les mises à jour de pointeurs en fonction des pages. L'absence d'entrées en double et la représentation dense des pointeurs nous ont également permis de supprimer le code complexe destiné à gérer le débordement des ensembles mémorisés. Dans notre test sur Gmail à long terme, ce changement a réduit le temps de pause maximum du compactage de la collection des déchets de 45 %, passant de 42 ms à 23 ms.

La troisième optimisation qu'Orinoco introduit est l'allocation noire, une amélioration de la phase de balisage du ramasse-miettes. L'allocation noire (déployée dans V8 5.1) est une technique de collecte des déchets dans laquelle tous les objets alloués dans l'ancienne génération (par exemple, les allocations pré-tenues ou les objets promus par le ramasse-miettes) sont immédiatement marqués en noir afin de les désigner comme "vivants". L'intuition derrière l'allocation noire est que les objets alloués dans l'ancienne génération sont probablement de longue durée. Par conséquent, les objets récemment alloués dans l'ancienne génération devraient au moins survivre à la prochaine collecte des déchets de l'ancienne génération, sinon ils auraient été faussement promus. Après avoir coloré les nouveaux objets alloués en noir, le ramasse-miettes ne les visitera plus. Nous accélérons la coloration des objets noirs en les allouant sur des pages noires où tous les objets sont noirs par défaut. Un autre avantage des pages noires est qu'elles n'ont pas besoin d'être balayées, puisque tous les objets qui y sont alloués sont (par définition) vivants. L'allocation noire accélère les progrès du marquage incrémentiel, car le travail de marquage n'augmente pas avec les nouvelles allocations. L'impact de l'allocation noire est clairement visible sur le benchmark Octane Splay, où le score de débit et de latence s'est amélioré d'environ 30 %, tout en utilisant environ 20 % de mémoire en moins grâce à une progression plus rapide du marquage et à une réduction globale du travail de collecte des déchets.

Nous prévoyons de déployer bientôt davantage de fonctionnalités Orinoco. Restez à l'écoute, nous sommes encore en train de bricoler !