gc

Le travail du ramasse-miettes est de libérer la mémoire des objets qui ne sont plus utilisés, pour libérer de l'espace pour d'autres objets. Cette simple description cache une implémentation très complexe. L'histoire du ramasse-miettes remonte à plusieurs décennies, le langage Lisp des années 60 a été le premier à adopter un mécanisme de ramasse-miettes. Python et Objective-C utilisent principalement le comptage de références, Java et C# adoptent le ramasse-miettes générationnel. Aujourd'hui, en termes d'algorithmes de récupération, on peut大致 diviser en plusieurs catégories :

Comptage de références : chaque objet enregistre combien de fois il est référencé, quand le compteur atteint 0, il est récupéré
Marquage-balayage : les objets actifs sont marqués, les objets non marqués sont récupérés
Algorithme de copie : les objets actifs sont copiés dans une nouvelle mémoire, tous les objets de l'ancienne mémoire sont récupérés
Marquage-compression : version améliorée du marquage-balayage, lors de la récupération les objets actifs sont déplacés vers le début du tas, facilitant la gestion

En termes de mode d'application, on peut diviser en :

Récupération globale : récupère tous les objets en une seule fois
Récupération générationnelle : divise les objets en différentes générations selon leur temps de survie, puis utilise différents algorithmes
Récupération incrémentale : effectue une récupération partielle à chaque fois

TIP

Consultez The Journey of Go's Garbage Collector pour en savoir plus sur l'histoire du ramasse-miettes Go.

À sa sortie, le mécanisme de ramasse-miettes de Go était très rudimentaire, avec seulement un simple algorithme de marquage-balayage. Le STW (Stop The World,暂停整个程序 pour le ramasse-miettes) pouvait durer plusieurs secondes ou plus. L'équipe Go a commencé à améliorer l'algorithme. Entre go1.0 et go1.8, ils ont essayé plusieurs approches :

GC de copie concurrent avec barrière de lecture : les coûts de la barrière de lecture sont incertains, cette approche a été abandonnée
Collecteur orienté requête (ROC) : nécessite d'activer la barrière d'écriture en permanence, ralentit l'exécution
Récupération générationnelle : peu efficace en Go car le compilateur tend à allouer les nouveaux objets sur la pile, les objets de longue durée sur le tas
Marquage de cartes sans barrière d'écriture : remplace le coût de la barrière par un hachage, nécessite un support matériel

Finalement, l'équipe Go a choisi la combinaison marquage tricolore concurrent + barrière d'écriture, constamment améliorée dans les versions suivantes. Les images ci-dessous montrent l'évolution de la latence GC de go1.4 à go1.9.

Au moment d'écrire cet article, la dernière version de Go approche go1.23. Pour Go aujourd'hui, la performance GC n'est plus un problème. La latence GC est maintenant inférieure à 100 microsecondes dans la plupart des cas, satisfaisant la grande majorité des scénarios métier.

En résumé, le ramasse-miettes Go se divise en plusieurs phases :

Phase de balayage : collecte les objets racines depuis la pile et les variables globales
Phase de marquage : colorie les objets
Phase de terminaison du marquage : gère le nettoyage, désactive les barrières
Phase de récupération : libère et récupère la mémoire des objets poubelles

Concepts

Dans la documentation officielle et les articles, vous pouvez rencontrer les concepts suivants :

Mutateur : expression technique désignant le programme utilisateur, en Go cela refers au code utilisateur
Collecteur : désigne le programme responsable du ramasse-miettes, en Go c'est le runtime
Finalizer : désigne le code responsable de la récupération et libération de la mémoire des objets après le marquage
Contrôleur : désigne la variable globale runtime.gcController, de type gcControllerState, qui implémente l'algorithme de pacing
Limiteur : désigne runtime.gcCPULimiter, responsable d'éviter que l'utilisation CPU soit trop élevée pendant le ramasse-miettes

Déclenchement

func gcStart(trigger gcTrigger)

Le ramasse-miettes est lancé par la fonction runtime.gcStart, qui prend un paramètre runtime.gcTrigger contenant la raison du déclenchement GC, l'heure actuelle, et le numéro du cycle GC.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: current time
    n    uint32 // gcTriggerCycle: cycle number to start
}

