Soutenance mémoire
Ramasse-miettes à comptage de références
Souvent utilisés pour leur simplicité [53, 54], ils présentent comme principal inconvénient de ne pas réclamer les cycles et d’être moyennement performants.
Fonctionnement du ramasse-miettes à comptage de références
Avec un ramasse-miettes à comptage de références, chaque bloc mémoire alloué connaît le nombre de fois qu’il est référencé, au moyen d’un compteur porté par le bloc lui-même. Ce compteur est incrémenté lorsque l’on crée une nouvelle référence sur le bloc, et on le décrémente lorsqu’on supprime l’une de ces références. Lorsque le compteur arrive à zéro, on peut le libérer puisqu’il n’est plus accessible. Avant de libérer complètement l’objet de la mémoire, il faut mettre à jour les compteurs de tous les objets sur lesquels pointait celui-ci, ce qui peut entraîner une cascade de libérations.
Les avantages et inconvénients du comptage de références
Avantage 1 Avec ce système de comptage, on peut très rapidement libérer les blocs dont le compteur est devenu nul : il n’est pas nécessaire d’attendre le prochain cycle de ramassage pour la libération.
Avantage 2 Simple à implémenter, il est souvent utilisé dans les contextes distribués (SSP Chains [77]).
Inconvénient 1 Le problème avec ce genre de ramasse-miettes est le ralentissement de la gestion mémoire, dû à la manipulation de ces compteurs. En effet, pour les programmes manipulant un nombre important de pointeurs, le temps de mise à jour des compteurs peut devenir non-négligeable. Par exemple, si nous prenons le code suivant :
1 let x = ref object1 in
2 x := object2
Ici, le pointeur vers object1 est remplacé par celui de object2. Il faut mettre à jour le compteur du premier objet qui doit être lu puis décrémenté. Il faut ensuite tester si le compteur est nul, et si tel est le cas, il faut alors désallouer l’objet. Puis, il faut faire de même avec le nouvel objet object2, c’est-à-dire, lire son compteur, l’incrémenter et le mettre à jour. Ces mécanismes de gestion de compteurs impliquent une augmentation de la taille du code à produire, et du temps d’exécution.
Ramasse-miettes traversant / traçant
Un ramasse-miettes traversant, ou traçant, est une autre forme de gestion mémoire automatique consistant à considérer la mémoire comme un graphe. Il consiste à déterminer les objets pouvant être désalloués en parcourant les pointeurs depuis des racines et en marquant tous les objets atteignables depuis celles-ci, considérant alors tous les autres comme morts (car non atteignables depuis les racines). Une racine est un pointeur utilisé directement par le programme (mutateur). Les racines habituelles sont dans la pile, les variables statiques, les registres, etc. Ces types de ramasse-miettes sont les plus communs dans les langages de programmation modernes et il existe plusieurs implantations avec différents algorithmes que nous allons détailler dans la suite.
L’atteignabilité des objets
Le ramasse-miettes traversant parcourant le graphe mémoire, il faut comprendre ce que signifie pour un objet d’être vivant ou mort. Un objet est accessible, ou vivant, s’il est référencé par au moins une variable dans le programme, soit directement, soit à travers des références par d’autres objets vivants/accessibles. Les racines (dont nous avons vu la définition précédemment) représentent un ensemble d’objets considérés comme vivants.
Le ramasse-miettes à balayage
Les ramasse-miettes à balayage (mark and sweep en anglais) peuvent être modélisés à l’aide d’un coloriage des objets [67, 83, 94] qui indique l’état d’avancement d’un cycle du ramasse-miettes. Dans la version naïve de l’algorithme, on utilise deux couleurs, les objets en mémoire étant initialement colorés en blanc. En parcourant le graphe depuis les racines, le ramasse-miettes noircit tous les objets atteignables depuis celles-ci. En commençant par les racines, il itère tant qu’il existe des objets noirs avec des fils blancs. Quand aucun objet noir ne pointe plus vers un objet blanc, la phase de marquage est terminée. Cela se fait par un parcours récursif en profondeur du graphe mémoire. Le fait de noircir un objet en noir signifie donc que celui-ci est atteignable depuis une racine. Pour ne pas chercher tous les objets noirs pointant vers des objets blancs, il suffit, après avoir marqué un objet en noir, de parcourir ses fils blancs. L’inconvénient de cette version est que le parcours récursif utilise de la mémoire pendant le parcours des fils, pour se souvenir de l’objet que nous parcourons. Or, lorsque l’on déclenche le ramasse-miettes, c’est qu’il n’y a plus de mémoire. Dans la version à trois couleurs (blanc, gris et noir), le gris servira au ramasse-miettes pour les noeuds en cours de parcours. À chaque itération,pendant la phase de marquage, le ramasse-miettes va colorier les blocs blancs en gris, s’ils sont toujours vivants. Lorsque tous les fils immédiats d’un nœud gris auront été visités, celui-ci sera alors colorié en noir. Lorsqu’il n’y a plus d’objets gris, le marquage est fini. L’utilisation de la couleur grise permet de rendre le marquage incrémental, c’est-à-dire de le découper en phases plus courtes. En OCaml, il y a une quatrième couleur, le bleu, servant à identifier un bloc dans la freelist . Pour résumer :
• Bleu signifie que le bloc est dans la freelist.
• Blanc signifie que le bloc n’est pas encore visité par la phase de marquage.
• Gris signifie que le bloc a été visité par la phase de marquage, mais certains de ses fils ne l’ont pas encore été.
• Noir signifie que le bloc, ainsi que tous ses fils immédiats ont été visités par la phase de marquage.
Durant la phase de balayage, le ramasse-miettes va colorier les blocs noirs en blanc pour les préparer à la prochaine itération, et les blocs blancs en bleus (les blocs ne sont plus utiles, donc on les ajoute à la freelist).
Avantage 1 Un avantage indéniable des ramasse-miettes traversant, est que la libération de l’espace se fait d’un coup, en récupérant les objets blancs. Cela devient très utile lorsqu’il y a beaucoup d’objets alloués. Le ramasse-miettes ne déplaçant pas les objets, il n’y a pas besoin d’opérations en plus pour mettre à jour les pointeurs .
Avantage 2 Le ramasse-miettes est complet et ne demande que très d’espace supplémentaire par objet (juste les couleurs) .
|
Table des matières
Introduction
1 Introduction aux ramasse-miettes
1.1 Ramasse-miettes à comptage de références
1.1.1 Fonctionnement du ramasse-miettes à comptage de références
1.1.2 Les avantages et inconvénients du comptage de références
1.2 Ramasse-miettes traversant / traçant
1.2.1 L’atteignabilité des objets
1.2.2 Le ramasse-miettes à balayage
1.2.3 Le ramasse-miettes copiant
1.2.3.1 Fonctionnement de base du ramasse-miettes copiant
1.2.3.2 Avantages et inconvénients
1.2.4 Ramasse-Miettes à générations
1.2.5 La compaction
1.3 Ramasse-miettes Concurrent / Parallèle / Incrémental
1.4 Ramasse-miettes Conservatif
1.5 Stratégie d’allocation et gestion de la freelist
1.5.1 Stratégie first-fit
1.5.2 Stratégie next-fit
1.5.3 Stratégie best-fit
1.5.4 Stratégie worst-fit
1.5.5 Stratégie de malloc (binning)
1.5.5.1 Stratégie exact-fit
1.5.5.2 Stratégie par intervalles
1.6 Notions et définitions utiles
2 Gestion mémoire
2.1 Les différentes mémoires d’un programme
2.1.1 La pile
2.1.2 Les registres du processeur
2.1.3 Le segment de données
2.1.4 Le tas
2.2 Gestion mémoire en Swift et Objective-C
2.2.1 Swift, un langage de programmation pour smartphone
2.2.2 Le ramasse-miettes dans Swift
2.2.2.1 Ramasse-miettes à compteur de références automatique
2.2.2.2 Exemple de code en Swift
2.2.2.3 Traitement des valeurs cycliques
2.3 Gestion mémoire en Java
2.3.1 Java, langage de programmation orienté objet
2.3.2 Représentation mémoire des objets
2.3.2.1 Représentation des objets Java en 32 bits et 64 bits
2.3.2.2 Représentation des tableaux Java en 32 bits et 64 bits
2.3.2.3 Représentation des objets plus complexes en Java
2.3.3 Le ramasse-miettes à générations de Java
2.3.3.1 Les racines du ramasse-miettes de Java
2.3.3.2 Les zones mémoires
2.3.3.3 Le ramasse-miettes à générations
2.4 Gestion mémoire en Haskell/GHC
2.4.1 Haskell, langage de programmation fonctionnel pur
2.4.2 Représentation mémoire des valeurs en Haskell/GHC
2.5 Gestion mémoire en OCaml
2.5.1 OCaml, langage de programmation fonctionnel, impératif et orienté
objet
2.5.2 Représentation mémoire des données
2.5.3 Une unité d’allocation de mémoire (chunk)
2.5.3.1 Représentation des valeurs
2.5.3.2 Représentation des blocs
2.5.4 Le ramasse-miettes d’OCaml
2.5.4.1 Le tas mineur
2.5.4.2 Le tas majeur
2.5.4.3 La compaction
3 La gestion mémoire par régions
3.1 Définitions et rappels de la gestion mémoire par régions
3.2 Implantation des régions en C avec Cyclone
3.3 Implantation des régions en Java avec RTSJ
3.3.1 Spécificité de l’approche
3.3.2 L’algorithme utilisé
3.3.3 Exemple
3.4 Implantation des régions en ML
3.5 Inférence de régions en OCaml pour calculer la durée de vie des valeurs
4 Introduction aux outils de profiling
4.1 Outils de profiling pour la performance / optimisation de la mémoire
4.2 Profiler l’occupation mémoire
4.2.1 LeakBot, profiler l’augmentation mémoire
4.2.2 Cork, profiler l’augmentation mémoire à moindre coût
4.3 Outils de profiling sur la durée de vie des objets
4.3.1 Sleigh, détecter les fuites mémoire
4.3.2 Profiler les conteneurs
4.4 Assertions sur le ramasse-miettes
4.4.1 Assertion sur le tas avec DEAL
4.4.2 Framework d’assertion sur le tas avec LeakChaser
4.5 Outils de profiling en Scheme
4.5.1 Kprof, profiler la fréquences des allocations
4.5.2 Kbdb, un outil pour inspecter le tas
4.6 Outils de profiling en Haskell/GHC
4.6.1 Statistiques sur la runtime
4.6.2 Profiling du temps
4.6.3 Profiling de l’espace mémoire
4.7 Outils en OCaml
4.7.1 Profiling d’une application avec ocamlcp et ocamlprof
4.7.2 Profiling d’une application avec perf
4.7.3 Profiling d’une application avec ocamlviz
4.7.4 Échantillonneur d’allocations (Poor man’s profiler)
Conclusion
Télécharger le rapport complet
