Les différents algorithmes de Garbage Collector

Accès rapide :
   Les différents algorithmes existant
           Comptage de références
           Algorithme Mark and Sweep
           Algorithme Stop and Copy
   Aspect générationnel de Garbage Collector

Une machine virtuelle Java (une JVM) est un environnement d'exécution complexe. Ce point est d'autant plus vrai si l'on regarde les mécanismes mis en jeux pour garantir la bonne gestion de votre mémoire. Au niveau des spécifications Java SE, il est dit que l'allocation de la mémoire est de votre responsabilité, mais la libération de la mémoire est de la responsabilité de la JVM. Mais cette spécification n'impose pas d'algorithmes de ramasse miettes particuliers. Chaque implémentation de JVM est donc libre de réaliser cette gestion à sa manière (pour peu que la mémoire soit finalement libérée).

Les différents algorithmes existants

Il existe plusieurs algorithmes permettant de réaliser un Garbage Collector. Voici les principaux.

Pour de plus amples informations sur les algorithmes cités ci-dessous, je vous renvoie vers le site le site Wikipedia sur lequel vous trouverez quelques compléments d'information.

Comptage de références

Cet algorithme consiste à compter le nombre de pointeurs (références) vers une zone mémoire. Quand une zone de mémoire est relâchée par votre programme, son compteur associé est décrémenté et s'il tombe à zéro alors la zone de mémoire est libérée. Les développeurs C++ sont notamment sensibilisés à cet algorithme via la technique de développement RAII (Resource Acquisition Is Initialization).

