GoSuda

Le moment de détente d'une tasse de thé vert que le runtime de Go nous dérobera, GreenTea GC

By snowmerak views ...

Pourquoi un nouveau GC arrive-t-il encore ?

Pourquoi le GC existant

Le GC actuel de Go peut être décrit de la manière suivante.

  • concurrent tri-color mark and sweep
    • Il utilise au total trois couleurs (blanc, gris, noir) pour suivre l'état des objets.
      • Blanc : objet non encore visité
      • Gris : objet visité dont tous les objets enfants n'ont pas encore été visités
      • Noir : objet dont tous les objets enfants ont été visités
      • Une fois le parcours terminé, tous les objets blancs sont collectés.
    • Il utilise une Write Barrier pour protéger la mémoire nouvellement créée pendant le GC.
      • Le temps d'activation et de désactivation de la Write Barrier représente une grande part de ce que l'on appelle communément Stop-The-World (ci-après STW).
    • Ce processus est exécuté de manière concurrente.
  • No Compaction
    • Le GC de Go n'effectue pas de compaction.
    • Une fragmentation de la mémoire peut survenir.
      • Toutefois, les objets de 32 Ko ou moins exploitent le cache par P de l'allocateur de mémoire (Allocator) du langage Go afin de minimiser la fragmentation.
  • Non-Generational
    • Le GC de Go ne gère pas les objets par générations.
    • Tous les objets appartiennent à la même génération.
  • Escape Analysis
    • Go détermine, grâce à l'Escape Analysis, si un objet est alloué sur le tas ou sur la pile.
    • De manière approximative, on peut considérer qu'un objet est alloué sur le tas s'il s'agit d'un pointeur pendant (dangling pointer) ou s'il utilise une interface.

Ce qui est important

Le GC de Go explore tous les objets à partir des racines (roots) et exécute le marquage tri-couleur. Si l'on résume ce processus en une seule ligne, on peut le qualifier d'algorithme de parcours concurrent de graphe par tri topologique. Cependant, chaque objet se trouve probablement dans une zone mémoire différente. Concrètement :

  1. Supposons qu'il existe deux zones mémoire distantes d'environ 32 Mo l'une de l'autre.
  2. Cinq objets sont alloués dans chacune de ces deux zones mémoire.
    1. Les objets A, B et C se trouvent dans la zone 1.
    2. Les objets D et E se trouvent dans la zone 2.
  3. L'ordre de référence des objets est A -> D -> B -> E -> C.
  4. Lorsque le GC démarre, il visite A, puis D, puis B, puis E, puis C.
  5. Or, A et D se trouvent dans des zones mémoire différentes ; par conséquent, la visite de A puis celle de D impliquent un changement de zone mémoire.
  6. Ce processus entraîne des changements de zone mémoire et le remplissage de nouvelles lignes de cache, ce que l'on appelle le coût de saut mémoire (memory jump cost). Une part importante du temps CPU utilisé par l'application peut alors être consacrée à ce travail de GC.
  7. Ce coût continue de survenir pendant toute la durée du GC.

Quel est le problème ?

Ce comportement du GC pose problème dans les cas suivants.

  • Lorsque le nombre de cœurs est élevé et que la mémoire est volumineuse
    • Le GC de Go s'exécute par défaut de manière concurrente.
    • Toutefois, si la zone mémoire est vaste et que les objets sont dispersés, plusieurs cœurs explorent simultanément des objets répartis dans des espaces mémoire variés.
    • Si le bus entre le CPU et la mémoire n'est pas suffisamment large, la bande passante mémoire peut devenir un goulot d'étranglement.
    • De plus, la distance physique réelle fait que chaque exploration entraîne un délai relativement important.
  • Lorsque les petits objets sont nombreux
    • Si vous exploitez en Go des arbres ou des graphes profonds ou à nombreux enfants, le GC doit parcourir l'ensemble de ces objets.
    • Si ces objets sont dispersés dans différentes zones mémoire, un délai survient en raison de la première raison évoquée.
    • De plus, lorsque les petits objets sont nombreux, le GC doit tous les parcourir, de sorte que pendant son exécution, une part considérable des ressources des cœurs CPU est consacrée au GC.

Pour résoudre ces problèmes, l'équipe Golang a présenté le GC GreenTea.

Vous n'avez plus le temps de boire du thé vert

Ce qui prive du thé vert

