Ramasse-miettes (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Ramasse-miettes.
Illustration d'un ramasse-miette compactant.

Un ramasse-miettes, ou récupérateur de mémoire, ou glaneur de cellules (en anglais Garbage Collector, abrégé en GC), est un sous-système informatique de gestion automatique de la mémoire. Il est responsable du recyclage de la mémoire préalablement allouée puis inutilisée.

Historique[modifier | modifier le code]

Lorsqu'un système dispose d'un ramasse-miettes, ce dernier fait généralement partie de l'environnement d'exécution associé à un langage de programmation particulier. Le ramassage des miettes a été inventé par John McCarthy comme faisant partie du premier système Lisp.

Le terme français de ramasse-miettes apparaît vers 1970 dans les communications de Claude Pair aux écoles d'été de l'AFCET[1] ainsi qu'à la même époque dans ses cours d'informatique à l'université de Nancy. Il est rapidement adopté les années suivantes par Jean-Claude Derniame (Nancy), Louis Bazerque (Toulouse), Jean Cea (Nice), Jean-Pierre Verjus (Rennes), Claude Hans (Grenoble), Olivier Lecarme (Montréal) et Jacques Arsac (Paris).

Définition et fonctionnement[modifier | modifier le code]

Le principe de base de la récupération automatique de la mémoire est assez simple :

  • déterminer quels objets ne peuvent plus être utilisés par le programme ;
  • récupérer l'espace utilisé par ces objets.

Il n'est pas toujours possible de déterminer à l'avance à quel moment un objet ne sera plus utilisé. En effet, les instructions qui seront exécutées dépendent des données en entrée, et aussi de la structure du programme qui peut être complexe. Cependant, il est possible de découvrir à l'exécution que certains objets ne peuvent plus être utilisés. En effet, un objet sur lequel le programme ne maintient plus de référence, donc devenu inaccessible, ne sera plus utilisé. Cependant, le contraire n'est pas vrai, à savoir que le fait qu'il existe une référence vers un objet ne signifie pas obligatoirement qu'il sera utilisé.

Lorsque les langages sont typés, les récupérateurs peuvent correctement identifier toutes les références à un objet : ils sont appelés des récupérateurs exacts.

Dans le cas des langages faiblement typés, les récupérateurs sont conservatifs : le ramasse-miettes doit présumer que n'importe quelle suite de bits en mémoire interprétée comme un pointeur est une référence accessible. En effet, les langages faiblement typés ne permettent pas complètement à un observateur extérieur à l'application en cours d'exécution — ce qui est la situation du ramasse-miette — de déterminer le type des objets, et donc de connaître leur taille et l'emplacement des pointeurs qu'ils peuvent contenir. Un ramasse-miette conservatif fait toutes les hypothèses plausibles compatible avec ce qu'il sait des typages possibles et de l'organisation de la mémoire. De ce fait, il peut y avoir de faux positifs et le ramasse-miettes est incomplet.

Principe d'accessibilité d'un objet[modifier | modifier le code]

Les ramasse-miettes utilisent un critère d'accessibilité pour déterminer si un objet peut être potentiellement utilisé. Les principes sont :

  • un ensemble distinct d'objets accessibles : ce sont les racines. Dans un système typique ces objets sont les registres machine, la pile, le pointeur d'instruction, les variables globales. En d'autres termes tout ce qu'un programme peut atteindre directement.
  • tout objet référencé depuis un objet accessible est lui-même accessible.

Dit autrement : un objet accessible peut être obtenu en suivant une chaîne de pointeurs ou de références. Bien évidemment, un tel algorithme est une approximation conservatrice de l'objectif idéal de libération de toutes les valeurs (ou plutôt zones mémoire) ne servant plus : certaines valeurs peuvent fort bien être accessibles depuis les racines mais ne plus jamais être utilisées. Cet objectif idéal est jugé trop complexe : déterminer quelles valeurs serviront dans le futur est équivalent au problème de l'arrêt (indécidabilité de l'arrêt, et par extension, du nombre de passage à un endroit donné - et des ressources mémoires associées, à cause de boucles, sauts, etc.), non soluble dans les cas d'une mémoire infinie[2]. D'autre part, le comportement du programme dépend des données en entrée, par définition non connues à l'avance.

Cette approximation conservatrice est la raison de la possibilité de fuites de mémoire, c'est-à-dire de l'accumulation de blocs de mémoire qui ne seront jamais réutilisés, mais jamais libérés non plus au long de l'exécution du programme : un programme peut conserver un pointeur sur une structure de données qui ne sera jamais réutilisée. Il est pour cette raison recommandé de libérer (autrement dit autoriser le recyclage) les structures inutilisées et leurs pointeurs, afin d'éviter de conserver des références inutiles. Pour des raisons de modularité, les couches conceptuelles où l'inutilité est constatée ne sont cependant pas toujours celles où la libération peut s'effectuer sans danger.

Algorithmes de base[modifier | modifier le code]

On distingue trois familles d'algorithmes :

  • Les algorithmes à comptage de références. Ces algorithmes maintiennent pour chaque objet un compteur indiquant le nombre de référence sur cet objet. Si le compteur d'un objet devient nul, il peut être recyclé.
  • Les algorithmes traversants. Ces algorithmes traversent le graphe des objets accessibles en partant des racines pour distinguer ces objets accessibles (à conserver) des autres objets considérés donc comme inaccessibles (à recycler).
  • Les algorithmes à générations.

La famille des algorithmes traversants est souvent décomposée en deux sous-familles :

  • Les algorithmes marquants et nettoyants (mark and sweep collector en anglais);
  • Les algorithmes copiants (copy collector en anglais), dont l'archétype est l'algorithme de Cheney [réf. souhaitée].

En fait, certains algorithmes peuvent combiner diverses méthodes traversantes car elles suivent toutes un modèle abstrait commun.

Comptage de références[modifier | modifier le code]

Une solution qui vient vite à l'esprit pour la libération automatique de zones de mémoire est d'associer à chacune un compteur donnant le nombre de références qui pointent sur elle. Ces compteurs doivent être mis à jour à chaque fois qu'une référence est créée, altérée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée. Cette méthode est très efficace dans la plupart des cas.

Cependant, cette technique a un inconvénient lors de l'usage de structures cycliques : si une structure A pointe sur une structure B qui pointe sur A (ou, plus généralement, s'il existe un cycle dans le graphe des références), mais qu'aucun pointeur extérieur ne pointe ni sur A ni sur B, les structures A et B ne sont jamais libérées : leurs compteurs de références sont strictement supérieurs à zéro (et comme il est impossible que le programme accède à A ou B, ces compteurs ne peuvent jamais repasser à zéro).

En raison de ces limites, certains considèrent que le comptage de références n'est pas une technique de récupération de mémoire à proprement parler ; ils restreignent le terme de récupération de mémoire à des techniques basées sur l'accessibilité.

En plus de l'impossibilité de gérer les références circulaires, ce système souffre d'autres problèmes sérieux, comme son coût élevé en temps de calcul et aussi en espace mémoire. Pour chaque zone mémoire allouée, il faut en effet maintenir à jour le nombre de références qui y accède ce qui nécessite quelques octets supplémentaires spécifiquement destinés à cet usage. D'un autre côté, il récupère les « miettes » plutôt vite, ce qui présente des avantages s'il y a des destructeurs à exécuter pour libérer les ressources rares (sockets…) autres que le tas (mémoire).

Des systèmes hybrides utilisant le comptage de références pour obtenir la libération quasi immédiate des ressources, et appelant à l'occasion un récupérateur de type Mark and Sweep pour libérer les objets contenant des cycles de références, ont été proposés et parfois implémentés. Cela donne le meilleur des deux mondes, mais toujours au prix d'un coût élevé en termes de performances[réf. nécessaire].

Les ramasse-miettes traversants[modifier | modifier le code]

Modélisation des algorithmes traversants[modifier | modifier le code]

Les algorithmes traversants peuvent être modélisés à l'aide de l' abstraction des trois couleurs, publiée par Dijkstra, Lamport et al. en 1978.

L'abstraction des trois couleurs permet de décrire l'avancement d'un cycle de ramassage. Au cours d'un cycle de ramassage, les objets peuvent prendre successivement trois couleurs :

  • Les objets blancs sont les objets que le ramasse-miette n'a pas encore vus. Au début d'un cycle, tous les objets sont blancs.
  • Les objets gris sont les objets que le ramasse-miette a vus, mais pas encore traversés. Pour initier un cycle, le ramasse-miette colorie les objets-racines en gris.
  • Les objets noirs sont les objets que le ramasse-miette a traversés.

À chaque itération de la boucle principale d'un algorithme traversant, le ramasse-miette choisit un objet gris, le colorie en noir et colorie tous ses objets fils blancs en gris. L'algorithme se termine quand il n'y a plus d'objets gris. Les objets sont alors soit blancs soit noirs. Les blancs ne sont pas accessibles à partir des objets racines et peuvent donc être recyclés : l'espace qu'ils occupent est récupéré. A contrario, les objets noirs sont accessibles et sont donc conservés.

Implémentation des algorithmes traversants[modifier | modifier le code]

Les différences entre les algorithmes traversants sont souvent fondées sur la façon dont la coloration des objets est réalisée en pratique dans l'implémentation des ramasse-miettes. Les méthodes les plus courantes sont l'utilisation de bits de coloration placés dans les objets ou dans des cartes de la mémoire, l'utilisation de listes d'objets correspondant à une couleur donné, ou la détermination de la couleur en fonction de la zone de mémoire où l'objet se trouve, ce qui peut nécessiter de le recopier.

Par exemple on peut réaliser un algorithme marquant et nettoyant classique en utilisant pour chaque objet un bit qui est à 0 pour les objets blancs, et à 1 pour les objets gris ou noirs. Les objets gris sont distingués des noirs en listant leurs adresses, ce qui facilite le choix d'un objet gris au début de chaque itération et la détermination de la fin du cycle de récupération par absence d'objets gris. Mais, au lieu d'une liste, on pourrait aussi utiliser un deuxième bit pour chaque objet.

Au lieu de ce bit, (ou ces bits), on peut recopier les objets reconnus comme accessibles (donc gris, puis noirs) dans une zone de mémoire nouvelle, l' espace de copie, réservée à cet effet. La distinction entre blanc d'une part et gris ou noir d'autre part se fait alors en regardant dans quelle zone l'objet est rangé. On réalise ainsi un algorithme copiant. La distinction entre gris et noir peut être faite par une liste d'adresses, par un bit de coloration, ou en bi-partitionnant l'espace de copie. Dans ce dernier cas, le plus simple consiste à utiliser un unique pointeur qui indique l'adresse de la frontière entre les objets noirs et les gris, frontière que l'on déplace à mesure que les objets gris sont traités.

Avantages et inconvénients[modifier | modifier le code]

Un avantage des ramasse-miettes copieurs est que la libération de l'espace des objets blancs (morts) se fait d'un coup en récupérant la zone ancienne : le coût d'un cycle du ramasse-miettes est donc proportionnel aux nombre d'objets vivants. Ceci est particulièrement utile quand il y a beaucoup d'objets alloués, dont la plupart sont temporaires et meurent rapidement. En outre, tous les objets vivants sont rassemblés, et l'espace pour les nouveaux objets peut être alloué facilement à partir d'un unique bloc, quelle que soit la taille de l'objet désiré. Par contre, le déplacement des objets lors de la copie impose la mise à jour des pointeurs vers ces objets, ce qui a un coût et peut être complexe dans le cas des variantes incrémentielles ou concurrentes car l'application doit pouvoir trouver les objets et suivre les pointeurs en dépit du fait que le ramasse-miettes les déplace. Par ailleurs, l'algorithme impose à l'application de n'utiliser en principe qu'une moitié de la mémoire, l'autre moitié étant réservée à la copie du prochain cycle de ramassage et à l'allocation de mémoire entre ce cycle et le suivant : la moitié de mémoire utilisée par l'application change à chaque cycle de ramassage.

Les ramasse-miettes marquant et nettoyant ne posent pas de problème de localisation des objets dû à leur déplacement. En outre ils permettent d'utiliser la mémoire entière, au lieu de se limiter à une moitié. Cependant la récupération impose une phase de balayage de toute la mémoire pour récupérer l'espace des objets inaccessibles (et donc toujours blancs). Le coût de cette phase est proportionnel à la taille de la zone mémoire utilisée, passant sur tous les objets accessibles ou non. Cela peut être très coûteux par rapport à la phase de marquage si la plupart des objets sont devenus inaccessibles. Par ailleurs, la mémoire disponible n'est pas récupérée en un seul morceau, mais sous forme d'une collection de fragments de tailles variables. La gestion de ces fragments et leur usage optimal en fonction de leur taille pour allouer de l'espace à de nouveaux objets peut être complexe, surtout si l'application utilise des objets de taille variable. C'est pourquoi certaines implémentations prévoient également une phase de compactage de la mémoire à la fin de chaque cycle de ramassage ou combinent ce compactage avec la phase de balayage. Cependant le compactage requiert un déplacement des objets, avec les mêmes problèmes que pour les algorithmes copieurs.

Variantes et améliorations fonctionnelles des ramasse-miettes traversants[modifier | modifier le code]

Les algorithmes de bases peuvent être implémentés selon diverses variantes.

  • Les ramasse-miettes bloquants (en anglais stop-the-world) arrêtent l'application (ou le système) pour la durée d'un cycle de collection entier.
  • Les ramasse-miettes incrémentiels permettent d'exécuter des pas d'un cycle en alternance avec l'exécution de l'application
  • Les algorithmes dits concurrents s'exécutent parallèlement à l'application. Les algorithmes de ce type ne peuvent s'exécuter que sur des machines avec plusieurs processeurs. Les problèmes diffèrent selon que ces processeurs partagent ou non leur espace mémoire.
  • Les ramasse-miettes peuvent également opérer sur un mode réparti, sur des réseaux locaux ou non.

Choix du récupérateur : conservateur ou exact[modifier | modifier le code]

La sémantique d'un langage et la réalisation du compilateur vont déterminer la réalisation du récupérateur. Dans le cadre d'un langage où le programme peut librement allouer et désallouer de la mémoire, l'utilisation d'un récupérateur conservateur est inévitable car le compilateur ne peut pas déterminer exactement si une valeur est un pointeur ou non. Dans le cadre d'un langage « memory safe », il a le choix entre l'utilisation d'un récupérateur exact ou conservateur. Pour des raisons de facilité de mise en place, le choix se fait généralement vers un récupérateur exact (il est également historiquement plus performant). Cependant, Une étude[3] a comparé les performances des récupérateurs exacts et conservateurs sur différentes réalisations, ce chapitre s'appuie sur cette étude.

Réalisations utilisées[modifier | modifier le code]

Cette partie détaille les différentes réalisations de récupérateur utilisées dans l'étude comparative.


Exact mark-sweep (MS)[4][modifier | modifier le code]

L’algorithme Mark-sweep fait partie de la famille des “stop-the-world” collection, ce qui signifie que quand le programme demande de la mémoire et qu’il n’y en a plus de disponible, le programme est arrêté et une collection est exécutée pour libérer de l’espace puis le programme reprend la main à la fin de la collection. Dans l’algorithme Mark-sweep, tous les objets ont un flag, durant le parcours après avoir été visité son flag est positionné pour éviter qu’un objet soit visité deux fois.

Algorithme MS

Cet algorithme à une complexité en O(N) c’est-à-dire en temps linéaire par rapport à la taille du tas. Ceci ne nous dit pas directement le coût de son exécution car l’algorithme sera appelé à chaque fois qu'une demande d’allocation échoue et donc le coût dépend de plusieurs paramètres comme la taille du tas et la quantité de mémoire qui est devenue inaccessible depuis sa dernière collection.

Dans la pratique, le coût, au même titre que le temps durant lequel l’algorithme mets en pause le programme, est élevé comparé à d’autres algorithmes. Cependant, l’algorithme à l’avantage de libérer tout espace mémoire inutilisé mais cette mémoire peut facilement devenir fragmentée ce qui diminue les possibilités d’avoir de larges régions. Il y a également un coût supplémentaire en mémoire à cause du flag qui permet de savoir si un objet a déjà été visité mais il n’est nécessaire que quand une collection est en cours et donc quand le programme reprend la main l’espace est ré-alloué pour d’autre structure de données.

Conservateur Boehm-Demers-Weiser (BDW)[modifier | modifier le code]

Voir Boehm garbage collector (en).

Exact Semi-Space (SS)[5][modifier | modifier le code]

L’algorithme Semi-Space fonctionne par copie ce qui veut dire que les objets accessibles sont déplacés d’une adresse vers une autre adresse pendant la collection. La mémoire est divisée en deux régions de taille égale appelées “from-space” et “to-space”. L’allocation consiste à garder un pointeur dans “to-space” qui est incrémenté par le nouveau besoin en mémoire. Quand il n’y a plus suffisamment d’espace dans “to-space” pour incrémenté le pointeur du nouveau besoin en mémoire, une collection s’exécute. Une collection consistes à inverser le rôle des régions et à copier les objets de la zone “from-space” vers la zone “to-space” laissant un bloc d’espace libre correspondant à la mémoire utilisée par tous les objets inaccessibles à la fin de “to-space”.

Puisque les objets sont déplacés pendant une collection, les adresses de toutes les références doivent être mises à jour, ceci est fait en stockant une adresse de réexpédition pour un objet quand il est copié de “from-space”.

Algorithme semi-space

L’avantage principal de l’algorithme semi-space par rapport à un algorithme “mark-sweep" est que le coût de l’allocation est très bas car il n’y a pas besoin de maintenir et de parcourir des listes de mémoire libre, de plus, il n’y a pas de fragmentation. Pour augmenter l'efficacité et la fiabilité de l’allocation, éviter la fragmentation permet d’éviter de stocker des références locales inutiles ce qui signifie que le programme va s'exécuter plus rapidement.

Le désavantage principal de l’algorithme semi-space est qu’il requière deux fois plus de mémoire pour un temps donnée durant l'exécution du programme et que la moitié de cette mémoire ne peut pas être utilisée. Pour un tas de taille N, semi-space demande beaucoup plus de collection que “mark-sweep” et donc si la plupart des objets sont accessibles au moment de la collection, le semi-space devient beaucoup moins efficace que l’algorithme “mark-sweep”.

Conservateur Mostly-copying collector (MCC)[6][modifier | modifier le code]

Algortihme MCC

L’algorithme “Mostly-copying collector” MCC divise le tas en deux espaces appelés page courante et page précédente. Les nouveaux objets sont toujours alloués dans la page courante. Quand le tas est plein, le rôle des pages s’inversent et le récupérateur continue de déplacer tous les objets accessibles de la page précédente vers la page courante. Les pages de chaque espace ne sont pas nécessairement contiguës et elles peuvent même s’entrelacer. Chaque page a un identifiant qui permet de garder la trace de son statut, ce procédé permet au récupérateur de déplacer un objet de la page précédente vers la page courante de deux façons :

  • En le copiant physiquement vers la page courante
  • Ou simplement en changeant l’identifiant de sa page

Grâce au second procédé, les objets qui semblent être des références ambiguës peuvent être “déplacés” entre les espaces en gardant la même adresse virtuelle et préserver ainsi son intégrité. De même, les objets de taille importante sont également “déplacés” en utilisant ce procédé pour réduire la charge due au copiage d’une mémoire à l’autre.


Exact RC immix et conservateur RC immix[modifier | modifier le code]

Cette réalisation est le résultat de la combinaison de deux autres réalisations à part entière : Reference counting (RC) et Immix.

Reference counting (RC)[7][modifier | modifier le code]

Voir Reference counting (en).

Immix[8][modifier | modifier le code]

Le récupérateur Immix mark-region gère la mémoire de façon hiérarchique, il alloue de la mémoire de façon contiguë dans des blocs et lignes vides. Il identifie les objets et lignes utilisées et fait du marquage et de la copie dans un même passage. Alors que les récupérateurs générationnels copient tous les objets, Immix copie de façon opportuniste dans des blocs et des lignes libres quand la collection commence. Quand l’algorithme rencontre un objet qu’il ne peut pas déplacer il effectue simplement un marquage. À la fin de sa collection, il recycle tout bloc et ligne libre.

Comparaison entre récupérateur exact et conservateur[modifier | modifier le code]

L'étude aboutit sur une comparaison des différentes réalisations listées dans le rubrique précédente. La figure[9] ci-dessous, issue de cette étude, illustre les performances (temps d'exécution du programme additionné au temps de collection sur un benchmark Java) des récupérateurs :

  • exact semi-space (SS)
  • conservateur Mostly-copying collector (MCC)
  • exact mark-sweep (MS)
  • conservateur Boehm-Demers-Weiser (BDW)
  • exact RC Immix (RC Immix)
  • conservateur RC Immix (RC Immix cons)
