03 - Le garbage collector

Ce que tu vas apprendre

• Le comptage de références et son problème avec les cycles
• L'algorithme mark-and-sweep utilise par V8
• Le tri-color marking et les pauses stop-the-world
• Le GC incremental et concurrent
• Quand le GC se déclenché (et pourquoi c'est non déterministe)

Prerequisites

• Avoir lu Le cycle de vie de la mémoire
• Comprendre la notion d'accessibilité (reachability)

La poubelle intelligente

Quand j'explique le garbage collector a des juniors, je leur dis de penser a un service de voirie intelligent. Il passe quand il veut, ramasse ce qui traine, mais il ne touche jamais a ce qui est encore utilise. Le problème ? Si tu laisses un fil attache entre ta maison et un vieux meuble sur le trottoir, le service considéré que le meuble t'appartient encore.

Le GC, c'est pareil. Tant qu'il y a un chemin de références depuis une racine vers un objet, l'objet est considéré vivant.

L'ancienne approche : le comptage de références

La première idee pour gerer la mémoire automatiquement, c'est de compter combien de références pointent vers chaque objet. Quand le compteur tombe a zero, on libéré.

typescript// Principe du reference counting (pseudo-code)
let obj = { data: "hello" };  // refcount = 1
let ref2 = obj;                // refcount = 2
ref2 = null;                   // refcount = 1
obj = null;                    // refcount = 0 -> libere !

Ca marche bien... jusqu'aux références circulaires :

typescriptfunction createCycle() {
  const a: any = {};
  const b: any = {};
  a.ref = b;  // a reference b
  b.ref = a;  // b reference a
  // refcount de a = 1 (via b.ref)
  // refcount de b = 1 (via a.ref)
}

createCycle();
// Apres le return, ni a ni b ne sont accessibles
// Mais leurs refcounts sont toujours a 1
// Avec du reference counting pur, c'est une fuite memoire !

  +-------+       +-------+
  |   a   | ----> |   b   |
  |       | <---- |       |
  +-------+       +-------+
  refcount=1      refcount=1

  Aucun chemin depuis les racines,
  mais les refcounts ne tombent jamais a 0.

Internet Explorer 6 et 7 utilisaient du référencé counting pour les objets DOM. C'est pour ca que les fuites mémoire etaient si frequentes a cette epoque. Les vieux devs frontend s'en souviennent avec douleur.

L'approche moderne : mark-and-sweep

Tous les moteurs JavaScript modernes (V8, SpiderMonkey, JavaScriptCore) utilisent une variante de mark-and-sweep. L'idee :

1. Mark : partir des racines, suivre toutes les références, marquer chaque objet atteignable comme "vivant"
2. Sweep : parcourir tout le heap, libérer tout ce qui n'est pas marque

Phase Mark :

  RACINES
    |
    +---> [A] marque -----> [B] marque
    |                         |
    +---> [C] marque          +---> [D] marque

  [E] non marque    [F] non marque

Phase Sweep :

  [A] garde    [B] garde
  [C] garde    [D] garde
  [E] LIBERE   [F] LIBERE

Avec mark-and-sweep, les cycles ne posent plus de problème. Si a et b se referencent mutuellement mais qu'aucune racine ne mene a eux, ils ne sont pas marques et sont liberes.

Tri-color marking

V8 utilise une version optimisee appellee tri-color marking. Chaque objet est dans un des trois états :

• Blanc : pas encore visite (potentiellement garbage)
• Gris : visite, mais ses références pas encore parcourues
• Noir : visite, toutes ses références parcourues

Debut : tout est blanc
  (o) (o) (o) (o) (o)    o = blanc

Etape 1 : les racines deviennent grises
  [o] (o) (o) (o) (o)    [o] = gris

Etape 2 : on traite les gris -> noir, leurs enfants -> gris
  {o} [o] [o] (o) (o)    {o} = noir

Etape 3 : on continue jusqu'a plus de gris
  {o} {o} {o} (o) (o)

Fin : les blancs sont du garbage
  {o} {o} {o}  X   X     X = libere

L'avantage du tri-color, c'est qu'on peut interrompre le marquage et le reprendre plus tard. C'est la base du GC incremental.

Les pauses stop-the-world

Un GC "stop-the-world" arrêté l'exécution du code JavaScript pendant qu'il fait son travail. Pendant une pause GC, ton code ne tourne pas. Pas de rendu, pas de réponse aux events, pas de traitement de requêtes.

Sur un vieux navigateur, une pause GC pouvait durer 100ms ou plus. Sur une animation a 60fps, ca veut dire 6 frames perdues. L'utilisateur voit un saccade.

V8 a beaucoup travaille pour réduire ces pauses :

Approche naive (stop-the-world complet) :

  JS: ====|          |====================
  GC:     |==========|
          ^          ^
          pause      reprise
          (100ms+)

Approche V8 moderne (incremental + concurrent) :

  JS: ====|=|====|=|====|=|==============
  GC:     |=|    |=|    |=|  (incremental, petites pauses)
       +  ------GC concurrent en background------

GC incremental et concurrent

V8 utilise deux techniques pour minimiser les pauses :

Incremental : le marquage est coupe en petits morceaux. V8 marque quelques objets, rend la main au JS, marque encore, rend la main. Chaque micro-pause dure moins d'1ms.

Concurrent : une partie du travail GC se fait dans un thread séparé, pendant que le JS tourne. Le sweep (libération) est entièrement concurrent dans V8. Le thread principal n'est pas bloque.

Le résultat : les pauses GC dans V8 moderne sont généralement sous 1ms, meme avec des heaps de plusieurs Go. C'est pour ca que tu ne "sens" pas le GC en temps normal.

Quand le GC se déclenché

Le GC n'a pas de timer. Il ne se déclenché pas toutes les X secondes. Voici ce qui le provoque :

1. Allocation trigger : quand la young génération est pleine (minor GC) ou quand le heap approche de sa limite (major GC)
2. Idle time : V8 profite des moments ou le moteur n'a rien a faire (entre deux frames par exemple) pour faire du GC
3. Pression mémoire : si l'OS signale un manque de RAM, V8 peut forcer un GC

typescript// Tu ne peux pas forcer un GC en JavaScript standard
// Mais en Node.js avec le flag --expose-gc :
// global.gc(); // force un GC (utile pour le profiling, jamais en prod)

Le point a retenir : le GC est non déterministe. Tu ne sais pas quand il va passer. Tu ne sais pas combien de mémoire il va libérer. Tu ne peux pas compter dessus pour un timing precis.

Le GC n'est pas gratuit

Meme avec les optimisations de V8, le GC a un coût :

• Chaque objet alloue devra etre parcouru par le GC a un moment
• Plus tu alloues d'objets, plus le GC a de travail
• Des milliers d'objets temporaires = des milliers de marquages

C'est pour ca que les patterns qui reduisent les allocations (object pooling, mutation en place, pre-allocation) peuvent avoir un impact mesurable sur les performances. On en reparlera dans les articles suivants.

Sur paltemps.fr, j'ai mesure qu'en passant de la création de 10 000 objets temporaires par requête a la réutilisation d'un pool, le temps de réponse au P99 a baisse de 15%. Pas grâce à l'allocation elle-meme (elle est rapide), mais grâce à la réduction de la pression GC.

Résumé

• Le référencé counting est simple mais ne gere pas les cycles. Il n'est plus utilise seul.
• Le mark-and-sweep part des racines, marque les vivants, libéré le reste. Il gere les cycles.
• V8 utilise le tri-color marking pour pouvoir interrompre et reprendre le marquage.
• Les pauses stop-the-world sont minimisees par le GC incremental et concurrent.
• Le GC est non déterministe : il se déclenché quand il veut, pas quand tu veux.

Precedent : Cycle de vie de la mémoire Suivant : V8 en profondeur

Sources

• V8 Blog - Trash talk: the Orinoco garbage collector
• MDN - Memory management
• Vyacheslav Egorov - A tour of V8: Garbage Collection