Les valeurs possibles de gcTriggerKind sont :

const (
  // gcTriggerHeap indicates that a cycle should be started when
  // the heap size reaches the trigger heap size computed by the
  // controller.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indicates that a cycle should be started when
  // it's been more than forcegcperiod nanoseconds since the
  // previous GC cycle.
  gcTriggerTime

  // gcTriggerCycle indicates that a cycle should be started if
  // we have not yet started cycle number gcTrigger.n (relative
  // to work.cycles).
  gcTriggerCycle
)

Il y a trois moments de déclenchement du ramasse-miettes :

Lors de la création d'un nouvel objet : lors de l'appel à runtime.mallocgc pour allouer de la mémoire, si la mémoire tas atteint le seuil (généralement le double du dernier GC, ajusté par l'algorithme de pacing), le GC est déclenché
go
```
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
  if shouldhelpgc {
    if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
      gcStart(t)
    }
  }
    ...
}
```

Déclenchement forcé temporisé : Go lance une goroutine séparée pour exécuter runtime.forcegchelper. Si aucun GC n'a eu lieu pendant longtemps, il force le déclenchement. Cette durée est définie par runtime.forcegcperiod, soit 2 minutes

func forcegchelper() {
  for {
        ...
    gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
        ...
  }
}

func sysmon() {
    ...
  for {
        ...
    // check if we need to force a GC
    if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && forcegc.idle.Load() {
      lock(&forcegc.lock)
      forcegc.idle.Store(false)
      var list gList
      list.push(forcegc.g)
      injectglist(&list)
      unlock(&forcegc.lock)
    }
  }
}

Déclenchement manuel : via la fonction runtime.GC, l'utilisateur peut déclencher manuellement le ramasse-miettes

func GC() {
    ...
  n := work.cycles.Load()
  gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
    ...
}

TIP

Pour en savoir plus, consultez Go Gc Pacer Re-Design qui explique la conception et les améliorations de l'algorithme de pacing.

Marquage

L'algorithme GC de Go suit toujours l'étape marquage puis balayage, mais son implémentation est plus complexe qu'avant.

Marquage-Balayage

Commençons par l'algorithme de marquage-balayage le plus simple. En mémoire, les relations de référence entre objets forment un graphe. Le ramasse-miettes travaille sur ce graphe en deux phases :

Phase de marquage : depuis les nœuds racines (variables sur la pile, variables globales, objets actifs), parcourt chaque nœud accessible et le marque comme actif
Phase de balayage : parcourt tous les objets du tas, récupère les objets non marqués

Pendant la récupération, la structure du graphe d'objets ne peut pas changer, donc tout le programme doit être arrêté (STW). Après la récupération, le programme reprend. Les inconvénients de cet algorithme sont :

Produit des fragments mémoire (moins problématique avec la gestion mémoire style TCMalloc de Go)
Scanne tous les objets du tas pendant le marquage
Provoque un STW qui暂停整个程序 pendant un temps non négligeable

Marquage Tricolore

Pour améliorer l'efficacité, Go adopte l'algorithme classique de marquage tricolore. Les trois couleurs sont :

Noir : objet déjà visité pendant le marquage, et tous ses objets directement référencés ont été visités, représente un objet actif
Gris : objet déjà visité pendant le marquage, mais ses objets directement référencés n'ont pas tous été visités, devient noir quand tous sont visités
Blanc : jamais visité pendant le marquage, devient gris après visite, représente potentiellement un objet poubelle

Au début du marquage tricolore, il n'y a que des objets gris et blancs. Tous les objets racines sont gris, les autres sont blancs.

À chaque tour de marquage, on commence par les objets gris, les marque en noir (objets actifs), puis marque tous les objets directement référencés par l'objet noir en gris. Le reste est blanc.

On répète jusqu'à ce qu'il ne reste que des objets noirs et blancs. Quand l'ensemble des objets gris est vide, le marquage est terminé.

Après le marquage, dans la phase de balayage, il suffit de libérer la mémoire des objets blancs.

Invariance

Le marquage tricolore lui-même ne permet pas le marquage concurrent. Si la structure du graphe d'objets change pendant le marquage, deux situations peuvent se produire :

Sur-marquage : un objet marqué noir voit toutes ses références supprimées par le programme utilisateur, il devrait être blanc et être récupéré
Sous-marquage : un objet marqué blanc voit un autre objet le référencer, il devrait être noir et ne pas être récupéré

Le premier cas est acceptable car l'objet non récupéré sera traité dans le prochain cycle. Mais le second cas est inacceptable : libérer par erreur la mémoire d'un objet en cours d'utilisation provoquerait de graves erreurs.

L'invariance tricolore vient du papier de Pekka P. Pirinen de 1998 « Barrier techniques for incremental tracing ». Elle définit deux invariantes pour le marquage concurrent :

Invariance tricolore forte : un objet noir ne peut pas directement référencer un objet blanc
Invariance tricolore faible : quand un objet noir référence directement un objet blanc, il doit y avoir un objet gris qui peut accéder directement ou indirectement à cet objet blanc

Pour l'invariance forte, l'objet noir 3 est déjà visité et ses enfants sont marqués gris. Si le programme utilisateur ajoute une nouvelle référence à l'objet blanc 7 depuis l'objet noir 3, normalement l'objet 7 devrait être marqué gris. Mais comme l'objet 3 est déjà visité, l'objet 7 ne sera pas visité et restera blanc, pour être finalement libéré par erreur.

Pour l'invariance faible, c'est similaire. Comme l'objet gris peut accéder directement ou indirectement à l'objet blanc, il sera finalement marqué gris lors du marquage, évitant la libération par erreur.

Grâce à l'invariance, on s'assure qu'aucun objet n'est libéré par erreur pendant le marquage, garantissant la correction du marquage concurrent. La clé pour garantir l'invariance tricolore en concurrent est la technologie de barrière.

Travail de marquage

Pendant la phase de balayage GC, une variable globale runtime.gcphase indique l'état du GC :

_GCoff : marquage non commencé
_GCmark : marquage commencé
_GCmarktermination : marquage va se terminer

Quand le marquage commence, l'état est _GCmark. Le travail de marquage est exécuté par la fonction runtime.gcDrain, avec un paramètre runtime.gcWork qui est un pool de tampons contenant les pointeurs d'objets à suivre.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Elle tente d'obtenir des pointeurs à suivre depuis le pool, et appelle runtime.scanobject pour continuer le balayage, qui scanne les objets du tampon et les colore en noir.

if work.full == 0 {
    gcw.balance()
}

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Flush the write barrier
        // buffer; this may create
        // more work.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // Unable to get work.
    break
}
scanobject(b, gcw)

