Comptage de références

Lorsqu'un objet est créé, on alloue également un espace mémoire associé, appelé compteur de références. Ce compteur stocke le nombre de références qui pointent vers cet objet. Lorsqu'on crée ou que l'on supprime une référence vers un objet, on incrémente ou décrémente son compteur de 1. Lorsque le compteur atteint 0, on sait que l'objet n'est plus référencé par le programme, il peut alors être supprimé.

Le principal avantage du comptage de références par rapport au ramasse-miettes traversant est que les objets sont récupérés dès qu'ils ne peuvent plus être référencés, sans interrompre le programme pendant des cycles de collecte. Cela permet également d'avoir une durée de vie bien définie pour chaque objet. Dans les applications en temps réel ou sur des systèmes à mémoire limitée, cela peut permettre une meilleure réactivité. Le comptage de références est également l'une des formes de gestion mémoire les plus simples à mettre en œuvre. Il permet également une gestion efficace des ressources autres que des blocs de mémoire, telles que les objets du système d'exploitation.

Si les objets actifs remplissent la majeure partie de la mémoire disponible, un algorithme ramasse-miettes traversant s'exécute trop souvent et est peu efficace, alors que les performances du comptage de références sont indépendantes de la quantité d'espace libre^[1].

Le compteur de références peut également servir pour d'autres optimisations. Par exemple, les systèmes qui reposent sur des objets immuables, comme de nombreux langages de programmation fonctionnelle, peuvent subir une perte d'efficacité en raison de copies fréquentes. Cependant, si le compilateur (ou le système d'exécution) sait qu'un objet particulier n'a qu'une seule référence, et que la référence est perdue en même temps qu'un nouvel objet similaire est créé (par exemple avec une instruction de concaténation de chaînes de caractères comme str ← str + "a" ), il peut remplacer l'opération par une mutation sur l'objet d'origine.

Le comptage de références sous forme naïve présente trois inconvénients principaux par rapport au ramasse-miettes traversant:

• Les mises à jour fréquentes qu'il implique sont inefficaces. Si l'exécution d'un algorithme ramasse-miettes peut prendre beaucoup de temps, celui-ci n'a pas besoin d'être exécuté très fréquemment, alors que le comptage de références implique de changer souvent les nombres de référence. De plus, il faut réserver pour chaque objet un espace mémoire supplémentaire pour stocker le nombre de références.
• L'algorithme naïf décrit ci-dessus ne peut pas gérer un cycle de références, par exemple deux objets qui pointent mutuellement l'un vers l'autre. Un mécanisme reposant uniquement sur le comptage de références ne supprimera jamais un tel cycle, car les nombres de références de ses objets ne seront jamais nuls (cf. illustration). Une méthode pouvant être utilisée pour contourner ce problème est d'utiliser des références faibles qui ne sont pas prises en compte dans le comptage de références. Une autre consiste a appeler régulièrement un algorithme ramasse-miettes marquant et nettoyant.

  

• En programmation concurrente, toutes les mises à jour des compteurs de références doivent être des opérations atomiques, ce qui engendre un coût supplémentaire, car le compteur de références peut être mis à jour simultanément par plusieurs threads.

De plus, le comptage de référence seul ne déplace pas les objets en mémoire, ce qui diminue la localité et donc les performances du cache, contrairement à un ramasse-miettes copiant. La plupart des implémentations (par exemple dans PHP et Objective-C) ont de ce fait des mauvaises performances de cache^[2].

Lorsqu'on traite des schémas de gestion de mémoire, il est souvent utile de penser au graphe de références, qui est un graphe orienté où les sommets sont les objets et où une arête de A à B représente une référence vers B contenue dans A. On a également un ou plusieurs sommets spéciaux qui représentent la pile d'exécution (aucune arête ne peut pointer vers ces sommets).

Dans ce graphe, le nombre de références d'un objet correspond au degré entrant de son sommet. Supprimer un sommet revient à libérer la mémoire d'un objet. Elle peut affecter le degré entrant d'autres sommets, entraînant la suppression des objets correspondants si leur degré entrant devient également nul, et ainsi de suite.

Les composantes connexes contenant des sommets spéciaux représente les objets utilisés par le programme, tandis que les autres peuvent être supprimées. Si on utilise un algorithme de comptage de références, chacune de ces composantes inutilisées contient au moins un cycle, sinon leur nombres de références serait tombé à zéro.

La modification du compteur de références à chaque création ou destruction de référence peut considérablement réduire les performances. Non seulement ces opérations prennent du temps, mais elles nuisent également aux performances du cache et peuvent entraîner des bulles de pipeline. Même les opérations en lecture seule, comme le calcul de la longueur d'une liste chaînée, nécessitent un grand nombre de lectures et d'écritures des nombres de références avec un algorithme de comptage naïf.

Une amélioration simple consiste à combiner plusieurs mises à jour de références proches en une seule lors de la compilation. Cette méthode est particulièrement efficace pour les références créées et rapidement détruites.

Par exemple, la méthode de Deutsch-Bobrow exploite le fait que la plupart de ces mises à jour sont générées par des références stockées dans des variables locales. Elle consiste à ignorer ces références et ne compter que celles contenues dans les structures de données. Cependant, avant de pouvoir supprimer un objet dont le compteur de références est nul, le système doit vérifier qu'il ne reste aucune référence dans la pile d'appel ou les registres^[3].

Une autre technique imaginée par Henry G. Baker implique l'incrémentation différée ^[4], où les références stockées dans des variables locales n'incrémentent pas immédiatement le compteur, et l'incrémentation est reportée jusqu'à ce que cela soit nécessaire. Si une telle référence est détruite rapidement, il n'est pas nécessaire de mettre à jour le compteur. Cela élimine un grand nombre de mises à jour associées aux références éphémères (comme dans l'exemple de comptage de longueur de liste ci-dessus). Cependant, si une telle référence est copiée dans une structure de données, l'incrémentation doit être effectuée à ce moment-là. Il est également crucial d'effectuer l'incrémentation avant que le compteur de l'objet ne tombe à zéro, afin d'éviter une suppression prématurée.