Résultat de la comparaison


Elle les compare à un des récupérateurs le plus performant actuellement, le récupérateur exact générationnel Immix pour une taille de tas moyenne. Les premiers récupérateurs conservateurs de l’étude sont clairement inférieurs en temps d'exécution au récupérateur générationnel Immix avec une pénalité de 12 % pour BDW et de 45 % pour MCC. La comparaison entre MCC et son homologue exacte SS montre également un écart important avec 12 % de pénalité en temps d'exécution mais la comparaison entre BDW et son homologue exact MS commence à montrer une certaine équivalence en terme de performance entre récupérateurs exact et conservateur.

Cependant, ce qui met plus en avant l’équivalence est la dernière comparaison car elle montre à la fois que les versions exactes et conservatrices ont des performances similaires avec environ 2 % d’écart et, en plus, que la version RC immix conservatrice est plus performante, dans les conditions du test, que le conservateur générationnel Immix.

Ce résultat[10] prouve qu’il y a une nouvelle voie à exploiter, qu’il ne faut pas forcément sélectionner une réalisation exacte de son récupérateur car selon le contexte un récupérateur conservateur peut être autant voire plus performant qu’un récupérateur exact et que récupérateur à haute performance et récupérateur conservateur ne sont pas incompatible.

Pour des résultats plus détaillés sur cette comparaison, voir le tableau “Table 4” [11].