Le balayage s'arrête quand P est préempté ou qu'un STW se produit.

for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
  ...
  scanobject(b, gcw)
  ...
}

runtime.gcwork est une file producteur/consommateur qui stocke les objets gris à scanner. Chaque processeur P a une telle file locale, correspondant au champ runtime.p.gcw.

func scanobject(b uintptr, gcw *gcWork) {
  ...
  for {
    var addr uintptr
    if hbits, addr = hbits.nextFast(); addr == 0 {
            if hbits, addr = hbits.next(); addr == 0 {
                break
            }
        }
    scanSize = addr - b + goarch.PtrSize
    obj := *(*uintptr)(unsafe.Pointer(addr))
    if obj != 0 && obj-b >= n {
      if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
        greyobject(obj, b, addr-b, span, gcw, objIndex)
      }
    }
  }
  gcw.bytesMarked += uint64(n)
  gcw.heapScanWork += int64(scanSize)
}

La fonction runtime.scanobject marque les objets blancs accessibles en gris et les met dans la file locale via gcw.put. gcDrain tente d'obtenir des objets gris via gcw.tryget pour continuer le balayage. Le processus de marquage est incrémental, pas besoin de tout faire en une fois.

gc ​

Concepts ​

Déclenchement ​

Marquage ​

Marquage-Balayage ​

Marquage Tricolore ​

Invariance ​

Travail de marquage ​

gc