Comptage de références

En informatique, le comptage de références est une technique de programmation qui consiste à stocker le nombre de références ou de pointeurs vers une ressource dans un compteur associé à celle-ci, telle qu'un objet, un bloc de mémoire, un espace disque, etc.

Lorsqu'une référence est créée ou supprimée, le compteur est incrémenté ou décrémenté, ce qui permet de savoir quand la ressource n'est plus utilisée.

Dans les algorithmes ramasse-miettes, le comptage de références peut être utilisé pour détecter et libérer les blocs de mémoires qui ne sont plus utilisés.

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.

Une façon de gérer le problème des cycles de référence est d’empêcher leur création. Un système peut les interdire explicitement, comme par exemple les systèmes de fichiers avec liens physiques. Une utilisation judicieuse de références « faibles » (non comptées) permet également d'éviter les cycles de références. Par exemple, le framework Cocoa recommande d'utiliser des références « fortes » pour les relations parent-enfant et des références « faibles » pour les relations enfant-parent^[9].

Un système peut également être conçu pour tolérer ou corriger les cycles. Les développeurs peuvent écrire du code pour supprimer manuellement les références d'une structure de données lorsqu'elle n'est plus utilisée. Cette technique peut être automatisée en créant un objet « propriétaire » qui effectue la suppression lorsqu'il est détruit. Par exemple, le destructeur d'un objet de type "graphe" pourrait supprimer l'entièreté de ses sommets, résolvant ainsi les cycles de référence dans le graphe. Les cycles peuvent parfois être ignorés dans les systèmes à courte durée de vie, au détriment de l'efficacité.

Une solution simple pour détecter les cycles consiste à utiliser périodiquement un ramasse-miettes traversant. Comme les cycles occupent généralement une quantité relativement faible d'espace mémoire, il peut être exécuté beaucoup moins souvent qu'un ramasse-miettes traversant classique.

Bacon décrit un algorithme de détection de cycles similaire aux ramasse-miettes traversants, avec les mêmes limites de temps théoriques. Il part du constat qu'un cycle ne peut devenir isolé que lorsqu'un compteur de références est décrémenté vers une valeur non nulle. Lorsque cela arrive, l'objet concerné est placé dans une liste de racines. Le programme recherche ensuite périodiquement des cycles parmi les objets accessibles depuis les racines. Il sait qu'il a trouvé un cycle isolé lorsque la décrémentation de tous les compteurs de références d'un cycle les ramène à zéro^[10]. Une version améliorée de cet algorithme, développée par Paz et al. ^[11] peut s'exécuter en parallèle d'autres opérations et améliore son efficacité grâce à la méthode de coalescence des mises à jour de Levanoni et Petrank^[5],[6].

Le comptage de référence pondéré a été conçu indépendamment par Bevan ^[12] et Watson & Watson ^[13] en 1987.

Un poids est attribué à chaque référence, et chaque objet ne stocke pas son nombre de références, mais le poids total de ses références. La référence initiale à un objet nouvellement créé a un poids important, par exemple 2¹⁶. À chaque copie, la moitié du poids est attribuée à la nouvelle référence, et l'autre moitié à l'ancienne. Comme le poids total ne change pas, le compteur de l'objet n'a pas besoin d'être augmenté.

La destruction d'une référence soustrait son poids au compteur de l'objet. Lorsque le compteur atteint zéro, l'objet est supprimé. Si l'on tente de copier une référence dont le poids est égal à 1, on doit augmenter le poids total de l'objet pour donner un poids à la nouvelle référence.

Cette variante est particulièrement utile lorsque l'accès au compteur de références est coûteux, par exemple s'il est utilisé par un autre processus ou stocké sur un disque ou un serveur. Elle diminue également le nombre de threads qui verrouillent un compteur de références. Cette méthode est donc particulièrement utile dans les applications multi-processus et les bases de données.

Cependant, elle ne résout pas entièrement le problème car les compteurs doivent toujours être décrémentés lors de la suppression de références. Pour éviter ce problème, certaines adaptations essayent de transférer le poids des références supprimées à celles encore actives.

• Portail de l'informatique théorique