A priori, cet algorithme est très simple à coder et donc très performant (en termes de temps d'exécution). Pour autant, cet algorithme pose un gros problème : il ne permet pas de libérer les cycles de pointeurs en mémoire. Cela est ennuyeux et à ma connaissance, il n'existe aucune JVM basée sur cet algorithme.

Algorithme Mark and Sweep

Cet algorithme fonctionne en deux étapes (comme le laisse suggérer son nom). La première étape, la phase de marquage (Mark), consiste à scruter l'ensemble de piles d'exécution de votre JVM pour y retrouver tous les pointeurs sur vos objets. Ces objets sont alors marqués comme étant à conserver. Puis, pour chacun de ces objets, une analyse est faite (via le moteur Java de réflexion) pour y marquer récursivement tous les attributs qui sont eux-mêmes de type objet. Via cette descente récursive, la JVM est capable de retrouver tous les objets encore exploités.

La seconde étape, le nettoyage (sweep), consiste à scanner la liste de tous les objets instanciés (la JVM est obligée de l'avoir) et de supprimer toutes les instances non marquées lors de la phase précédente. Au terme de ce nettoyage, tous les objets non marqués (donc non atteignables) sont supprimés. Puis tous les objets restants sont démarqués. Puis la JVM recommence un cycle de GC.

Les plus curieux d'entre vous se poseront certainement une question : quand la JVM explore les piles d'exécution (il y en a normalement une par thread) comment distingue-t-'elle une valeur numérique (un long par exemple) d'un pointeur. Effectivement un pointeur n'est qu'une valeur numérique. En fait, une JVM doit obligatoirement stocker des méta-données descriptives associées à chaque bloc de données empilées sur la pile d'exécution : c'est le concept de Frame, qui est définit dans les spécifications Java SE.

Remarque : il ne faut pas confondre le concept de frame (contexte de méta-données descriptives) proposé ici avec la classe java.awt.Frame permettant de produire des fenêtres graphiques. C'est deux aspects n'ayant, bien entendu, aucun rapport.

Il est a noter qu'on peut aussi avoir un algorithme "Mark and Sweep" réalisant une défragmentation de la mémoire. Cela permet de continuer à instancier des objets de grosse taille (tableaux, ...). Cette défragmentation de la mémoire est alors réalisée durant la phase de nettoyage. Cela impose des mécanismes de synchronisation entre les threads de votre application (il est hors de question qu'un objet Java soit utilisé alors qu'il est en cours de déplacement).

Algorithme Stop and Copy

L'algorithme traditionnel découpe l'espace mémoire en deux zones de tailles égales. À un instant donné, un seul espace mémoire est utilisé. Tant que celui-ci n'est pas saturé, on ajoute les objets les uns après les autres. L'instanciation mémoire est donc beaucoup plus rapide qu'avec Mark and Sweep. Lors de la saturation de l'espace mémoire, tous les survivants sont basculés dans le second espace mémoire, puis on cherchera à saturer ce second espace. À ce moment-là les survivants seront basculés dans le premier espace mémoire et ainsi de suite jusqu'à l'arrêt de la JVM.

Les survivants sont détectés via une phase de marquage similaire à Mark and Sweep. Vous l'aurez tous compris : le gros problème de cet algorithme est la perte sèche de 50% de l'espace disponible. Par définition, cet algorithme réalise une défragmentation de la mémoire.

Dans le cas de la JVM Hotspot, Stop and Copy est utilisé mais une optimisation fait qu'il n'y aura pas deux zones, mais trois (Eden et deux survivor spaces). Cela est possible grâce à l'aspect générationnel du GC de Hostspot. S'il y a trop de survivants, on pourra les maintenir dans un autre espace mémoire.

Aspect générationnel de Garbage Collector

Assez classiquement, une JVM propose un GC générationnel : cela veut dire que votre espace de mémoire est divisé en plusieurs zones de mémoire. Chaque zone de mémoire correspond à une génération d'objet et utilise un algorithme de GC adapté à cette génération d'objets. Dans le cas de Hotspot, il y a trois générations d'objets. Ces trois générations sont :

• L'espace des jeunes objets (aussi appelé Young Space) : cet espace de mémoire est traité avec un algorithme dérivé de Stop and Copy. Cet algorithme est adapté à la gestion d'objets de faible durée de vie. Statistiquement, une très grande proportion d'instances Java produites meurt rapidement : il est donc important de plutôt favoriser les temps d'allocation. Pour ce faire, le Yound Space est divisé en trois parties distinctes : l'Eden et deux Survivor Spaces. L'Eden (le paradis des objets Java) est l'espace dans lequel toutes les instances Java naissent : cette zone peut être vue comme une pile. Dès que l'Eden est saturé, on recopie l'ensemble des survivants dans l'un des deux Survivor Spaces. Du coup l'Eden est considéré comme vide et on peut commencer à le réalimenter. Lors de la prochaine saturation de l'Eden, tous les survivants de cette zone ainsi que du précédent Survivor Space seront recopiés dans l'autre Survivor Space et ainsi de suite. On bout d'un certain nombre de recopie, un objet sera considéré comme ancien et sera alors déplacé dans le "Old Space" : effectivement recopier Ad vitam æternam des instances n'est pas forcément une bonne idée (déplacer un objet en mémoire sous-entend de mettre à jour toutes les références vers cet objet). Notez aussi que si une instance dépasse une certaine taille, on considère alors qu'elle risque de vivre plus longtemps et on la créée alors directement dans le "Old Space".

• L'espace des vieux objets (aussi appelé Old Space ou encore Tenured Space) : cet espace de mémoire est géré avec l'algorithme Mark and Sweep. Cet algorithme est plus adapté pour la gestion d'objets de longue durée de vie. Or un programme utilise souvent des instances de courte durée de vie et des instances de longue durée de vie : c'est pour cela que Hotspot vous propose ces deux algorithmes. Notez aussi que l'algorithme proposé cherche à compacter la mémoire, ce qui entraine encore des déplacements d'instances. Dans cet algorithme, les objets trouvent assez rapidement leur place définitive, car les objets de très longue durée de vie se retrouvent compactés en début de l'espace mémoire de la génération ancienne. Ce compactage de l'espace mémoire permet de pouvoir instancier de gros objets (tableaux, ...). Sans ce compactage, vous pourriez avoir beaucoup de mémoire disponible, mais très fortement fragmentée et il serait alors impossible d'avoir un espace de mémoire compact et suffisamment grand.

• Et enfin l'espace des objets permanents (aussi appelé Perm Gen, pour Permanent Generation) : un objet permanent est un objet dont on est certain qu'il ne sera pas relâché avant la fin de l'exécution de la JVM. Du coup, il devient inutile de lancer un algorithme de ramasse miettes sur cet espace mémoire. Il serait donc dommage de les placer dans le Young Space ou le Old Space : on saturerait les espaces plus fréquemment et donc on consommerait plus de temps CPU pour l'exécution du GC. On soulage ainsi l'activité du GC. Durant l'exécution d'une JVM, la taille du Perm Gen ne peut qu'augmenter : souvent elle augmente très rapidement au démarrage de la JVM puis sa croissance ralentit très rapidement. Cela est dû à la nature des instances qui y sont stockées : pour être considéré comme permanent, une instance Java doit être préfixée des qualificateurs static et final et donc être un attribut de classe.

IMPORTANT : à partir de la version 8.0 du standard Java SE, Hostpot supprime la troisième génération, celle des objets permanents. Si vous utilisez cette version de Hostspot (ou une version supérieure) ne cherchez donc pas à localiser le PERM dans les outils de monitoring. Ne cherchez pas non plus à utiliser les options de la JVM associées.

Le diagramme proposé ci-dessous vous montre ces différents espaces mémoire. Les proportions de tailles des différents espaces mémoire ne sont absolument pas représentatives de la réalité. La zone de mémoire appelée Code Cache correspond à l'endroit où sont montés les codes machines de vos différentes classes.

Quand une phase de nettoyage de la mémoire (une phase de GC) déclenche, tous les espaces ne sont pas forcément collectés. Une collecte mineure correspond à un nettoyage du Young Space. Il se peut que certaines instances Java passent dans le Old Space durant cette phase de collecte mineure : du coup, si le Old Space se sature, cela déclenche une phase de collecte majeure (Full GC). Le Old Space étant très souvent bien plus grand que le Young Space, mécaniquement le temps d'une collecte majeure sera plus long que celui d'une collecte mineure.