Gestion mémoire =============== L'allocation dynamique: ----------------------- Allocation statique impossible parce que les structures sont arbitrairement grandes ou arbtrairement compliquées. Modèle simple: allocation linéaire dans un gros bloc. Mais: si on veut pouvoir désallouer n'importe où, il apparaît des trous dans le bloc. D'où: la liste libre (un ensemble de blocs libres, souvent organisés en liste chaînée pour ne pas prndre de place supplémentaire). Allouer un bloc de taille N, c'est: - trouver un bloc libre de taille M >= N - l'enlever de la liste libre - si M > N, remettre un bloc de taille M-N dans la liste libre. Plusieurs stratégies: - first fit (le premier bloc de taille >= N convient) - best fit (prendre un bloc de taille minimale) Problème général: la fragmentation. Ex: beaucoup de blocs de taille 3 dans la liste libre. Le programme alloue beaucoup de blocs de taille 2. ==> de la mémoire gâchée ==> une recherche plus longue (si first fit) Solutions: compaction garder la liste libre triée par adresses -> collapsing des blocs libres (mais: déallocation plus coûteuse) Le GC (garbage collection, glanage de cellule): déallocation automatique ------------------------------------------------------------------------ Déallocation explicite non viable: trop dangereuse; trop difficile; parfois inefficace. Déallocation automatique: les blocs qui deviennent inaccessibles sont désalloués automatiquement. Accessibilité = il existe un chemin d'une des racines vers le bloc. Principales techniques: 1- Déallocation immédiate: dès que le bloc devient inaccessible 2- Déallocation différée: quand plus de mémoire disponible, on parcours tout le graphe mémoire; tous les blocs non accessibles sont alors récupérés. 3- Solutions intermédiaires: GC parallèle, GC incrémental. Le compte de référence: ---------------------- Chaque objet contient le nombre de pointeurs vers cet objet. Quand le compte tombe à zéro: on décrémente le compte de ses fils et on désalloue. Les fils peuvent à leur tour être désalloués. Mis à jour à chaque opération sur les pointeurs. Exple: let f x = let y = 1 :: x in tl(y) ... f l ... Problème: très coûteux si beaucoup d'opérations sur les pointeurs ne récupère pas les cycles. Marquage et balayage: --------------------- Un bit de "marque" par objet. Les objets sont alloués non marqués. Quand plus de mémoire: parcours du graphe mémoire en mettant la marque à 1. À la fin du parcours: tous les objets non marqués sont inaccessibles. Puis balayage de tous les objets du tas: - les objets non marqués sont placés dans la liste libre - les objets marqués sont démarqués Remarque: on peut garder la liste libre triée, et donc regrouper les objets libres adjacents -> fragmentation diminuée. Copie à deux demi-espaces: -------------------------- On partage le tas en deux moitiés. On alloue linéairement dans la première moitié. Quand plus de mémoire: on parcours le graphe mémoire en copiant les objets rencontrés dans l'autre semi-espace. Utilisation de "forwarding pointers" pour copier les objets une seule fois. À la fin de la copie: tous les objets de la première moitié sont inutilisés. On échange les deux moitiés. Remarque: fragmentation zéro, allocation toujours linéaire. Mais 50% de l'espace mémoire est perdu en permanence. Comment faire le parcours en espace constant: -------------------------------------------- Copie: l'algorithme de Cheney. On utilise la zone de destination comme une file d'attente de pointeurs à copier. Marquage: le marquage à 3 couleurs. Comparaison: ----------- Refcount M&S S&C Gâchis mémoire: 0-infini (frag) 0-infini (frag) 50% 40-50% (est) 40-50% (est) Opérations sur les pointeurs: surcoût normales normales Temps d'allocation: variable variable constant,faible Temps de récupération: cM cV + dT cV M: quantité d'objets morts pendant l'intervalle considéré V: quantité d'objets vivants à la fin de l'intervalle T: taille totale du tas Langages fonctionnels: beaucoup d'allocation, beaucoup d'objets morts. Se marient bien avec les GC à copie. Utilisation d'une génération: ---------------------------- Remarque: beaucoup d'objets meurent jeunes. (Peu de temps après avoir été alloués.) D'où l'idée de concentrer l'effort de récupération sur ces objets. On coupe le tas en deux générations: jeunes et vieux. On alloue linéairement dans la jeune génération. Quand elle est pleine: on fait un GC à copie de la jeune génération vers la vieille génération. (GC mineur.) Les pointeurs jeunes vers vieux ne sont pas suivis. La jeune génération est alors récupérée. Quand la vieille génération est pleine: on fait un GC majeur dedans (à copie ou à marquage). Une estimation du gain en efficacité: On suppose mortalité jeune 80%, vieille 30%, globale 50% taille jeune 64k, taille totale 1M Si pas de génération: on alloue 1M, on récupère 500k en temps 500 c on alloue 500k, on récupère 500k en temps 500 c ... Coût par k alloué en régime stationnaire: c Si une génération: on alloue 64k, on récupère 51.2k en temps 12.8 c on alloue 64k, on récupère 51.2k en temps 12.8 c ... Les GC majeurs: tous les 300k alloué en zone majeure, on récupère 300k en temps 700 c. Chaque GC mineur alloue 12.8 k dans la zone majeure => 1 GC majeur pour 23 GC mineurs. Temps moyen du GC mineur: 12.8 c + 1/23 * 700 c = 43.2 c Coût par k alloué: 43.2 c / 64 = 0.67 c Variantes: - davantage de générations - "tenuring policy" (on laisse les objets chez les jeunes jusqu'à ce qu'ils aient survécu à N GC mineurs) (Mais attention: davantage de copies.) Problème des pointeurs inverses: On a supposé qu'il n'y avait pas de pointeurs vieux -> jeunes. De tels pointeurs ne peuvent pas être créés lorsqu'on construit des structures. Ils peuvent apparaître si on modifie des structures pré-existantes. Donc: la modification physique d'un bloc doit tester si on est en train de créér un pointeur inverse, et si oui l'ajouter à une table de racines supplémentaires (the remembered set). D'où surcoût sur l'affectation (mais l'affectation est peu fréquente dans un langage fonctionnel). Aussi: ça se généralise à plusieurs générations (mais c'est compliqué). Exemples: -------- LeLisp/Caml V3.1 M&S + compaction sur chaînes et tableaux Bigloo/Camloo M&S simple, avec racines ambiguës Caml Light, Obj Caml 2 générations, GC majeur M&S incrémental SML/NJ ancien 2 générations, GC majeur S&C SML/NJ récent 5 générations, S&C