Ecologie Informatique

L’univers/mémoire a quelques conséquences sur la flore et la faune qu’il faut bien assimiler :

1. Il est facile de faire des clones parfaits de n’importe quelle donnée A à n’importe quelle distance de l’original, mais il faut faire attention à ne pas en écraser une autre B. Comme seul le contexte permet de savoir ce qu’une donnée représente, la prochaine fois que le processeur lira la donnée B, il n’aura aucun moyen de savoir qu’il lit un bout de A en lieu et place, et un orage virtuel tombera sur la tête d’un utilisateur désemparé dans les microsecondes suivantes.
2. Il faut donc veiller à faire naître les données à un endroit non occupé de la mémoire, ce qui implique de savoir quelles portions de mémoire sont occupées.
3. Lorsqu’une donnée n’est plus utilisée, elle « meurt ». Mais pour pouvoir réutiliser la mémoire que la donnée occupait, il faut déclarer le décès. C’est en général le rôle du programme qui a créé la donnée. S’il ne le fait pas, la mémoire occupée par le zombie de la donnée ne pourra pas être réutilisée et cette « fuite de mémoire » (« memory leak ») réduira peu à peu la mémoire disponible.
4. Le plus dur reste à faire : informer la famille. Il faut en effet faire en sorte que plus aucun pointeur vers feu la donnée ne soit utilisée par la suite, sous peine d’assister à des tentatives de résurrection, voire des actes nécrophages, touts deux punis par des pluies de cafards mortels. Le Les Pointeur aborde divers rites funéraires informatiques.
5. On peut éventuellement déplacer une donnée en mémoire par une variante douloureuse de la téléportation : on clone, puis on tue l’original. Cette « réallocation » pose donc les même problèmes qu’une la mort d’une donnée : la famille doit être informée de la nouvelle adresse.
6. Cependant, la plupart des données sont sédentaires et passent toute leur vie à la même adresse. Rien à signaler tant qu’elles ne changent pas de taille, mais si elles grossissent, le spectre de l’écrasement réapparaît, et si elles rétrécissent, c’est celui du cimetière. Mais la conséquence la plus importante de la croissance d’un être dans un monde linéaire, c’est qu’il peut être forcé de ne plus être contigu car sa croissance peut être limitée par un voisin inamovible que la crainte de la foudre nous interdit d’écraser.

La mémoire a donc besoin d’anges gardiens, qui peuvent être plus ou moins prévenants, mais il faut au minimum attribuer aux données une place en mémoire, et recycler ces places lorsque les données sont détruites. C’est le rôle des « allocateurs de mémoire », que nous allons décrire au paragraphe suivant. Plus loin nous aborderons d’autres anges comme les « ramasse-miettes », plus puissants mais plus lourds aussi, et volant donc moins vite.

Allocation de mémoire

Ici nous avons un petit problème : nous n’avons encore pas parlé de structures de données ou d’objets, donc nous ne pouvons pas décrire les allocateurs de mémoire en termes biologico-informatiques. Pour l’instant nous allons continuer à en parler comme d’anges abstraits. Leur nature réelle, ou plutôt virtuelle, deviendra claire plus tard.

Qu’ils gèrent de la mémoire de travail ou de stockage sur disque, le principe des allocateurs est le même. Nous allons commencer par décrire un allocateur très simple, mais très souvent utilisé pour gérer la mémoire centrale.

1. L’ange possède une liste ou chaque ligne décrit un bloc de mémoire libre grâce à 2 colonnes répertoriant :
   1. L’adresse de début du bloc
   2. Sa taille
2. Au début on initialise la liste avec une seule ligne, décrivant toute la mémoire comme étant libre.
3. n programme qui veut créer une donnée appelle l’allocateur en spécifiant la taille de la donnée. L’allocateur cherche dans la liste le premier bloc assez grand pour contenir la donnée. On donne l’adresse mentionnée dans le bloc au programme pour qu’il y crée la donnée et on rétrécit le descripteur de bloc libre en modifiant son adresse de départ et sa taille.
4. Lorsque le programme veut détruire une donnée, il passe son adresse et sa taille à l’allocateur, ou plutôt au « dé-allocateur » qui est le côté obscur de la force. Là, une méthode fréquente consiste à chercher dans la liste s’il existe 1, voire 2 blocs libres contigus à celui qu’on libère. Si oui, on fusionne tous ces blocs en un seul, si non on insère le bloc libéré à la liste de manière à ce qu’elle reste triée par adresse.

