Le Garbage Collector en JavaScript

Cet article fait partie d’une série d’articles sur la mémoire en Javascript :

• Comprendre la mémoire en Javascript
• Le Garbage collector en Javascript

En Javascript, la gestion de la mémoire est invisible pour le développeur. Lorsque l’ont créé un objet, une fonction, un tableau, le moteur Javascript alloue l’espace mémoire dédié sans que nous aillions besoin de faire quoi que ce soit. Mais une fois utilisé, l’espace mémoire doit être libéré pour laisser la place à de futures allocations.

Dans les langages “Bas-niveau” comme le C, c’est le développeur qui est en charge de la gestion mémoire avec la fonction malloc() pour allouer un espace et free() pour le libérer.

En Javascript, c’est le garbage collector (ramasse-miette en français — oui, ça fait un peu penser à un aspirateur de table) qui est responsable de libérer l’espace mémoire inutilisé.

Afin de mieux comprendre le fonctionnement du garbage collector, nous allons aborder le concept d’accessibilité.

L’accessibilité

Le concept d’accessibilité peut être décrit par :

Une valeur à la garantie de disposer d’un espace mémoire tant qu’elle est accessible

Une valeur accessible c’est :

• La fonction exécutée avec toutes ses variables locales et ses paramètres.
• Toutes les fonctions imbriquées, leurs variables locales et leurs paramètres présents dans la call-stack.
• Les variables globales.
• Toute valeur référencée depuis la racine du programme.
• Toute valeur référencée depuis une valeur elle-même accessible.

Toute valeur n’étant pas noté comme “accessible” sera supprimé par le processus de garbage collection.

Les algorithmes de comptage de références

Les garbages collectors, présents dans de nombreux langages, implémentent tous des algorithmes plus ou moins performant.

Les premiers utilisés étaient les algorithmes de reference-counting.

Le principe est simple :

Chaque zone mémoire dynamique possède un compteur de référence sur celle-ci. À chaque fois qu’une nouvelle référence pointe sur cette zone, le compteur s’incrémente. Et inversement, à chaque fois qu’une référence est retirée, le compteur se décrémente.

Si un compteur atteint la valeur 0, la mémoire est libérée.

Voici une représentation schématique du fonctionnement d’un algorithme de reference-counting.

Cet algorithme, facile à implémenter, pose cependant un problème majeur. Il ne gère pas les références circulaires.

Lorsqu’un objet A pointe vers un objet B qui pointe lui-même sur l’objet A, mais qu’aucune autre référence ne pointe vers A ou B, alors les espaces mémoires de A et B ne seront jamais libérés, même s’ils ne sont plus utilisés.

Chacune de ces zones mémoires sera incrémentée à 1, car le premier aura une référence vers le second est inversement. Les deux zones ne seront donc jamais libérées.

En Javascript, une référence circulaire peut être créée telle que :

const a = {
    refB: null
}

const b = {
    refA: a
}

a.refB = b

Pour répondre à cette problématique, un nouvel algorithme a été créé, le Mark and Sweep.

L’algorithme Mark and Sweep

L’algorithme Mark and Sweep, très utilisé dans les garbage collectors actuels, va nous permettre de résoudre les problèmes de référence circulaire vu ci-dessus.

Plutôt que de répondre à la définition “un objet n’est plus nécessaire”, le mark and sweep va répondre à la définition :

un objet ne peut être atteint

Fonctionnement de l’algorithme Mark and Sweep

L’algorithme de Mark and Sweep se déroule en 2 phases :

• La phase de marquage (mark)
• La phase de balayage (sweep)

La phase de marquage

Dans cette première phase, chaque espace mémoire alloué est marqué pour définir si celui-ci est accessible ou non.

L’algorithme permettant ce marquage est l’algorithme de parcours en profondeur. Il consiste à considérer chaque objet comme un nœud. En partant des racines (par exemple, window en Javascript), l’ensemble des nœuds ayant pour référence un nœud déjà visité seront visités de manière récursive jusqu’à avoir parcouru l’ensemble des nœuds.

Chaque nœud visité est noté, ce qui indique qu’il est encore utilisé.

Tous les éléments non marqués seront supprimés lors de la phase de balayage.

Dans le schéma ci-dessus, on remarque bien le fonctionnement de l’algorithme de parcours en profondeur. Tous les nœuds sont parcourus de façon récursive. Ceux qui ne sont pas liés (directement ou indirectement) à un point d’entrée ne sont pas marqués. Les références circulaires dans ce schéma seront donc bien supprimé comme nous allons le voir juste en dessous.

La phase de balayage

La phase de balayage consiste à parcourir l’ensemble des nœuds. Tous les nœuds non marqués sont supprimés de la heap et leur espace mémoire libéré. Si le nœud est marqué, alors on supprime la marque afin de pouvoir relancer notre phase de marquage plus tard.

Comme on le voit sur le schéma ci-dessus, les nœuds non marqués sont supprimés puis on retire les marquages sur tous les nœuds pour recommencer une nouvelle phase de marquage.

Avantages & inconvénients de l’algorithme Mark and Sweep

Le principal avantage de cet algorithme est sa capacité à gérer les références cycliques.

Néanmoins, il possède aussi un inconvénient au niveau de la gestion de la mémoire.

À chaque fois que celui-ci libère de la mémoire, il créé des zones (fragments) non utilisés. Ceux-ci peuvent être de nouveau rempli uniquement à condition de disposer de l’espace nécessaire pour nos nouvelles allocations. Il se pourrait donc qu’une nouvelle allocation demandée ne puisse arriver à son terme malgré la disponibilité de la mémoire.

Dans le schéma ci-dessus, on a simplifié la représentation de la mémoire en une suite de carré formant chacun un espace mémoire. Les couleurs représentent des enregistrements (suite d’espaces mémoire) qui ne peuvent pas être séparés.

Lors de la phase de balayage du garbage collector, 2 enregistrements (jaunes) de 3 carrés chacun sont libérés. On a ainsi 6 espaces mémoires libres. On souhaite ensuite créer un nouvel objet faisant 4 espaces mémoire (bleu).

Comme on le voit sur la représentation, ce n’est pas possible. La mémoire disponible et pourtant supérieur à la mémoire demandée, mais on ne retrouve pas une suite de 4 espaces mémoires d’affilée disponible. C’est ce qu’on appelle la fragmentation.

Conclusion

Le garbage collector n’a désormais plus de secrets pour vous. Bien qu’il existe plusieurs algorithmes de garbage collection, le Mark and Sweep est présent dans la part majeure des ramasses-miettes.

Il est important de noter que ces algorithmes ne sont pas simplement implémentés dans les moteurs Javascript mais sont souvent couplés avec d’autres algorithmes et système pour accroître au mieux les performances du ramasse-miettes.