Reference counting : comment fonctionne ce type de garbage collector
Le reference counting est une façon simple de gérer la mémoire : chaque objet sait combien de pointeurs le désignent, et il est libéré dès que ce compteur tombe à zéro. C’est l’une des deux grandes familles de garbage collectors, avec le tracing (mark-and-sweep).
Le principe
Chaque objet porte un compteur. Copier un pointeur l’incrémente (retain), détruire ou écraser un pointeur le décrémente (release). À zéro, l’objet est libéré, et ses propres champs perdent à leur tour une référence.
typedef struct node {
int rc; /* reference count */
struct node *child; /* a field pointing to another node */
} node;
void retain(node *n) { if (n) n->rc++; }
void release(node *n) {
if (n && --n->rc == 0) {
release(n->child); /* fields lose a reference too */
free(n);
}
}Ce qu’on y gagne
La libération est immédiate et prévisible : pas de pause stop-the-world pour parcourir la mémoire, et un objet disparaît exactement quand plus personne ne l’utilise. C’est aussi simple à implémenter, ce qui en fait un bon choix pour un compilateur pédagogique.
Ce que ça coûte
- Chaque copie ou destruction de pointeur met à jour un compteur, ce qui ajoute de l’overhead.
- Avec plusieurs threads, les compteurs doivent être atomiques, ce qui coûte encore plus cher.
- Les cycles ne sont jamais libérés : si A référence B et B référence A, aucun compteur n’atteint zéro.
Pour les cycles, on utilise des weak references (qui ne comptent pas) ou un cycle collector complémentaire. CPython, par exemple, combine reference counting et cycle collector.
Dans un compilateur
Le générateur de code doit insérer les retain et release aux bons endroits : affectations, passage de paramètres, retour de fonction, sortie de portée. L’ordre compte lors d’une affectation, car dest et src peuvent désigner le même objet :
void assign(node **dest, node *src) {
retain(src); /* new value first */
release(*dest); /* then the old one */
*dest = src;
}Les erreurs classiques : un retain oublié libère l’objet trop tôt et laisse un pointeur invalide, un release en double corrompt la mémoire ou provoque un segfault, un release oublié crée une fuite. Un outil comme Valgrind ou AddressSanitizer aide à les repérer.
Voir aussi : le compilateur vers C, qui embarque ce garbage collector