Récupérateur à générations ou generational GC en anglais[modifier | modifier le code]

Toutes les données d'un programme n'ont pas la même durée de vie. Certaines sont éliminables très peu de temps après leur création (par exemple, une structure de donnée créée uniquement pour retourner une valeur d'une fonction, et démantelée dès que les données en ont été extraites). D'autres persistent pendant toute la durée d'exécution du programme (par exemple, des tables globales créées pendant l'initialisation). Un ramasse-miettes traitant toutes ces données de la même façon n'est pas forcément des plus efficaces.

Une solution serait de demander au programmeur d'étiqueter les données créées selon leur durée de vie probable. Cependant, cette solution serait lourde à utiliser ; par exemple, il est courant que les données soient créées dans des fonctions de bibliothèque (par exemple, une fonction créant une table de hachage), il faudrait leur fournir les durées de vie en paramètre.

Une méthode moins invasive est le système des générations. Le ramasse-miettes opère alors sur une hiérarchie de plusieurs générations, étagées de la plus « jeune » à la plus « âgée ». Les données nouvellement créées sont (en général) placées dans la génération la plus jeune. On ramasse assez fréquemment les miettes dans cette génération jeune ; les données encore présentes à l'issue de la destruction des données inaccessibles de cette génération sont placées dans la génération d'âge supérieur, et ainsi de suite. L'idée est que les données de plus courte durée de vie n'atteignent, pour la plupart, pas la génération supérieure (elles peuvent l'atteindre si elles viennent d'être allouées quand le ramassage de miettes les repère dans la génération jeune, mais c'est un cas rare).

On utilise généralement 2 ou 3 générations, de tailles croissantes. Généralement, on n'utilise pas le même algorithme de ramasse-miettes pour les diverses générations. Il est ainsi courant d'utiliser un algorithme non incrémentiel pour la génération la plus jeune : en raison de sa faible taille, le temps de ramasse-miettes est faible et l'interruption momentanée de l'exécution de l'application n'est pas gênante, même pour une application interactive. Les générations plus anciennes sont plutôt ramassées avec des algorithmes incrémentiels.

Le réglage des paramètres d'un ramasse-miettes à génération peut être délicat. Ainsi, la taille de la génération la plus jeune peut influencer de façon importante le temps de calcul (un surcoût de 25 %, par exemple, pour une valeur mal choisie) : temps de ramasse-miettes, impact sur la localité du cache… Par ailleurs, le meilleur choix dépend de l'application, du type de processeur et d'architecture mémoire.

Langages dotés de ramasse-miettes[modifier | modifier le code]

Avantages et inconvénients des ramasse-miettes[modifier | modifier le code]

Les langages utilisant un ramasse-miettes permettent d'écrire des programmes plus simples et plus sûrs. La mémoire étant gérée automatiquement par l'environnement d'exécution, le programmeur est libéré de cette tâche, source de nombreuses erreurs difficiles à débusquer. La gestion manuelle de la mémoire est l'une des sources les plus courantes d'erreur.

Trois types principaux d'erreurs peuvent se produire :

  • l'accès à une zone non allouée, ou qui a été libérée,
  • la libération d'une zone déjà libérée,
  • la non-libération de la mémoire inutilisée (fuites mémoire).

Si des outils et une méthodologie appropriés permettent d'en réduire l'impact, l'utilisation d'un ramasse-miettes permet de les éliminer presque complètement (les fuites de mémoire restent possibles, notamment lors de collision d'exceptions, mais plus rares). Cette simplification du travail de programmation se paie de quelques inconvénients, comme de brusques ralentissements lorsque l'opération se déclenche, ce qui rend cette technique peu appropriée au temps réel.

Un ramasse-miettes augmente pourtant les performances d'un programme, même si sporadiquement l'inverse se produit. Le choix des paramètres du ramasse-miettes peut aussi altérer ou améliorer significativement les performances d'un programme. Lorsque le ramasse-miettes effectue de nombreuses opérations de copies en tâche de fond (cas de l'algorithme stop-and-copy), il tend à défragmenter la mémoire. Le ramasse-miettes peut ainsi se révéler plus rapide qu'un codage ad-hoc de l'allocation/dés-allocation. Les meilleures implémentations peuvent aussi optimiser l'utilisation des caches mémoires, accélérant ainsi l'accès aux données. L'opération de collection reste cependant coûteuse par construction.

Il est difficile de borner le temps d'exécution de la phase de collection des objets non atteignables, ce qui est peu acceptable pour les programmes temps réel ; un ramasse-miettes spécialisé (temps-réel) doit être utilisé pour cela, comme dans JamaicaVM, une implémentation de machine virtuelle Java.

Sans intervention du programmeur, un programme utilisant un ramasse-miettes a tendance à utiliser plus de mémoire qu'un programme où la gestion est manuelle (en admettant que, dans ce cas, il n'y a pas de fuites, d'erreur d'accès ou de libération). La technique classique de pré-allocation des objets utilisés, dans des pools réduit fortement les taux d'allocation/désallocation. Dans ce cas, le ramasse-miettes fournit toujours le bénéfice d'une programmation sans erreur grave de gestion de la mémoire, ce qui permet une meilleure continuité de service.

