a plupart des langages de programmation modernes automatisent les activités d'allocation et de libération mémoire grâce à un organe "magique" : le
Garbage Collector (ou Ramasse Miettes). Cette automatisation de tâches qui étaient jadis du ressort du développeur est très séduisante car elle évite les fuites mémoire et les tentatives de libération répétée des mêmes zones mémoire (nos applications en sont d'autant plus robustes), tout en permettant au développeur de gagner du temps et de se focaliser sur l'objectif principal
: Son application (les temps de développement sont réduits). Toutefois, le Garbage Collecting peut s'avérer coûteux, dangereux ou inadapté dans certains cas.
Dans cet article, nous allons brièvement présenter différents algorithmes de Garbage Collection, leurs attraits, leurs limitations, ainsi que les raisons qui ont poussé leurs inventeurs à évoluer vers d'autres techniques. Une fois ces concepts posés, nous verrons quels algorithmes ont été choisis dans le Common Language Runtime de la plate-forme .NET, ainsi que dans la machine virtuelle de Sun Microsystem, Hotspot.
Enfin, en guise de conclusion, nous proposerons quelques Design Patterns liés à la gestion mémoire, qu'ils soient génériques (FlyWeight, Pool) ou liés à une plate-forme (IDisposable).
Toute classe Java ou C# possède au moins un constructeur, c'est-à-dire une méthode un peu spéciale qui aura pour rôle de créer de nouveaux objets (instances) de cette classe. La réalité est en fait un peu plus complexe, puisque c'est la machine virtuelle (JVM ou CLR) qui a la responsabilité d'allouer suffisamment de mémoire pour stocker l'objet en question; cette allocation se fait dans une zone mémoire réservée appelée le "tas" (ou "heap" en anglais). Le constructeur n'intervient que plus tard, son rôle se limitant généralement à l'initialisation des valeurs des différents attributs de l'objet fraîchement créé.
Un objet n'a d'intérêt que tant que le programme qui l'a engendré peut interagir avec lui, donc tant qu'il existe une référence (directe ou indirecte) permettant au programme d'atteindre cet objet. Plus formellement, nous appellerons "référence racine" toute référence statique ou toute référence appartenant à la "pile" ("stack") d'un des threads de notre application.
Le rôle d'un Garbage Collector sera de bâtir ces graphes d'objets en partant des références racines et en parcourant récursivement toutes les références rencontrées. Tout objet qui n'appartiendra pas à l'un de ces graphes devra être supprimé, et sa mémoire récupérée.
L'algorithme Mark and Sweep est probablement le plus simple et le plus connu. Dans son principe, lorsque le GC se déclenche, il part des références racines de l'application et suit récursivement toutes les références qu'il rencontre. Chaque objet ainsi visité est "marqué" : il est effectivement accessible au programme, et ne doit en aucun cas être supprimé. Dans un deuxième temps, le GC joue le rôle du balayeur (opération "sweep") : il parcourt linéairement le tas, objet par objet, et supprime tout objet qui n'est pas marqué et récupère la mémoire qui lui était allouée. Bien entendu, il efface également les marques des objets "survivants" en prévision de la prochaine collecte.

Il est évident que la collecte des objets (du moins la première étape "mark") ne peut s'effectuer que si tous les threads applicatifs sont arrêtés. Donc lorsque le GC se lance, l'application s'interrompt complètement.
L'algorithme Mark and Sweep est très simple, mais pose un certain nombre de problèmes :
Cet autre algorithme découpe l'espace d'allocation mémoire, le tas, en deux parties égales; lorsque le GC se déclenche, il parcourt le graphe d'objets référencés dans le premier espace. Les objets référencés sont tout simplement copiés les uns après les autres vers le second espace. Toutes les références de l'application sont ensuite mises à jour pour pointer vers ce nouvel espace. En bien sûr, lors de la prochaine collecte, on recopiera les objets vivants vers le premier espace, et ainsi de suite.

Cette technique a l'avantage de compacter automatiquement le tas, ce qui élimine la fragmentation, et limite donc la pagination des systèmes d'exploitation. Un autre intérêt par rapport au Mark and Sweep est que le travail du GC n'est plus proportionnel à la taille du tas, mais à la taille et au nombre des objets référencés (accessibles à l'application).
Mais il reste un certain nombre de problèmes en suspens :
Ces limitations amènent logiquement à différentes familles de GC :
Les machines virtuelles (JVM ou CLR) sont elles-mêmes implémentées dans des langages proches du système d'exploitation tels que le C/C++ ou assembleur. Lors du parcours des objets, ou lors du parcours systématique du tas, un problème récurrent se présente : comment distinguer une zone mémoire contenant un pointeur (vers une autre zone) d'une zone contenant une valeur entière ? En effet, un pointeur n'est finalement rien d'autre que l'adresse d'une case mémoire, donc un entier.
Certains algorithmes partent du principe "dans le doute, s'abstenir", et préfèrent ne pas interagir avec certaines zones mémoire ambiguës : si le type d'une zone ne peut pas être déterminé, cette zone sera laissée de côté par le GC. Cette approche simpliste aboutit à des machines virtuelles dans lesquelles les objets ne sont pas certains d'être "libérés" un jour, c'est-à-dire que leur méthode de finalisation risque de n'être jamais invoquée, empêchant le développeur de libérer les ressources non-mémoire (Nous reviendrons sur la relation entre finalisation d'objets et Garbage Collector dans les sections suivantes). Ce type d'algorithme "prudent" est dit "conservatif".
La tâche de collecte d'objets s'allonge avec le nombre et la taille des objets : imaginez un tas de 1 Go dans lequel vous appliquez un GC par recopie ! Il est donc assez logique de vouloir partitionner la collecte en plusieurs parties cohérentes, que l'on peut déclencher indépendamment les unes des autres; cela permet de ne pas bloquer l'application pendant un délai trop long, et donc de rendre nos applications plus fluides. La contre-partie de cette découpe est que la somme des temps d'exécution de chaque partie est plus long que le temps d'exécution d'une collecte atomique, donc nous perdons en performances pures (throughput)...
Vous connaissez bien sûr les principes de localité :
Si les systèmes d'exploitation tirent profit de la première propriété pour implémenter leurs mémoires virtuelles, les GC jouent sur la seconde pour rentabiliser leur activité de collecte. Il suffit en effet de distinguer les différentes générations d'objets; les objets "jeunes" ayant statistiquement plus de risques d'être dé-référencés que les "vieux", les GC parcouront en priorité la partie du tas correspondant à la jeune génération. Ils ne s'intéresseront aux générations précédentes que si la collecte au sein de la jeune génération n'a pas été assez riche.
Il n'est pas rare d'allouer de nouveaux objets dans une boucle d'itération. Or ces objets devront mourir à la fin de l'itération courante. On a donc tout intérêt à les allouer dans une zone mémoire réservée dans laquelle le GC passera en priorité; la proportion d'objets à collecter par rapport au nombre d'objets global sera bien plus élevée dans cette génération que dans les suivantes.
L'introduction de générations a plusieurs répercussions positives sur les propriétés des GC. Tout d'abord, leur travail est moins important que précédemment puisqu'ils ne parcourent pas nécessairement tout le tas à chaque collecte. Les performances globales des applications sont donc meilleures. D'autre part, mais c'est un corollaire, le travail à réaliser d'un seul coup est généralement moins lourd qu'avant, donc on gagne également en fluidité. On comprend bien pourquoi la plupart des GC récents sont générationnels.
Les algorithmes générationnels sont paramétrables, et il faut savoir jouer sur leurs réglages pour optimiser le GC en fonction des besoins de nos applications. Par exemple, on peut modifier le nombre d'itérations du GC après lesquelles un objet sera promu dans la génération suivante (on parle de "seuil de promotion" pour dénoter ce paramètre). On pourra aussi jouer sur le nombre de générations en présence...
En pratique, choisir deux ou trois générations rend les implémentations assez simples. On choisira généralement le nombre de générations en fonction du nombre de classes d'âge des objets, si l'on peut le déduire de l'application. Il n'est pas rare non plus de voir les GC réserver une zone mémoire particulière pour les objets "immortels" ou les objets trop volumineux, afin d'éviter des collectes par recopies inefficaces.
Concernant le seuil de promotion, choisir la valeur "1" est tentant puisque cela ne nécessite pas de se souvenir de l'âge de chaque objet, ce qui mène à une occupation mémoire moins importante. Mais d'un autre côté, cette valeur a la mauvaise idée de promouvoir des objets très jeunes, dont l'espérance de vie n'est pas encore bien définie.
L'algorithme choisi par Microsoft pour le Framework .NET est un compromis entre le Mark and Sweep et la collecte par recopie, que l'on appelle le "Mark and Compact". A chaque collecte, le GC bâtit les graphes d'objets atteignables à partir de chaque référence racine; dans un deuxième temps, il parcourt le tas linéairement, objet par objet. Chaque fois qu'il trouve un objet non référencé, il considère sa mémoire comme libre; les prochains objets "survivants" seront recopiés vers le bas du tas afin d'écraser la zone mémoire des objets devenus inutiles et donc de compacter le tas. Et bien entendu, les références pointant vers ces objets seront mises à jour pour refléter le déplacement de ces derniers.
Il existe une petite exception à ce mécanisme de parcours et d'écrasement par recopie pour les objets ou les structures très volumineux (plus de 20 Ko) qui seront, eux, stockés dans un endroit réservé du tas et pratiquement jamais recopiés.

Au vu de cette description de l'algorithme, on s'aperçoit vite que la notion de génération est très simple à implémenter : le tas respecte l'ordre de création des objets, donc les générations plus anciennes précèdent nécessairement les plus récentes. Plus précisément,



Un cycle de collecte .NET ne se déclenche que lorsque la génération 0 est pleine, c'est-à-dire lorsque le tas ne dispose plus de suffisamment de place pour accueillir de nouveaux objets, et ne s'intéresse qu'aux générations qui permettront de satisfaire les besoins immédiats en allocation mémoire. Le GC ne collecte que la génération 0 si cela suffit à la demande d'allocation du code applicatif (voilà pourquoi, dans le dernier diagramme ci-dessus, une zone mémoire de la génération 2 n'a pas été collectée).
Il est impossible de décrire le mode de fonctionnement "du" Garbage Collector Java, puisque cet aspect de la JVM est très peu contraint par la spécification. En pratique, il peut exister autant d'algorithmes de GC que de machines virtuelles (entendez par là UNE version de JVM construite par UN éditeur, sur UN OS d'UNE version bien déterminée). Nous ne nous pencherons ici qu'à la machine virtuelle de Sun Microsystem, dans sa version 1.3.1 sous Sun Solaris.
La JVM de Sun Microsystem utilise trois types d'algorithmes différents, selon que l'on collecte les objets morts, que l'on promeuve les objets survivants... Mais l'algorithme principal est de type Mark and Compact générationnel, tout comme dans le framework .NET.
Une avancée significative au crédit de la JVM : le GC est complètement paramétrable. Si l'on parvient à déterminer qu'il constitue un goulot d'étranglement pour une application, cela devient intéressant de mieux paramétrer la taille des générations (qui ont des valeurs par défaut dimensionnées pour de petites applications graphiques clientes). Comment savoir la durée passée par une application dans l'activité de GC ? Lancez tout simplement la JVM en mode -verbose:gc, les traces vous informeront précisément sur les instants et les durées d'exécution du Garbage Collector :
D:\DotNetGuru>java -verbose:gc Hello
Guru Says Hello
[Full GC 245K->134K(1984K), 0.0177229 secs]
Hello.java.txt
Pour être précis, la JVM de Sun Microsystem utilise deux générations principales (jeune et ancienne), dans lesquelles il faut distinguer plusieurs sous-ensembles (chambre d'immortels, Eden, espaces de survivants...); toutes ces subtilités sont résumées par le diagramme suivant :

Il est possible de raffiner les paramétrages par défaut, et en particulier le dimensionnement de chacune de ces zones, en fonction des besoins d'une application. Voici les principales option de ligne de commande que l'on peut passer à la JVM de Sun :
Cela va sans dire, on peut jouer sur le paramétrage de chaque segment du tas géré par la JVM. Mais ces paramétrages n'ont pas d'abaque : il faudra un peu de bon sens et beaucoup de rigueur de benchmarking afin de trouver la combinaison de paramètres qui convient le mieux à vos applications.
Les deux runtimes (JVM et CLR) permettent aux applications de déclencher le Garbage Collector de manière autoritaire. En Java, cela passe par l'invocation de la méthode System.gc(). D'aucun diront que cette instruction n'est en réalité qu'une indication destinée au GC pour qu'il se déclenche si le coeur lui en dit; en réalité, sur les JVM de Sun à partir de la version 1.3.1, sur Solaris et Windows, cet appel invoque réellement le garbage collector.
En .NET, il suffit de faire appel à System.GC.Collect() pour faire de même. Attention toutefois, cette instruction force le GC à collecter toutes les générations (0, 1 et 2). Si vous souhaitez être plus fin, utilisez la version surchargée System.GC.Collect(n), où n est l'indice de la génération que vous souhaitez voir collectée.
Bien sûr, ce n'est pas toujours une bonne idée que d'invoquer explicitement le GC : l'invoquer trop souvent dégraderait considérablement les performances de vos applications. Toutefois, l'invoquer avant une tâche qui crée quelques objets et qui aurait un besoin impérieux de ne pas être interrompue peut s'avérer utile. Il n'existe en effet aucun moyen programmatique (ni en Java ni en C#) d'inhiber le Garbage Collector, ne fût-ce que temporairement.
C# comme Java donnent à tout objet l'occasion d'exécuter du code afin de libérer les ressources allouées. Les ressources en question ne sont pas des ressources mémoire (puisque le GC se charge de libérer tous les objets de manière transparente), mais plutôt de type descripteur de fichier, de socket, connexions aux bases de données, etc...
A cet effet, Java nous invite à redéfinir la méthode finalize() héritée de la classe générique Object :
public class ObjetFinalise{
public ObjetFinalise(){
// Constructeur, invoqué par
// l'utilisateur par l'opérateur
// "new"}
protected finalize() throws Throwable{
// Méthode de finalisation, invoquée
// par le Garbage Collector} } ObjetFinalise.java
C#, lui, emprunte la syntaxe des destructeurs de C++ pour implémenter sa méthode de finalisation. Ne vous y trompez pas : il n'existe bien évidemment pas de destructeur en C# : c'est le GC qui déclenchera cette méthode dont la syntaxe ressemble simplement à un destructeur :
public class ObjetFinalise{
public ObjetFinalise(){
// Constructeur, invoqué par
// l'utilisateur par l'opérateur
// "new"}
protected ~ObjetFinalise {
// Méthode de finalisation, invoquée
// par le Garbage Collector} } ObjetFinalise.cs
Attention, pour des raisons d'implémentation que nous n'exposerons pas ici, le simple fait de définir une méthode de finalisation rend la création des objets plus coûteuse, et allonge le délai de libération des objets. Ce qui fait qu'en pratique, si vous implémentez ces méthodes, il vaut mieux les voir comme un garde-fou qui libèrerait les ressources si le reste du code avait omis de le faire; mais il vaut toujours mieux prévoir un mécanisme supplémentaire dans vos classes qui libère (généralement le plus tôt possible) les ressources monopolisées par un objet. Si la finalisation se déclenche, elle vérifiera si les libérations ont déjà eu lieu, et ne les prendra en compte que dans le cas contraire.
Une dernière mise en garde : êtes-vous certain que toutes les méthodes de finalisation de tous les objets C# ou Java seront appelées ? La réponse dépend cette fois du langage (en fait, du CLR / JVM). En C# : oui, tous les finaliseurs seront appelés avant le terme de l'application. En Java : non, ce n'est pas garanti; les finaliseurs ne seront déclenchés que si le GC collecte effectivement tous les objets de l'application avant la terminaison de l'application. Donc en pratique, il vaut mieux toujours invoquer System.gc() avant la fin d'une application Java (ce qui garantit, mais c'est récent, que tous les objets seront collectés et finalisés s'il y a lieu).
C'est bien connu, les activités non applicatives les plus coûteuses à l'exécution d'applications orientées objet sont liées à la création et à la destruction d'objets (au sens large : allocation mémoire, initialisation des attributs, puis finalisation et garbage collection). Or certains objets ont des propriétés intéressantes qui nous permettent d'imaginer certaines optimisations, dont nous vous proposons ici un échantillon.
Imaginez des classes dont vous ne pouvez vous passer dans une application; vous en créez de nombreuses instances, mais souvent pour les utiliser brièvement puis les laisser choir après usage (comprenez : à la merci du Garbage Collector). Il serait certainement bien plus judicieux de "recycler" ces objets très utiles plutôt que de passer votre temps à les créer puis à les détruire.
Il convient donc d'implémenter un "pool" d'objets réutilisables. Lorsque votre application aura besoin d'une instance, elle en fera la demande au pool; et au lieu de s'en débarrasser, elle renverra l'objet au pool après utilisation. Celui-ci pourra donc choisir de détruire l'objet, ou au contraire de le conserver en prévision d'une demande à venir (du même client, ou d'un autre).

On peut spécialiser un pool afin qu'il ne gère qu'un type d'objets, ou au contraire le rendre générique. On peut placer des contraintes sur le pool (nombre d'objets minimum, maximum, le pas d'incrémentation, le délai d'inactivité avant de supprimer un certain nombre d'instances), ou encore le rendre intelligent et proactif (si le pool est une classe active, qui possède donc son propre thread, rien ne l'empêche de faire des statistiques et tenter de prévoir le besoin de création de nouveaux objets avant d'arriver à une situation de carence).
Pour résumer, les pools sont des "factories singleton" permettant d'optimiser la création et la gestion d'objets réutilisables. Leur usage limitera le nombre de créations d'objets et de cycles de Garbage Collection d'où une nette amélioration des performances globales des applications. Vous pouvez assez simplement en implémenter par vous mêmes, ou encore faire quelques recherches sur le Web : de nombreux algorithmes ont été implémentés dans divers langages de programmation, y compris Java et C#.
Une autre technique applicable cette fois à des systèmes manipulant un grand nombre d'objets similaires : au lieu de créer des objets identiques ou très proches à de nombreuses reprises, on peut imaginer de partager certains de ces objets entre plusieurs clients (comprenez plusieurs instances de classes qui utilisent ces objets).
L'exemple le plus connu de ce pattern est l'implémentation orientée objet d'un éditeur de documents dans lequel chaque caractère était représenté par un objet en mémoire. Pour éviter l'explosion du nombre d'objets, on utilise le FlyWeight qui consiste simplement à créer un ensemble d'objets distincts (à la demande), et à renvoyer aux classes utilisatrices une simple référence vers ces objets, évidemment partagés. Dans le cas de l'éditeur de documents, on pouvait typiquement représenter 180000 caractères par 480 objets en mémoire ! (480 car en plus des caractères en question vient se greffer la gestion des polices tout simplement).
Mais on peut appliquer cette pratique à d'autres domaines : imaginez un site Web sur lequel les clients peuvent sélectionner des livres et les placer dans leur caddie virtuel. Les caddies peuvent évidemment porter la liste des objets instances de Livre, mais il serait plus judicieux qu'ils partagent les livres qu'ils ont en commun. Le plus simple est donc d'implémenter une factory qui créera les livres à la demande et renverra aux caddies des références vers ces livres. Si un deuxième caddie demande à créer un livre qui a déjà été instancié précédemment, la factory se borne à renvoyer une référence vers le même bouquin.

Notez que si dans cet exemple très simple les objets ne portent aucun état conversationnel par rapport au caddie virtuel (le nombre d'exemplaires de chaque bouquin), rien ne s'y oppose dans l'absolu. Il suffira de décrire ces informations contextuelles dans une instance de classe par caddie et par bouquin (le contexte est généralement bien plus succinct que l'objet lui-même, donc notre FlyWeight reste rentable) et de passer ce contexte à chaque invocation de méthode sur l'objet partagé.
Le framework .NET propose un Pattern intéressant lorsqu'on souhaite libérer les objets de manière déterministe (c'est-à-dire lorsque l'on souhaite maîtriser l'instant précis où seront libérés les objets). Il suffit pour cela d'implémenter l'interface IDisposable, et d'implémenter sa méthode void dispose(). Cette méthode pourra être invoquée directement afin de libérer l'objet immédiatement, sans attendre un cycle de garbage collection.
Le langage C# propose également, côté client d'un objet IDisposable cette fois, une syntaxe raccourcie permettant de libérer l'objet dès que l'on sort de son scope d'utilisation :
public class ClientIDispose{
public static void Main(){
// Première manière :try{ ObjetDisposable o =
new ObjetDisposable();
// Utilisation de oo.dispose(); } catch(Exception e){
// Exception si dispose est invoquée
// plusieurs fois}
// Deuxième manière :
using (ObjetDisposable o2 = new ObjetDisposable(){
// utilisation de o2} } } ClientIDispose.cs
Mais attention, si l'on "dispose" un objet, il n'y a plus aucune raison de laisser le Garbage Collector le finaliser quelques instants plus tard (cette opération de finalisation est vraiment lourde dans le processus du GC). Le framework .NET expose donc une méthode statique permettant de "désinscrire" un objet de la liste des instances "à finaliser par le GC" : System.GC.SuppressFinalize(object). Elle sera typiquement appelée par "dispose" (si elle est invoquée). Du coup, le code client de notre classe a toute latitude pour choisir entre :
Dans certains cas très particuliers, il peut être intéressant de manipuler des objets vivant dans le tas, tout en laissant la possibilité au GC de récupérer ces objets si la mémoire venait à manquer. Nous ne voulons pas dire par là que ces objets sont superflus, mais simplement que leur perte n'est pas grave car ils peuvent toujours être reconstruit d'une manière ou d'une autre. L'exemple le plus flagrant : les objets que l'on placerait dans un cache.
Seulement voilà : si l'on dispose d'une référence sur un objet, il sera atteignable depuis les références racines. Donc le Garbage Collector n'osera jamais le libérer. D'un autre côté, si nous affectons "null" à nos références, nous ne pouvons plus du tout accéder aux objets...
La ruse consiste à utiliser une référence faible (Weak Reference), qui nous permet d'accéder à l'objet, tout en faisant croire au GC que plus personne ne pointe sur cet objet. Bien entendu, comme le GC peut libérer l'objet instantanément, il faut toujours tester la référence faible avant de l'utiliser; si l'objet a été libéré entre temps, la référence aura un objet sous-jacent de valeur "null".
Cette notion est disponible aussi bien dans en C#.NET :
public class WeakReferenceTest{
public static void Main(){
// Instanciation et remplissage d'une
// collection lArrayList l = ...;
// Création de la référence faibleWeakReference wr =
new WeakReference(l);
l = null;
// ...
// Tentative de travail sur la collection
// si elle n'a pas été collectée
if (wr.IsAlive){
l = wr.Target as ArrayList;
// Manipulation de l} } } WeakReferenceTest.cs
qu'en Java :
public class WeakReferenceTest{
public static void main(String[] argv){
// Instanciation et remplissage d'une
// collection lArrayList l = ...;
// Création de la référence faibleWeakReference wr =
new WeakReference(l);
l = null;
// ...
// Tentative de travail sur la collection
// si elle n'a pas été collectéel = (ArrayList) wr.get();
if (l != null){
// Manipulation de l} } } WeakReferenceTest.java
Dans cet article, nous avons pris connaissance des principales techniques de Garbage Collecting, nous avons décortiqué un peu la manière dont ces organes fonctionnent dans une JVM ou dans le CLR .NET, et nous avons conclu sur quelques pratiques récurrentes dans le domaine de la gestion de la mémoire.
Le sujet est vaste, et il serait bien présomptueux de prétendre le couvrir complètement dans une première approche. Par exemple, certains inconvénients des Garbage Collectors n'ont pas été évoqués. Nous laissons le lecteur curieux se poser la question de l'aspect temps réel d'un Garbage Collector : est-il possible d'implémenter des applications Java ou .NET complètement déterministes, dans lesquelles on respecte de manière certaine les échéances des traitements ?
Allez, un petit coup de pouce : sachez qu'il existe des groupes de travail et des spécifications complémentaires pour implémenter des machines virtuelles temps réel (RT Java par exemple), qualité indispensable à de nombreuses applications industrielles... Bonne recherche.
Auteur : Thomas GIL
Copyright : DotNetGuru ©