La zone où appliquer la solution la plus rapide au GC existant semble être la localité mémoire. Autrement dit, il s'agit de rapprocher les objets les uns des autres afin de minimiser les sauts mémoire. Cependant, on ne peut pas imposer de schémas de codage aux programmeurs, et l'allocation des objets est imprévisible selon le flux de travail.

C'est peut-être pour cette raison que l'équipe Golang a choisi la méthode Memory Span (span mémoire).

Qu'est-ce qu'un Memory Span ?

Un Memory Span est une zone mémoire relativement grande, allouée pour y placer de petits objets. Le nouveau GC appelé GreenTea GC effectue la collecte des déchets sur ces spans mémoire. Les détails de fonctionnement sont presque identiques à ceux du Tri-Color Mark and Sweep existant.

Fonctionnement du GC GreenTea

Tout d'abord, le GreenTea GC alloue un Memory Span. Sa taille, comme indiqué précédemment, est de 8 Kio, une taille suffisamment conséquente. Il peut y allouer des objets d'au plus 512 octets. C'est à peu près la taille que l'on peut raisonnablement attendre pour un nœud d'arbre ou de graphe comme dans l'exemple, ou pour une structure qui s'échappe typiquement vers le tas. Les objets de 512 octets ou moins sont empilés dans ce Memory Span à chaque fois qu'ils s'échappent vers le tas, et lorsque ce Memory Span est plein, un nouveau Memory Span est alloué.

Ensuite, lorsque le GC se déclenche, le GreenTea GC place ces Memory Spans dans une file d'attente et les examine séquentiellement. Dans ce processus, le GreenTea GC utilise un ordonnancement presque similaire au modèle GMP existant. Des mécanismes tels que le vol de travail (work stealing) sont également implémentés. Quoi qu'il en soit, le worker qui extrait un Memory Span de la file examine les objets internes du Memory Span qui lui est assigné. Dans ce processus, le même Tri-Color Mark and Sweep est utilisé.

Quel en est l'avantage ?

Dans ce processus, la différence avec le GC existant tient, à grands traits, à un seul point : l'unité de travail du GC, qui était auparavant l'objet, devient le Memory Span. Grâce à cela, le GC présente les avantages suivants.

  • Localité mémoire : les objets étant regroupés dans un Memory Span, les sauts mémoire sont minimisés lors de l'exploration des objets. Autrement dit, le cache CPU peut être exploité au maximum.
  • Amélioration des performances du GC : en effectuant le GC par unité de Memory Span, le GC fonctionne plus efficacement dans un environnement multicœur.
  • Optimisation de l'allocation mémoire : les Memory Spans étant alloués à taille fixe, le surcoût d'allocation des petits objets diminue et le risque de fragmentation est réduit. Cela améliore également l'efficacité de la libération de la mémoire.

En bref, il devient désormais possible d'allouer plus souvent et plus sereinement des objets de 512 octets ou moins.

Toutefois, cette approche présente aussi certains cas favorables.

  • Structures arborescentes et de graphes : lorsque le degré sortant (fan-out) est élevé et que les modifications sont rares
    • B+ trees, Trie, AST (Abstract Syntax Tree)
    • Structures de données favorables au cache
  • Traitement par lots : workflows impliquant l'allocation massive de petites données
    • Nombreux petits objets générés lors de l'analyse JSON
    • Objets DAO issus des jeux de résultats de base de données

Dans ces cas, le GreenTea GC peut offrir de meilleures performances que le GC existant. Cependant, il ne s'applique pas à tous les cas, et il est particulièrement difficile d'attendre une amélioration spectaculaire lorsque les objets sont dispersés dans différentes zones mémoire.

Conclusion

L'équipe Golang envisage vraisemblablement de continuer à améliorer le GC à long terme. Ce GreenTea GC peut être considéré comme une modification mineure portant sur un domaine restreint, et il ne remplace pas le GC existant. Néanmoins, le GreenTea GC constitue un cas intéressant qui laisse entrevoir les problèmes auxquels l'équipe Golang est confrontée ou qu'elle anticipe. Bien que le problème soit étonnamment complexe, la tentative de le résoudre par l'ajout d'un concept relativement simple m'a également paru remarquable. Personnellement, je considère qu'il s'agit d'un cas intéressant.

Le GreenTea GC est une fonctionnalité expérimentale introduite à partir de Go 1.25. Il peut être activé en définissant la variable d'environnement GOEXPERIMENT=greenteagc. Cette fonctionnalité étant encore expérimentale, des tests approfondis sont nécessaires avant toute utilisation en environnement de production.

Références