Bien que ce ne soit pas le but d'un ramasse-miettes son implémentation peut aussi faciliter l'implémentation de la Persistance d'objet (certains algorithmes sont partagés).

Bibliographie[modifier | modifier le code]

  • Herbert Schorr, William M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. CACM, août 1967 DOI:10.1145/363534.363554
  • Edsger Dijkstra, Leslie Lamport, A. J. Martin, Carel S. Scholten, Elisabeth F. M. Steffens, On-the-Fly Garbage Collection: An Exercise in Cooperation. CACM, V.21, N. 11, pp. 966-975, novembre 1978. DOI:10.1145/359642.359655
  • R. E. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, juillet 1996. (ISBN 0-471-94148-4)
  • Fridtjof Siebert, Realtime Garbage Collection in the JamaicaVM 3.0. JTRES 2007, 26-28 September 2007, Vienna, Austria
  • (en) Antony L. Hosking et Jiawan Chen, « Mostly-copying reachability-based orthogonal persistence », OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, vol. 34, no 10,‎ , p. 384-385 (ISBN 1-58113-238-7, DOI 10.1145/320385.320427)
  • (en) Hezi Azatchi, Yossi Levanoni, Harel Paz et Erez Petrank, « An on-the-fly mark and sweep garbage collector based on sliding views », OOPSLA '03 Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, vol. 38, no 11,‎ , p. 270 (ISBN 1-58113-712-5, DOI 10.1145/949343.949329)
  • (en) David F. Bacon, Perry Cheng et V. T. Rajan, « A unified theory of garbage collection », OOPSLA '04 Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, vol. 39, no 10,‎ , p. 51 (ISBN 1-58113-831-8, DOI 10.1145/1028976.1028982)
  • (en) Stephen M. Blackburn et Kathryn S. McKinley, « A Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance », PLDI '08 Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, vol. 43, no 6,‎ , p. 24 (ISBN 978-1-59593-860-2, DOI 10.1145/1375581.1375586)
  • (en) Rifat Shahriyar, Stephen M. Blackburn et Kathryn S. McKinley, « Fast conservative garbage collection », OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, vol. 49, no 10,‎ , p. 121-136 (ISBN 978-1-4503-2585-1, DOI 10.1145/2660193.2660198)
  • (en) Rick Byers, « Garbage Collection Algorithms », Project for CSEP 521, Winter,‎ , p. 3-4

Notes et références[modifier | modifier le code]

  1. En particulier les comptes-rendus de l'école d'été de Neuchâtel (Suisse) en 1972.
  2. Si la mémoire était réellement infinie, le ramasse-miettes serait alors inutile.
  3. l'étude 2014, p. 121
  4. algorithme MS 2003, p. 270
  5. algorithme Semi-space 2007, p. 3-4
  6. algorithme MCC 1999, p. 384-385
  7. algorithme RC 2004, p. 51
  8. algorithme immix 2008, p. 24
  9. graphique 2014, p. 122
  10. résultat 2014, p. 136
  11. tableau 4 2014, p. 132

Liens externes[modifier | modifier le code]