Dans ce second article, je vous propose de découvrir quelques techniques permettant de collecter la mémoire de manière progressive (incrémentale). L'application directe de celles-ci consiste à réduire les délais induits par la collecte. Cet article se veut, comme son prédécesseur, une introduction au sujet, et ne seront abordés que les aspects principaux, sans entrer dans les considérations plus fines.
Je tiens à remercier Dark-Side (désolé de ne pouvoir faire une référence correctement, celle-ci refuse de se laisser inscrire dans le code du tuto) pour l'adaptation du code LaTeX d'origine en zCode.
Dans notre premier article, nous avons étudié un collecteur basique appelé mark&sweep. Celui-ci avait pour propriété d'effectuer l'intégralité du travail en un seul passage ininterrompu. Durant son exécution, le programme est en arrêt, incapable de poursuivre, et si la quantité de mémoire à traverser est large, le temps nécessaire à l'opération peut devenir considérable. Pour certaines applications telles que l'exécution de scripts, cette restriction ne constitue pas un réel problème. Dans des environnements plus sérieux, il peut être nécessaire de mitiger cet impact ponctuel sur les performances des programmes.
Un internaute acceptera plus facilement d'attendre une seconde de plus durant le chargement d'une page, pourvu que ce phénomène soit ponctuel, qu'un joueur, au moment décisif, durant une partie de jeu en ligne, même si cela ne devait arriver qu'une fois toutes les dix minutes.
Cet article vous propose de découvrir des techniques permettant un traitement progressif, fragmenté dans le temps, de la mémoire. Une autre approche, très prisée des systèmes généralistes, est la collecte partielle que j'espère pouvoir aborder dans un article à venir.
L'algorithme du premier article se présentait naturellement de manière récursive. Les appels récursifs ayant recours à la pile automatique (que la mémoire soit ou non réellement gérée sous la forme d'une pile, le mécanisme des appels et des retours peut être assimilé à une pile), il n'est pas aisé d'interrompre l'opération de recyclage et donc de la fragmenter. La première étape dans l'obtention d'un mark&sweep progressif consiste donc à rendre notre algorithme itératif.
L'approche directe consiste à coder une pile manuellement, de sorte à imiter la récurrence. Ainsi, à chaque interruption, la position précise où nous nous arrêtons, dans le processus de recyclage, est inscrite au-dessus de notre pile. Si nous analysons des paires de valeurs, comme il est courant en Lisp, pour chaque objet analysé, il y a deux positions possibles : au niveau du premier ou du second champ (une fois que le premier a été traité). La situation se complique pour des objets plus larges ou hétérogènes.
Une alternative est de conserver, à la place de la liste des objets déjà traversés (et par lesquels il faut repasser pour compléter le processus), celle des objets à traverser (le lecteur averti comprendra sans mal qu'il s'agit d'un parcours en surface). Ainsi, chaque objet est analysé en une unique opération, à l'issue de laquelle la liste est augmentée des références contenues dans celui-ci.
Dans cette situation, il est possible de remplacer la pile par une file. Les avantages de ce changement sont imperceptibles à ce stade et peuvent paraître subtils, même après lecture de l'article. De ce fait, nous n'aborderons pas le sujet. Toutefois, par la suite, nous ne considèrerons que cette stratégie et ne ferons référence qu'à une file d'objets à traverser. Les informations sont toutefois transposables sans trop de difficultés aux autres modèles.
Représentation des ensembles d'objets
À ce stade, notre algorithme de réclamation de la mémoire nécessite lui-même une structure de données potentiellement conséquente pour effectuer correctement son travail. Au maximum, nous avons besoin d'autant de places dans la file qu'il y a d'objets dans le système.
Une première solution consiste à inclure, dans chaque objet, les champs nécessaires. Cette configuration est avantageuse si la représentation des ensembles d'objets libres et occupés prend déjà la forme d'une liste double (voyez à ce propos le premier article). Les mêmes champs pourraient alors être réutilisés sans coût ajouté.
D'autres organisations existent, par exemple : une table de bits (bitmap) indiquant le statut, occupé ou libre, de chaque bloc.
Division de la mémoire
Dans le cas général, supposons que l'espace disponible pour la file est borné. Selon la taille choisie, cette limite pourrait n'être jamais atteinte, en pratique. Cependant, nous ne pouvons négliger le cas malheureux où notre liste deviendrait insuffisante.
Il s'agit de sacrifier du temps pour épargner de la place en mémoire. Pour ce faire, nous employons une approximation de notre file d'attente. Il faut garder à l'esprit que celle-ci n'opère que dans le pire des cas : lorsque la pile est pleine.
L'approximation la plus simple consiste à parcourir alors toute la mémoire linéairement à la recherche d'objets à traiter. Avec cette approche, il est important de pouvoir distinguer l'état d'un objet (vierge, à traiter ou marqué). Le troisième état devient ainsi apparent, tandis que l'algorithme originellement étudié déguisait celui-ci derrière la pile de récurrence. L'inconvénient évident de ce premier essai est qu'il est inefficace ; il requiert une traversée intégrale de l'ensemble des objets parmi lesquels seuls quelques-uns sont réellement utilisés.
Il est possible, sur le même modèle, d'affiner notre approximation en scindant la mémoire dont nous avons la responsabilité en régions de tailles raisonnables, appelées cartes. La contrepartie est que chaque sous-ensemble doit pouvoir être marqué pour traitement, à la façon des objets individuels. Cela implique un coût supplémentaire d'un bit par carte. Dans la situation où la file est pleine, il s'agirait alors de marquer l'objet et la carte lui correspondant pour traitement ultérieur. Nous pourrions penser que nous n'avons en rien avancé par rapport aux algorithmes de la section précédente. En effet, à nouveau, nous sommes confrontés à un besoin de mémoire supplémentaire pour mener à bien notre mission. L'astuce consiste à allouer celle-ci par avance : pour chaque carte en notre possession, nous réservons un bit de mémoire à cet usage exclusif. Il s'agit alors de choisir la taille des cartes adroitement, afin d'obtenir le meilleur compromis, pour notre usage.
Considérations techniques (supplément) : dans le cas général, sans avoir recours à des techniques plus proches de la machine visée, il n'est pas aisé d'identifier la carte associée à un objet (donc, à une adresse). Le principe de base de cette association réside dans un calcul d'adresse : en divisant la mémoire en cartes contigües, adjacentes, de tailles régulières, il est possible, avec un peu d'arithmétique sur les adresses, d'obtenir directement la carte à partir du pointeur. Malheureusement, les opérations requises ne sont pas toutes disponibles en ANSI-C. Seules les additions sont possibles, ce qui est insuffisant pour notre usage. Néanmoins, il est possible, quoique pénible, en utilisant des informations additionnelles (donc, davantage de mémoire), d'obtenir des résultats équivalents. Le programmeur C averti remarquera tout de suite que si la mémoire à notre disposition est constituée d'un seul bloc contigu, nous pouvons utiliser le décalage entre l'adresse analysée et la base du bloc afin d'effectuer nos calculs. La situation se complique dès lors que l'on a plusieurs régions séparées à gérer. Je laisse au lecteur l'initiative d'élaborer d'autres solutions, s'il le désire.
Un mark&sweep amélioré
Dans cette section, nous avons opéré des modifications nécessaires à l'introduction de l'aspect progressif dans notre algorithme initial. Bien qu'il ne soit en rien plus progressif, notre méthode n'en est pas moins devenue un mark&sweep tout à fait correct. Un tel algorithme est acceptable pour les environnements pouvant tolérer les interruptions engendrées.
Contrairement à ce qui pourrait être suggéré par la direction de cet article, de tels cas de figure ne sont pas rares : une tâche de fond n'ayant aucune interaction avec l'utilisateur, n'importe quel programme pouvant intégrer le recyclage dans une de ses phases d'attente préexistante (chargement, etc.), ou lorsque une réactivité occasionnellement diminuée ne constitue pas un souci majeur. L'éditeur Emacs, avec lequel j'écris ces lignes, utilise un procédé similaire à celui que nous avons mis en place, afin de récupérer la mémoire utilisée en interne par son propre langage de script : Emacs Lisp.
Pointeurs inversés (supplément) : en réalité, un véritable mark&sweep utilisé tel quel se préoccupe rarement de gérer une pile ou une file d'objets à traiter. L'exécution continue permet de détourner temporairement la mémoire en cours d'analyse. Une pile est alors directement construite sur les emplacements des pointeurs d'origines : durant l'analyse, chaque objet atteint est modifié pour contenir, à la place d'une référence vers un objet à traiter, une référence de retour vers le dernier objet marqué. Ainsi, le passage dans un sens crée la pile, dans l'autre, la défait et restaure l'organisation initiale.
À partir de l'algorithme précédent, il paraît simple d'imaginer un fragment du processus de recyclage : en rendant les structures utilisées (file, marqueurs de cartes) permanentes, il nous est possible de reprendre le travail exactement là où nous l'avions interrompu. On appelle cycle la séquence de fragments correspondant à une exécution du mécanisme non progressif correspondant, ici, le mark&sweep de la section précédente. Un cycle correspond donc, dans notre cas, à un mark&sweep complet. Ceci serait suffisant si le programme demeurait dans le même état entre deux incréments. Or, il est probable que, durant cet intervalle, des objets soient créés et d'autres modifiés.
Le cas des objets nouvellement créés peut être aisément résolu en effectuant une approximation conservatrice : il suffit de les considérer marqués. Ils seront ainsi analysés par le cycle suivant.
Celui des objets modifiés est autrement plus délicat. Trois situations se présentent.
Si l'objet modifié est vierge de toute marque, il n'a pas encore été atteint par le collecteur, durant le cycle actuel. Le changement est donc absolument invisible pour celui-ci.
Si l'objet modifié est à traiter, le collecteur n'en a pas encore analysé le contenu. Ce dernier peut donc être altéré sans problème.
Le problème provient de la dernière éventualité, lorsque l'objet a déjà été traité et marqué durant le cycle en cours. La modification, si elle inscrit une nouvelle référence différente de la précédente, peut perturber l'analyse.
Plaçons-nous dans le cas non trivial. L'ancienne référence a été supprimée et pourrait donc, si aucun autre objet accessible ne la contient, devenir inaccessible. Cela est toutefois acceptable, car une telle erreur n'affecte pas la préservation des données utiles. La nouvelle référence est davantage problématique : elle introduit un nouvel objet à analyser. Il est possible, en effet, qu'elle devienne, d'ici la fin de la collecte, la seule référence à l'objet qui lui est associé, si toutes les autres références au même objet, accessibles, sont supprimées. Avec notre algorithme naïf, nous serions incapables de déterminer son existence et la phase de nettoyage supprimerait par erreur un objet susceptible d'être encore utilisé par le programme.
Une solution : la barrière à l'écriture
Une solution au problème évoqué ci-dessus est d'intercepter tous les accès en écriture aux objets de la troisième catégorie. Une telle technique porte le nom de barrière à l'écriture : c'est un mécanisme qui se glisse entre le programme qui souhaite agir sur la mémoire et le composant responsable de celle-ci, au cours d'un accès en écriture.
Le rôle de la barrière est de signaler au collecteur la nécessité d'analyser à nouveau certains objets. Il existe plusieurs stratégies pour organiser cette information.
Si nous optons pour une représentation sous forme de listes, il suffit à la barrière d'ajouter l'objet à réexaminer dans la liste appropriée.
Si la séparation en cartes est effective, celle-ci suggère naturellement une approche basée sur les mêmes cartes. Si la barrière marque la carte associée (ainsi que l'objet en question), l'algorithme finira par examiner la carte, à un moment ou un autre, lorsque sa file sera vide ; nous aurons alors l'effet attendu : une seconde analyse de l'objet.
Un algorithme final
Nous pouvons maintenant rassembler les divers éléments requis et élaborer un algorithme final basé, par exemple, sur l'organisation en cartes. L'algorithme est constitué des deux phases d'analyse et de nettoyage décrites dans l'article précédent, auxquelles s'ajoutent une file, un ensemble de marqueurs de cartes et une barrière à l'écriture.
Durant la phase d'analyse :
chaque fragment de cycle traite un nombre défini d'objets de la file, ces traitements sont susceptibles d'allonger celle-ci ;
si la file se remplit, la carte appropriée est marquée ;
si la file se vide, une carte est lue et le résultat du parcours des éléments de la carte est placé dans la file ;
si la file est vide et qu'aucune carte n'est marquée, l'analyse est terminée.
Durant la phase de nettoyage, chaque fragment libère un nombre défini d'objets. Le fonctionnement exact dépend de la représentation des ensembles d'objets (libres, occupés, etc.).
À chaque opération d'écriture, la barrière est activée et marque la carte correspondante, si nécessaire (iI est également possible de marquer tout le temps la carte).
Il existe maintes variations sur le thème d'un mark&sweep progressif. Selon les choix d'implantation effectués, tels que la représentation des ensembles d'objets, la taille de la pile, ou encore la taille des cartes, les coûts et les performances seront différents. Tous ces paramètres dépendent largement des programmes supportés et de leur usage de la mémoire. Un programme écrit en style fonctionnel aura moins de chance d'activer la barrière d'écriture fréquemment, mais sera très demandant sur les routines d'allocation et produira une grande quantité d'objets, dont une partie de déchets non négligeable.
Il existe de même plusieurs manières d'écrire la barrière, privilégiant certaines opérations et pénalisant d'autres. Il s'agit d'adapter le système à l'usage.
Pour clore le sujet des performances, il est à noter que l'ordre et la fréquence des collectes ont leur importance. Analyser des objets sujets à des changements fréquents est un très mauvais calcul, causant à la fois un usage plus intensif de la barrière, et un nouvel examen systématique. De manière similaire, des collectes trop fréquentes peuvent s'avérer infructueuses (aucun recyclage possible) et des collectes trop espacées peuvent entraîner une plus grande fragmentation, mais surtout un remplissage accéléré de la mémoire disponible. Le contrôle de ces critères relève toutefois d'une optimisation heuristique dynamique et dépasse de loin le cadre de cette série d'articles d'introduction.
Efficacité
Un souci majeur du recyclage progressif est l'efficacité : il s'agit de collecter suffisamment de mémoire en un temps raisonnable, afin de ne pas trop l'encombrer. Concrètement, cela signifie qu'un cycle doit être achevé avant que la mémoire restante ne soit épuisée. Si notre système contrôle l'intégralité de la mémoire, une estimation peut être faite à partir de la quantité de mémoire libre au début du cycle. Dans le cas contraire, nous devons nous contenter d'un paramètre arbitraire ou d'une approximation.
Il est également possible de coupler le collecteur progressif avec un collecteur classique, pouvant être invoqué par décision du programme (par exemple, en cas de nécessité, lorsque la mémoire vient à manquer ou simplement par souci d'optimisation, à des instants choisis).
Les techniques présentées au long de cet article permettent de concevoir un système de gestion automatique de la mémoire capable de supporter certaines contraintes de temps d'interruption. Le domaine d'application d'un tel composant est vaste ; les programmes qui requièrent une bonne réactivité ne sont pas rares. Les logiciels multimédias, tels que les jeux, constituent de bons exemples.
Seul un collecteur progressif est capable d'offrir des garanties intéressantes, contribuant à la fluidité des programmes. Couplé à un collecteur continu, il peut satisfaire les besoins d'environnements hétérogènes ou plus exigeants.