Les Pointeurs

Nous avons commencé à entrevoir l’importance de données de type « pointeur », qui contiennent l’adresse en mémoire d’une autre donnée. L’allocateur de mémoire fournit un pointeur lorsque l’on crée une donnée, et restitue la mémoire lorsqu’on lui « rend » le pointeur, qu’il peut éventuellement effacer (par convention un pointeur sur l’adresse mémoire 0 est considéré comme nul, ou ne pointant sur rien)

Un monde dangereux

Mais comme le pointeur est lui-même une donnée, il peut être copié en de multiples exemplaires et ça, le dé-allocateur décrit plus haut ne peut pas le savoir. Donc, lorsqu’une donnée est détruite ou déplacée, le dé-allocateur « simple » ne peut pas « avertir la famille », c’est le rôle du programme qui a créé et copié les pointeurs de veiller à ce qu’ils suivent la donnée à sa nouvelle adresse, ou dans la tombe.

Une autre opération risquée est la modification de la donnée via un pointeur : les autres possesseurs de pointeurs n’en seront pas avertis. Si ce comportement est celui désiré, par exemple dans une base de donnée, tout va bien. Mais si les autres pointeurs devaient conserver l’ancienne valeur, il faut obliger le modificateur à cloner la donnée pour ses propres besoins.

L’expérience prouve que tous ces risques sont réels : on peut dire que plus de 90% des bugs, crashs et autres plantages de votre ordinateur préféré sont dus à des pointeurs invalides, c’est-à-dire pointant sur des données qui ne sont plus à l’adresse indiquée, ou plus celles qui étaient attendues. Et encore, ceci est un résultat remarquable atteint grâce aux subtilités qui vont suivre, sans quoi ce taux atteindrait 99%. Si vous pensez qu’améliorer la fiabilité de 9% n’est pas vital, refaites le calcul, on parle de 1000%, 10 fois plus de bugs !

Un dernier problème ne cause pas de crash, et c’est presque dommage car il est très difficile à détecter est la « fuite de mémoire » mentionnée plus haut.

Référence = sécurité

On appelle référence un pointeur constant, qui ne peut donc que pointer sur une donnée immobile, ou du moins fixe pendant la durée de vie de la référence.

Il n’y a en réalité aucun moyen matériel d’empêcher la modification du pointeur, ce sont les langages de programmation qui s’assurent que la référence n’est pas modifiée, et qu’elle n’est utilisée que pendant la durée de vie de la donnée.

L’usage de références est donc très limité, mais simple et très sur. Moralité : les utiliser de préférences au pointeurs chaque fois que c’est possible, en particulier pour le passage de paramètres, comme on l’a vu au paragraphe « Les » du chapitre 3.

Les poignées.

Une poignée (« handle ») est une référence à un pointeur (variable) sur la donnée. C’est peut-être la « structure de données » la plus simple que l’on puisse imaginer, mais elle est déjà très, pour ne pas dire vachement, utile. Lorsqu’un nouveau pointeur sur la donnée est requis, il suffit d’utiliser une copie de la référence. On se retrouve donc avec N références au même pointeur, qu’il suffit de modifier lorsque la donnée bouge ou meurt. Il n’y a dès lors plus aucun risque que la famille parle à un cadavre. Par contre, il subsiste un risque d’incinérer une donnée vivante si l’un des membres de la famille trop pressé déclare son décès à l’ange dé-allocateur.

Les pointeurs malins

La traduction de « smart pointers » par « pointeurs intelligents » et un peu fausse, et très prétentieuse. « Malin » semble plus correct. L’idée est de placer chaque pointeur sous la responsabilité d’une autorité de tutelle responsable de lui face à la famille. Ainsi, les risques mentionnés plus haut pourraient être évités.

Le tuteur possessif.