Une diminution spectaculaire du nombre de mises à jour des compteurs a été obtenue par Levanoni et Petrank^[5],[6]. Ils introduisent la méthode de coalescence des mises à jour qui supprime de nombreuses mises à jour redondantes des compteurs de références. Considérons un pointeur qui est mis à jour plusieurs fois dans un bloc de code donné. Il pointe d'abord vers un objet O1, puis vers un objet O2, et ainsi de suite jusqu'à la fin du bloc ou il pointe vers un objet On. Un algorithme de comptage de références exécuterait typiquement rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++, mais la plupart de ces mises à jour sont redondantes. Il suffit d'exécuter rc(O1)-- et rc(On)++ pour que les compteurs de références soient corrects à la fin.

Levanoni et Petrank sont parvenus en 2001 a éliminer plus de 99% des mises à jours de compteurs de référence sur des tests de performances en Java, en utilisant la coalescence de mises à jour et avec un traitement approprié des créations d'objets^[7].

Il est intéressant de noter que la coalescence des mises à jour élimine également la nécessité des opérations atomiques lors des mises à jour simultanées. L'algorithme de Levanoni et Petrank fonctionne également pour des applications parallélisées^[7].

La méthode de comptage de références ultérieure de Blackburn et McKinley (2003) ^[8] combine le comptage de références différé avec un ramasse-miettes copiant pour les objets récemment créés, observant que la majorité des mutations de pointeurs se produisent chez ceux-ci. Cet algorithme atteint un débit comparable à celui des ramasse-miettes à générations les plus rapides, avec des temps de pause limités pour le comptage de références.