"Un bébé moineau
Saute avec curiosité
Pour regarder mon coup de pinceau"
Mizuhara Shuoshi (1892-1981)
"Placardée sur la porte d'entrée
La photo
Du chat qui n'est jamais revenu"
Midoriro no Mausu (la Souris Verte)
"J’ai manqué mon coup
La tête du clou
Est toute tordue"
Nakatsuka Ippekiro (1887-1946)
Hum, bon d'accord, on n'arrête pas de recycler le même dessin sur notre dossier, et alors ? Il faut dire que les titres de nos palpitants articles ne se prêtent pas facilement à une illustration imagée, surtout pour qui dessine avec le talent artistique d'un enfant de 3 ans ayant enfilé une bonne paire de moufles.
Bref, passons ces trivialités car on ouvre aujourd'hui un article excessivement important voire, nous n'avons pas peur de le dire, au moins aussi vital, indispensable et crucial que tous les autres mais même presque plus. Et, pour couronner le tout, il constitue un prolongement renversant à la fois de notre article sur l'algorithmique, non n'ayez pas peur, et de notre dernier article sur la base de données. Rappelez-vous, nous y avions énoncé, en effet, qu'il s'agissait autant que faire se peut de travailler en mémoire, et non à grand coup d'appels débridés à une base de données sympathique mais pas très véloce.
Et justement, aujourd'hui, nous regardons comment stocker efficacement des données en mémoire. Car la mémoire, certes, c'est rapide, mais il y a bien des manières de rendre un programme qui s'exécute entièrement dans cette belle zone nimbée aussi alerte qu'un hippopotame au sortir du déjeuner. Et, une fois de plus, c'est l'algorithmique qui va nous aider à faire la part des choses et à devenir le Programmeur Responsable de nos rêves.
Allez, n'introductions pas davantage car le fer est chaud et nous aussi, autant le battre sans tarder. En voiture ! Je précise que la voiture est à pédale, on ne va pas commencer à émettre des particules fines dans ce bel article aux éclats verdoyants d'automne, quand même. Aïe ! Ca y est, je me fais mordiller la cheville par les souris qui souhaitent qu'on en vienne au fait. On y va, on y va !
Et le menteur, mon cher Ouètsonne
Première révélation qui ne bouleversera pas ceux qui ont lu notre dernier article, nos données doivent être bien organisées pour s'adapter au contexte dans lequel on souhaite ensuite les récupérer. Ce n'est pas parce qu'on va travailler en mémoire que tout ce qu'on peut imaginer est efficace. A vrai dire, aucune structure de données n'est parfaite à tout point de vue, ça serait trop facile, c'est pourquoi il nous faut convoquer un peu nos connaissances en algorithmique et distinguer les opérations élémentaires suivantes :
- je souhaite accéder à une donnée précise dans mon gros paquet
- je souhaite ajouter une donnée à mon gros paquet
- je souhaite retirer une donnée à mon gros paquet
- je souhaite savoir si une valeur donnée appartient à mon gros paquet
- je souhaite énumérer toutes les données de mon gros paquet
Eh bien, c'est à peine pensable, mais il se trouve qu'AUCUNE, non, pas même une seule nulle part dans la galaxie, structure de données n'est parfaitement efficace pour toutes ces opérations. C'est bien la raison du pourquoi du fondement de cet article, en vérité, car il va nous falloir systématiquement faire des choix qui vont favoriser certaines opérations au détriment d'autres. C'est pourquoi tout Programmeur ResponsableTM se doit de connaître sur le bout des doigts une panoplie de structures de données, avec leurs avantages et leurs inconvénients, et d'être capable d'analyser son besoin pour choisir la plus adaptée au moment d'écrire ses milliers de lignes de code.
Le drame pour notre planète, mais qui en voit d'autres de toute manière, est que le choix systématique d'une structure de données pas du tout adaptée produit une pollution toute silencieuse : la machine ne crie pas, ne fume pas, le programme s'exécutera très bien, souvent même raisonnablement vite vu la puissance des processeurs, même ceux qui équipent les barrières de péage, donc personne ne s'aperçoit de ce gâchis constant d'instructions et de cycles machines, à part à la fin des fins l'ours polaire qui doit se déplacer de plusieurs dizaines de kilomètres supplémentaires chaque année pour trouver de la banquise.
Mais nous comptons bien que nos lecteurs aguerris et amateurs de gentilles souris vertes ne s'en laisseront pas conter et feront bien vite tous les efforts nécessaires, quand bien même ils ne recevraient pas de récompense du chef de l'Etat et d'acclamations de la foule en délire pour leur petite contribution stoïque à l'écologie numérique.
Or donc, comme nous le disions, aucune structure de données ne sera efficace pour toutes nos petites opérations élémentaires, et leur degré d'inefficacité se mesure grâce à la complexité propre à chacune de ces opérations, et là vous comprenez que vous avez bien fait de vous farcir notre bel article sur l'algorithmique sans vous assoupir.
Prenons par exemple le fait de trouver une donnée dans notre gros paquet de N données. Supposons que l'on a vraiment rangé tout ça en désordre complet, il nous faudra de l'ordre de N opérations (en général un peu moins, disons N/2 en moyenne, mais l'ordre de grandeur reste le même) pour aller retrouver notre petit copain, en gros on va les énumérer jusqu'à trouver la bonne. Si on a fait un petit effort, par exemple trié à l'avance nos données, on peut s'en sortir avec de l'ordre de log(N) opérations, ce qui est déjà nettement mieux, n'est-ce pas. Rappelons à toutes fins utiles, et sans frimer excessivement nos cours de maths de terminale, que log(10000)=4log(10), par exemple, soit au lieu de 10 000 essais, on en fait une dizaine environ. C'est mieux, non ? Mais toujours plus fort de café, si on a choisi une structure vraiment adaptée, on peut extraire notre donnée en une seule opération. Une seule ! Autrement dit ça vaut quand même bien le coup de choisir, non ?
Alors il se trouve que la plupart des programmeurs ne connaissent que le tableau, qui est une structure bien sympathique, mais qui offre précisément la complexité la moins bonne quand il s'agit d'aller chercher une valeur précise, même si elle a plein de qualités par ailleurs concernant les autres opérations. Bref, les tableaux sont certainement surutilisés (une souris me demande si ça existe, je suis sûr que l'Académie Française se hâtera de nous corriger, voire de l'inclure lors de sa prochaine session , si ça n'est pas le cas), et il serait bien temps de diversifier un peu notre palette en la matière.
Une petite remarque supplémentaire avant de décrire un peu le choix pléthorique au supermarché des structures de données : il faut savoir que toute structure de données n'est concrètement implémentée, à la fin des fins, qu'avec une combinaison de deux structures élémentaires, à savoir les tableaux et les listes chaînées. Couplée à quelques variables bien choisies, et parfois à des fonctions algorithmiques redoutables (comme les fonctions de hachage, par exemple), ces objets sympathiques nous permettent de construire des structures de données nettement plus complexes et adaptées à des situations très diverses. Cela dit, à moins d'utiliser un langage qui n'offre aucune structure de données un tant soit peu élaborée, et il y en a, ou d'avoir un besoin très spécifique en la matière, on aura rarement à implémenter soi-même ses propres structures de données complexes en partant de petits tableaux ou de listes chaînées.
Dernier point, enfin, la complexité en nombre d'opérations n'est pas nécessairement le seul critère qui entre en jeu quand il s'agit de choisir une structure de données, la place qu'elle occupe en mémoire peut également être décisive si vous stockez vraiment une grosse quantité de données. En règle générale, la différence n'est pas suffisamment importante d'une structure à l'autre pour que l'on prenne la peine de s'en soucier (les performances avant tout, n'est-ce pas), mais dans les situations extrêmes de beaucoup beaucoup d'octets à manipuler, on devra commencer à prendre des pincettes. Mais c'est également dans ce cas qu'on finira peut-être par développer ses propres structures de données aux petits oignons, si on en est là. Dans tous les cas, la structure de données qui occupe le moins de place en mémoire est le tableau, eh oui, bravo à lui. Comme quoi c'est tout de même un camarade bien gentil, malgré ses quelques défauts par ailleurs.
Tu les ranges tes données ?
Allez, il est temps de nous lancer dans un grand top 50, mais avec moins d'entrées au hit-parade quand même, des structures de données élues plus vertes de tous les temps par SourisMag. Bon, à vrai dire il existe tout un tas de structures très exotiques que nous garderons sous silence (arbres de plein de variétés, graphes, etc), pour nous contenter des structures les plus simples et les plus fréquemment utilisées. Nous allons également discuter des points forts et des points faibles de chacune, histoire de bien comprendre ce qui doit guider nos choix.
1 - Il est beau mon tableau
On commence par celui que nous connaissons tous, la structure universelle que même le VisualBasic de tonton doit savoir manipuler (enfin je dis ça, je m'avance peut-être), à savoir le tableau. Simple, élégant de bon, goût, le tableau est une structure formidable quand elle est implémentée par une vraie série de cases contigues en mémoire, jugez plutôt :
Plein d'avantages :
- c'est la structure la plus économe en mémoire
- c'est la structure la plus rapide à énumérer. Il ne faut qu'une seule opération pour passer d'un élément au suivant, et si en plus le tableau est tout entier dans le cache processeur ou dans la page de mémoire vive courante, on vole à la vitesse du vent
- c'est aussi la structure la plus efficace pour atteindre un élément donné si on connaît sa position : une seule opération, là encore, avec la même remarque que précédemment si le tableau est déjà chargé en mémoire
Mais des inconvénients :
- atteindre un élément dont on connaît la valeur, mais pas la position, demande d'énumérer tous les éléments. Coût de l'opération : de l'ordre de N instructions pour un tableau de taille N.
- c'est une des structures qui a le plus fort coût à l'insertion d'un élément. Si on l'ajoute à la fin et qu'on a alloué la place mémoire pour l'élément en trop, aucun problème. Par contre, ajouter un élément ailleurs nous oblige à décaler tous les éléments. Si jamais on a plus de place pour mettre un élément en plus, il faut allouer un tableau plus grand et tout recopier, bonjour le nombre d'opérations. Dans tous les cas l'insertion d'un élément coûte l'ordre de grandeur du nombre de valeurs dans le tableau.
- la suppression d'un élément est encore pire, sauf si là encore c'est le dernier. Dans tous les autres cas, c'est recopie de tous les éléments vers la gauche, sans possibilité de désallouer la mémoire inutilisée, sauf à tout recopier ailleurs, et là encore on paie environ N éléments en ordre de grandeur pour un tableau de taille N, sans compter la mémoire dépensée le temps de réaliser la copie. Eh oui ma bonne dame.
2- La liste déchaînée
Autre candidat bien sympathique parmi les structures toutes élémentaires, qu'on peut réimplémenter soi-même dans son salon sans risquer d'affreux plantages De La Mort, j'ai nommé la liste chaînée, sous vos applaudissements. Elle est toute simple : chaque élément contient une valeur, et un pointeur vers l'élément suivant. Facile, non ?
Des avantages à gogo :
- une efficacité redoutable pour énumérer tous les éléments, par petits sauts de puce de pointeur en pointeur. Pas tout à fait aussi véloce que le tableau, mais l'ordre de grandeur pour atteindre chaque élément depuis le précédent est d'une opération aussi.
- c'est une structure pas totalement, mais quand même relativement, efficace pour l'insertion d'un élément, où qu'il soit. En fait, il faudra compter de sauter jusqu'à l'élément où vous voulez ajouter un copain, donc plus il est loin du début, plus vous payez. Une seule instruction si vous insérez systématiquement en début de file, mais de l'ordre de N instructions si jamais vous allez n'importe où, c'est moins super.
- même chose pour la suppression, opération élémentaire, qui ne demande que de localiser l'élément en question.
Mais aussi des inconvénients quand même :
- on l'a déjà dit, atteindre un élément donné, par sa position comme par sa valeur, nécessite de suivre toute la liste, donc un ordre de grandeur de N opérations. Bof bof.
- cette structure occupe davantage de place en mémoire que le tableau, puisqu'en plus de la valeur on stocke l'adresse de l'élément suivant. Pas forcément énorme, mais ça peut commencer à saler l'addition si on a vraiment une grosse structure à maintenir.
Il existe une variante tout aussi rigolote, appelée la liste doublement chaînée, où, pour chaque élément, on stocke un pointeur vers l'élément précédent en plus du suivant. Dans ce cas on peut parcourir facilement la liste dans les deux sens, et insérer aussi facilement en début qu'en fin de liste. Pratique, mais là encore il y a un surcoût en mémoire.
3- En file indienne
Ah ah, ici on commence à rencontrer des structures un peu plus élaborées qui vont nous servir dans des situations très pratiques. Reconnaissons-le franchement, si on utilise des tableaux de manière courante, on ne va pas souvent sortir des listes chaînées de notre chapeau, sauf pour un exercice scolaire de programmation. Par contre la file, ça oui, on en voit partout et tout le temps. Dès qu'on fait communiquer deux machines/programmes/souris entre elles/eux, on a besoin d'une petite file : une structure où on empile d'un côté, et on dépile de l'autre, comme ça on prend toujours les éléments dans leur ordre d'arrivée, et on évite de mettre un joyeux désordre dans notre communication.
Alors, en fait la file en tant que telle peut être implémentée de plein de manières, mais si vous avez bien suivi ce qui précède, vous voyez que la plus efficace de loin est la liste doublement chaînée, puisque les opérations que l'on privilégie sont l'insertion en début et la suppression en fin de file. On peut s'en sortir aussi avec un tableau de taille variable, mais c'est à condition de connaître à l'avance la taille maximale du nombre d'éléménts qu'on peut mettre dans notre structure.
Pourquoi elle est gentille :
- insérer et supprimer un élément aussi bien en début qu'en fin de file ne nous coûte qu'une seule instruction machine, formidable.
- récupérer tous les éléments un à un à la suite est très efficace, même si ça n'est généralement pas pour cela qu'on choisit une file.
Pourquoi elle est méchante :
- l'insertion ou la suppression en milieu de file est totalement prohibée. Elle serait théoriquement possible, mais avec un surcoût non négligeable, et de toute manière c'est en contradiction flagrante avec la finalité même de la structure, donc souvent cette opération n'est même pas disponible.
- aller inspecter la file pour voir si une valeur précise y est stockée demande d'énumérer tous les éléments, donc de l'ordre de N instructions pour une file de taille N. Et là encore, cette possibilité n'est pas toujours offerte à l'utilisateur sympathique.
4- Remonté comme une pile
Autre structure à inclure dans sa petite besace, largement sous-estimée et trop peu utilisée à notre goût, la pile est votre amie dès lors qu'il s'agit ranger nos éléments pour ressortir toujours du tas le dernier déposé. Notez bien la différence avec la file, qui elle prend toujours l'élément le plus ancien encore disponible.
Par ailleurs, la pile est absolument indispensable dès que vous faites des parcours d'arbres en profondeur, ce que vous faites, si si, dès que vous parcourez une arborescence de fichiers. Si vous ne vous en rendez pas compte la plupart du temps, c'est que vous utilisez la pile d'appels de votre langage de programmation, en lieu et place de la votre propre.
Disons le franchement, elle regorge de qualités :
- l'insertion et la récupération d'un élément est simplissime, une seule minuscule instruction
- c'est une structure excessivement économe en mémoire, en tout cas quand elle est correctement implémentée
- l'énumération (enfin, le dépilement) de tous les objets dans la pile est très efficace
Mais elle a quand même quelques défauts :
- impensable d'insérer ou de retirer un élément ailleurs qu'au début, sans quoi elle perd tout son intérêt
- savoir si une valeur est présente dans la pile nécessite d'en énumérer tous les éléments un à un, donc de l'ordre de N instructions. Et encore, ceci n'est pas toujours possible sans dépiler puis réempiler tout le bazar.
5- Tout en gros tas
Moins connu du grand public, et très honnêtement assez difficile à trouver sur le marché aux structures incluses dans les librairies courantes, le tas est pourtant bien pratique dans certaines situations. Il faut dire aussi que son nom n'est pas très vendeur non plus, aux souris vertes on l'appelle souvent le Gros Tas, même si on a beaucoup d'affection pour lui.
Alors, le tas sert à entasser, eh oui, toutes nos petites données en leur accolant un poids. Plus la donnée pèse lourd, plus elle part au fond du tas. Et on peut ainsi récupérer en une seule instruction la donnée la plus légère, puis la suivante, etc. Il existe une variante également où c'est le plus lourd que l'on ressort à chaque fois ; bon, même si ça n'est pas disponible il suffit d'affecter l'opposé de nos poids pour que ça fasse la même chose, remarquez bien.
Une formidablitude non démentie :
- il faut une seule opération pour obtenir le minimum (ou le maximum) de notre structure. Attention cependant, comme l'insertion d'un élément n'est pas la plus économe, construire un tas juste pour trouver le minimum de N valeurs est moins efficace que d'énumérer simplement les valeurs en gardant la plus petite.
- l'énumération des valeurs successives ne coûte rien, et en prime on vous les renvoie dans l'ordre croissant des poids. Le tas fait donc partie des structures optimales pour trier des données, et est utilisé par un certain nombre d'algorithmes de tri
- voir si une valeur existe dans le tas est très rapide, de l'ordre de log(N) opérations pour un tas de taille N.
- l'insertion et la suppression d'une valeur est également relativement efficace, de l'ordre de log(N) opérations
Mais pas que non plus :
- ben, en fait, on pourrait remettre ici tous les points précédents : insertion, suppression, lecture d'une valeur, sont efficaces, c'est vrai, mais il existe des structures bien plus rapides pour chacune des ces opérations. Le tas est plutôt bon partout, mais il n'excelle nulle part.
En pratique, il n'y a pas de mystère, si le tas n'est pas utilisé de manière courante, c'est qu'il ne se démarquera de ses petits copains que dans des cas très spécifiques, et que pour l'écrasante majorité des cas il y aura toujours une structure plus adaptée. Mais ça reste souvent un bon deuxième choix si aucune implémentation d'une structure que vous souhaitiez n'est disponible.
6- En finesse mais à la hache
Nous avons gardé le meilleur pour la fin. Il existe toute une classe de structures qui s'appuient sur des fonctions de hachage pour vous offrir une efficacité redoutable sur certaines opérations très courantes. La structure algorithmique sous-jacente s'appelle une table de hachage, mais elle permet d'implémenter dictionnaires, ensembles, tableaux associatifs et sans doute encore d'autres structures que nous oublions au passage.
Le principe est toujours le même : grâce aux fameuses fonctions de hachage sorties du cerveau brumeux de mathématiciens déchaînés, nous sommes en mesure d'accéder à une valeur donnée de notre ensemble en une seule opération. Oui, une seule, et ceci quel que soit l'élément et quelle que soit la taille de votre ensemble. Vous pouvez vous pincer, vous ne rêvez pas. Alors, tout ceci n'a pas que des avantages, ça serait trop facile, et il va falloir payer du gros coût à la sortie sur certaines opérations. En général, nous utilisons ces structures pour stocker des ensembles (clé, valeur), on donne la clé et on retrouve la valeur en une seule opération rapide comme l'éclair.
Que de délices nous attendent :
- nous venons de le dire, une seule opération pour l'accès à un élément donné en connaissant uniquement sa clé associée.
- une seule opération aussi pour insérer et supprimer une clé de notre paquet
- une seule opération pour répondre à la question : ma clé est-elle dans mon gros tas ? Du coup c'est très utile pour dédoublonner des valeurs dans un ensemble : on pose tout dans notre dictionnaire / ensemble / table de hachage, et à l'arrivée l'ensemble des clés ne contient que des valeurs uniques.
Mais attention l'addition est parfois salée :
- commençons tout de suite par ce qui fâche, à savoir l'énumération des éléments qui est tout simplement misérable. Nous trouvons ici de très loin la structure la plus lente pour énumérer les éléments les uns après les autres, un phénomène dont bien peu de programmeurs semblent avoir conscience, qui mettent tout ce qu'ils ont sous la main dans une table de hachage uniquement pour la parcourir entièrement à la fin. Croyez-moi, la différence avec un tableau est tout simplement abyssale si la structure est de grande taille.
- la structure demande plus de place en mémoire que la plupart des autres structures élémentaires énumérées ici. Bon, rien d'incroyable non plus, surtout si elle est bien implémentée, mais dans certains langages où ça n'est pas le cas, la place occupée en mémoire peut devenir assez vite gênante.
- les opérations élémentaires demandent en moyenne une instruction, c'est vrai, mais il s'agit tout de même d'un calcul de hash qui est nettement plus qu'un simple accès à un élément dans un tableau par sa position. Donc une GROSSE instruction, quand même, et qui sollicite gentiment le processeur au passage.
- dernier point, si les hashs sont mal distribués, c'est-à-dire si la fonction de hachage utilisée ne se comporte pas très bien avec les données que vous stockez, eh bien là les ennuis commencent sérieusement et la structure devient aussi gracile qu'un éléphant cherchant à faire du skateboard. Le risque est minime tant que la taille de la structure reste limitée, mais si vous commencez à y jeter plusieurs millions d'entrées, il va sans doute falloir y regarder de plus près sur la manière dont la structure est implémentée dans les coulisses.
Mais cette dernière remarque est finalement valable pour n'importe quelle structure : si vous dépassez une taille critique, disons plusieurs centaines de milliers d'entrées, vous pourrez rarement vous contenter de l'implémentation standard à portée de main, et il vous faudra sans doute, soit la paramétrer finement, soit en modifier le code, soit carrément repartir de zéro pour écrire la votre à la place.
Soigner son langage
Bien, nous en avons terminé de notre petit tour d'horizon des plus belles structures de données de la collection automne-hiver de l'année. Nous ne pouvons que vous inviter à découvrir par vous-même tous les autres trésors que nous n'avons pas abordés ici, sachant que plus vous choisirez une structure adaptée à vos besoins, plus votre code sera performant et votre impact en mémoire ou en stockage limité.
Mais, en pratique, on ne peut pas non plus occuper son temps éveillé à implémenter des structures de données, donc on est bien souvent contraint de s'appuyer sur celles qui sont disponibles de base dans le langage de programmation que nous utilisons. Arrivé à ce point de notre réflexion, on se rendra vite compte que tous les langages ne sont pas équivalents, non non non, et que s'il faut un critère pour les discriminer, au-delà des Super Benchmarks De La Mort qui vous démontrent que X lave plus blanc car il calcule des fractales à la vitesse du son, on sera bien inspiré de regarder si ledit langage possède des structures de données bien implémentées et adaptées à toutes les situations.
En général, quel que soit le langage utilisé, on essaiera d'avoir au minimum deux structures toujours sous le coude : un bon vieux tableau, ou liste, pour les traitements qui demandent des énumérations fréquentes, et une table de hachage, ou équivalent, pour tout ce qui demande des accès par valeur, ou du dédoublonnage. Muni de ces deux outils de base, et en choisissant systématiquement celui qui va le mieux, nous sommes déjà en mesure d'écrire du code quasi optimal dans toutes les situations courantes. Si en plus, on a gardé en tête les conseils de notre dernier article, et qu'au lieu de spammer notre base de données, on monte en mémoire une structure qui nous permet de les interroger de la manière la plus efficace possible tout au long de l'exécution de notre programme, on aura largement mérité d'encadrer notre diplôme de Programmeur Responsable (TM) au-dessus du canapé de notre salon.
Mais t'arrêtes donc de recopier, toi ?
Une dernière remarque, et après promis on s'arrête là pour aujourd'hui, car les souris piétinent d'impatience à mes côtés, il y a une chose qu'il faut absolument contrôler lorsque vous utilisez un langage de programmation, c'est la manière dont sont passés les paramètres des fonctions. Il y a en fait deux possibilités :
- les paramètres sont passés par référence, c'est-à-dire qu'on vous donne un pointeur sur l'objet que vous aviez passé, et que votre fonction peut le modifier à loisir, vous récupérez ensuite l'objet modifié
- les paramètres sont passés par valeur, autrement dit vous en avez une copie toute neuve dans votre fonction que vous pouvez triturer à l'envi, l'appelant n'en saura rien, le coquin.
Aucune des deux méthodes n'est universellement satisfaisante, car parfois vous aimeriez bien que la fonction appelée n'aille pas mettre en bazar tout ce que vous lui envoyez, et en même temps si vous avez une structure géante, vous ne voulez pas forcément la recopier entièrement de fonction en fonction.
"Dans son écorce
Le chêne
Garde la mémoire de mon regard"
Midoriro no Mausu (la Souris Verte)
"Soleil de printemps
Boîte aux lettres repeinte
Dégoulinades jusqu’à terre"
Hara Sekitei (1889-1951)
Ah mais tout de même. Enfin un article dont nos amis programmeurs comprennent le titre et savent de quoi-t-on va parler, voilà qui ne serait pas du luxe. C'est que tout développeur ne connaît que ça, la base de données. Il l'appelle, la rappelle, lui envoie des petits coucous, prend de ses nouvelles, discute avec elle du temps qu'il fait, et ce toute la journée durant. Eh bien, une fois de plus, c'est malheureux de toujours en arriver là, les souris vertes doivent mettre les pieds dans le plat et mettre le holà à cette idylle apparemment parfaitement innocente. La manipulation sans précaution de notre gentille base de données est LA cause noumero uno (una ?) d'inefficacité des programmes dans le monde, et donc une alliée bien malgré elle du gaspillage informatique à tous les étages, et du réchauffement climatique qui s'ensuit.
Il va donc nous falloir renverser la tête pour arrêter de marcher sur la vapeur, et ce même si cette si cette image vous laisse aussi perplexe que moi. Essayons de comprendre pourquoi la base de données n'est pas le formidable couteau suisse du programmeur que l'on imagine souvent, mais plutôt sa version masse d'armes de vingt kilos à pommeau incrusté que l'on maniera avec la délicatesse d'Hercule, en fin de journée et un peu pressé de finir son onzième travail sur douze.
A la vitesse de l'électron, mais avec un boulet au pied
La base de données est, c'est bien connu, la meilleure manière en programmation de ranger ses petites affaires et de les avoir sous le coude instantanément. La meilleure, vraiment ? Commençons par un petit rappel salutaire directement recopié, sans reversement aux ayants droits, de notre magnifique dossier sur les grandeurs numériques, en se remémorant les ordres de grandeur de latence suivants :
- depuis le cache processeur : 0, négligeable, rien du tout, niente, le processeur travaille directement avec son petit cache qu'il garde auprès de lui
- depuis la mémoire vive (ou RAM pour les intimes) : 10 ns, soit 0,00001ms
- depuis un disque dur SSD : 0,01 à 0,1ms
- depuis un disque dur à plateau : 1 à 10ms
- à travers un appel réseau : de 0,1 à 1ms si on est sur un réseau local très performant, de l'ordre de 30ms si l'on est à travers des connexions distantes
Mais pourquoi donc rappeler tout cela, me demande une souris qui gratte ses mignonnes petites oreilles de consternation ? C'est qu'il nous faut nous poser la question : où est notre base de données là-dedans ? En fait, elle est à cheval sur trois catégories : elle travaille pour partie en mémoire vive (grâce à un cache plus ou moins performant), pour une grosse partie depuis le disque dur, mais il faut lui ajouter une petite latence réseau, car elle est en général déportée sur une autre machine et, quand ça n'est pas le cas, toute la couche des appels réseaux est utilisée quand même pour des appels en local.
Alors, nous voyons tout de suite le problème d'appeler sans arrêt notre base de données : à chaque appel, on paye quelques millisecondes, voire beaucoup plus quand on fait des requêtes maousse costaudes, et des millisecondes qui s'entassent, eh bien ça fait des secondes, puis finalement des heures, voire des jours. Alors que l'on voit tout de suite que si nos données étaient toutes en mémoire, eh bien on irait constamment à la vitesse de la mémoire vive, soit 100 000 fois plus vite, excusez du peu. L'idéal étant même de toujours s'arranger pour travailler dans le cache processeur, là on tombe carrément dans la vitesse intersidérale absolue, sauf que c'est bien difficile à réaliser en pratique si l'on ne programme pas dans un langage qui permet de gérer finement l'allocation mémoire, et désormais très peu de langages modernes l'autorisent, vu que c'est aussi une source d'erreurs fatales et de cataclysmes sans nom. Cela dit, nous ne sommes tout de même pas obligés de nous mettre les mêmes contraintes pour notre petit programme que pour la séquence de lancement d'une fusée en temps réel, donc déjà si on arrête de spammer la base de données à tout va et qu'on sollicite un peu plus la mémoire vive de notre machine on sera bien content.
Bien entendu, il n'y a pas équivalence stricte entre ces méthodes de stockage de données : les données en mémoire vive ou dans un cache processeur sont volatiles, alors que dans votre base de données, elles seront persistantes (enfin si tout va bien). Remarquons d'ailleurs la tendance bien navrante de certains programmeurs à utiliser leur base de données comme fourre-tout pour y mettre des données qui n'ont aucun intérêt à être stockées, comme des résultats de calculs intermédiaires, des caches temporaires, etc, tout ça parce que c'est bien facile de tout ranger dans le gros placard que de travailler un peu à gérer des structures de données en mémoire. Résultat des courses, c'est la double peine : vous perdez en performance à appeler sans cesse votre base de données, et en plus vous consommez du stockage inutilement pour des données qui peuvent être recalculées à la demande.
Il existe aujourd'hui des bases de données non relationnelles fringantes, ou encore des systèmes de cache clé-valeur excessivement plus performants qu'une base de données traditionnelle, comme Redis pour n'en citer qu'un, et qui seront bien utiles dans certains contextes, comme le fait de partager certaines données volatiles entre plusieurs serveurs. Cela dit, même quand ils travaillent exclusivement en mémoire, bravo à eux, ils resteront toujours nettement moins performants que l'utilisation de la mémoire vive au sein même de la zone d'exécution de votre propre code : vous évitez ainsi de payer une petite (ou grosse) latence réseau, ainsi que tout un traitement lié au protocole de transfert aller-retour à la base et son interprétation dans le langage de programmation que vous êtes en train d'utiliser, bref un tas de choses qui ne coûtent pas bien cher si on se sert de sa base de données avec parcimonie, mais qui commencent à chiffrer sévèrement dès qu'on fait tourner plusieurs milliers de fois par seconde notre petit code.
Allô, la base de données ?
Bien bien, on vous a compris, les souris, on jette la base de données à la poubelle et on ne fait plus que du code en mémoire, merci et salut. Attendez ! Ne partez pas si vite, on ne va pas se quitter sur un malentendu pareil : il n'est pas question de mettre toute notre application en mémoire partout et tout le temps, sinon on a remplacé une nuisance par une autre. De toute manière c'est tout simplement impossible, car vous avez sans doute remarqué qu'on est loin de pouvoir mettre autant de mémoire vive sur une machine qu'elle n'a de stockage disponible. Si votre application consomme 100 Go sur disque dur, vous aurez bien du mal à obtenir l'équivalent pour passer l'ensemble en mémoire vive, même à considérer que ça prendrait strictement la même place, ce qui n'est pas vrai (le stockage en mémoire consomme toujours légèrement plus de place que la donnée elle-même).
Bon, donc on ne jette pas notre base de données à la poubelle, au contraire même : c'est tout de même une technologie super robuste pour stocker des données de manière persistante et garantir leur intégrité, beaucoup mieux que s'il fallait faire ça soi-même par des bouts de fichiers, ou tout autre technique tordue qui vous viendrait à l'esprit. Simplement on va s'interdire d'appeler trop souvent notre base de données, pour ne pas payer le coût prohibitif de l'appel à chaque fois qu'on a besoin d'une donnée. Imaginez un peu un code de 100 lignes qui appelle la base de données toutes les 10 lignes pour faire un traitement. Disons qu'on perd 1ms à chaque appel, ce qui est déjà très optimiste, donc notre code s'exécute en 10ms. Si on a réussi à faire tous ces appels en une fois, on ne paye déjà plus que 1ms, on a déjà gagné un facteur 10. Mais si en plus on a anticipé, et préparé dans une autre section de code ces données et qu'elles sont déjà en mémoire, là notre bout de code s'exécute de manière quasi instantanée.
Alors évidemment, ceci supppose d'arrêter de manier à la truelle un concept de programmation particulièrement en vogue, mais qui est une ineptie en terme de performances : l'absence de contexte. Je fais ma petite fonction qui s'occupe de son petit calcul et ne sait rien du reste du monde, mieux encore, je l'appelle au travers d'une API comme ça c'est super étanche, elle ne sait rien de mon application, c'est l'insouciance bienheureuse de l'ignorance béate. Ces principes sont très sains appliqués à une certaine échelle, pour éviter ce qu'il faut bien appeler un sac de noeud géant qui constitue malheureusement la réalité sordide de bien des projets informatiques ayant dérivé dans la nuit, mais ils sont franchement délétères quand on les reporte à une échelle microscopique, puisque l'on va finir par payer un coût exhobitant à chaque micro-étape de notre programme.
Aux Souris Vertes, nous avons un Principe Majeur s'agissant de structurer correctement son application : toute partie du code qui utilise un tant soit peu intensément les données doit pouvoir disposer de la logique complète de la manière dont elles sont structurées, et même la guider : on stocke toujours ses données de la manière la plus adéquate pour les reprendre ensuite, et pas selon un schéma préétabli qui fait beau sur le papier, mais qui est totalement impraticable pour la machine. C'est quand même elle qui travaille à la fin, non mais.
Résumons en quelques savants conseils percutants notre manière de gérer la base de données en Programmeur Responsable :
- mutualiser autant que possible les appels successifs, quitte à organiser le code autrement. Par exemple, je dois récupérer la date de naissance d'un utilisateur à partir de son login à chaque fois qu'il se connecte. Soit je fais un appel à chaque connexion, soit je charge une fois pour toute en mémoire une relation
- maîtriser la logique globale de l'accès aux données dans l'application, en particulier savoir quelles parties de code écrivent ou lisent dans la base de données pour ne pas faire de traitements redondants ou des appels inutiles, pour des données que vous auriez pu vous repasser d'un bout à l'autre du code.
- stocker les données sous la forme la plus adaptée à la manière dont elles sont ensuite extraites. Le paradigme des bases de données relationnelles, je-mets-tout-à-plat-et-après-je-fais-30-jointures-si-j'ai-besoin, est en ce sens désastreux. En principe, on sait toujours comment une donnée est récupérée (toute seule ou en groupe, filtrée selon un attribut particulier, etc) et il faut en tenir compte dans la manière de structurer son stockage en base. Rappelons également que la création d'index à tout va quand on se rend compte que les performances sont abyssales, généralement lorsque l'on requête sur un ou des attributs que l'on n'avait pas anticipés, n'est pas une méthode viable : chaque nouvel index créé peut dépasser la taille des données brutes stockées, ce qui fait qu'on consomme du stockage à gogo sans vraiment corriger le problème, qui se trouve, comme presque toujours, au sein de la logique que déroule notre code.
Voilà, nous n'allons pas multiplier les conseils aujourd'hui, le principe est simple : on contrôle finement les appels à notre base de données, de manière à en faire le moins souvent possible. Et une fois qu'on a pris nos petites habitudes, on peut les appliquer même quand il n'y a pas forcément un enjeu important de performances, car il n'y a pas de raison de gaspiller des ressources machine, même quand la différence n'est pas perceptible à l'oeil nu. Bien sûr, on cherchera toujours un équilibre entre la complexité du code à écrire et à maintenir, et le gain réel en performance.
"Ciel d'hiver -
La neige répond
A l'appel du rocher"
Midoriro no Mausu (la Souris Verte)