Le tuteur le plus simple est celui qui possèderait le pointeur pour lui tout seul et le transfèrerait à un autre tuteur qui le demanderait en clonant/tuant son protégé. On s’assurerait ainsi qu’il n’existe qu’un seul pointeur vers une donnée donnée (sic…), le dernier propriétaire s’occupant des obsèques. Bien que très restrictive, cette politique simple peut être très utile dans des structures de données comme les conteneurs. Patience…

Le comptage de références

Une tutelle plus subtile est le comptage de référence, qui combine les avantages des pointeurs malins précédents, mais surtout évite la zombification en garantissant qu’une donnée ne survive pas au dernier membre de sa famille : elle est tuée au moment ou le dernier pointeur sur elle est détruit. Ce comportement civique est très apprécié pour éviter les fuites de mémoire, et donc très utilisé dans les systèmes d’exploitation ainsi que dans de nombreux langages modernes. L’architecture « COM » de Microsoft, intensivement utilisée dans Windows utilise le comptage de référence, tout comme « .NET », qui ne donne plus accès aux pointeurs « bêtes ».

L’intérêt du comptage de référence réside dans sa simplicité : il suffit d’ajouter un compteur à une poignée. Chaque fois qu’une poignée est copiée, on incrémente le compteur. Chaque fois qu’une poignée n’est plus utilisée, on le décrémente et si elle atteint 0, hop, on détruit la donnée que plus personne n’utilise.

Des vaches en string.

« cow », l’acronyme anglais de« copy on write », désigne le fait de forcer un pointeur à cloner sa donnée à une nouvelle adresse avant de la modifier. Pourquoi ne pas directement effectuer une copie de la donnée chaque fois que l’on copie le pointeur, me direz-vous ?

Parce qu’on risque de gaspiller de la mémoire avec des copies multiples de la même donnée, alors que de pointer sur la même depuis de nombreux endroits l’économise et accélère la copie. La politique « cow » est souvent utilisée pour manipuler les chaînes de caractères (« strings »), souvent de manière cachée. Par exemple en Visual Basic, si on fait :

Dim a ,b as String ' définit 2 chaînes de caractère
a=''hello''
b=a ' ici la chaîne n'est pas copiée, mais b contient un nouveau pointeur sur 'hello'
a=a+'' world'' 'avant d'ajouter le mot, « cow » copier le contenu de a

Prenons un exemple en considérant le fichier de la sécurité sociale d’un pays de 50 millions d’habitants. Dans les bases de données, on s’arrange pour que chaque donnée occupe la même taille pour y accéder plus rapidement et surtout pour éviter de devoir déplacer beaucoup d’information sur le disque dur, ce qui est très lent.

Considérons d’abord que chaque habitant ait un nom et prénom pouvant atteindre 50 caractères chacun (« Charles-Edouard Philibert Dubois-De la Rochefoucault»). En les stockant directement, les noms et prénoms prendraient 5 Gigabytes à eux seuls. C’est trop pour pouvoir résider en mémoire centrale sur une machine 32bits, et il faudrait plusieurs secondes pour chercher un nom dans cette longue liste sur disque.

Imaginons maintenant qu’il n’existe que 36′234 prénoms et 61′765 patronymes distincts, et que nous les stockions dans deux tables de 65535 éléments au maximum : ceci permet de n’utiliser que 4 nombres de 16 bits par habitant, en procédant ainsi : dans le premier nombre, on met le numéro de la ligne de la table des prénoms correspondant au premier prénom, par exemple 2341 pour « Charles-Edouard », puis « 23548» pour « Philibert » et de procéder de même pour le nom de famille et le nom d’alliance. Ceci ne prend que 8 octets par habitant, soit 800 Mo seulement, soit au total 12 fois moins que précédemment.

Et les pointeurs dans tout ça ? Et bien ces nombres de 16 bits en sont, conceptuellement : ils pointent vers une donnée (nom ou prénom) stockée ailleurs. Si maintenant un monsieur «Paul Michel» informe la sécu que son nom et son prénom ont été intervertis, et qu’il est en fait une femme prénommée «Michèle», nom de famille « Paule », il suffit de modifier les 2 nombres-pointeurs !