Retour aux bases

From The Joel on Software Translation Project

Jump to: navigation, search

Sur ce site, nous avons passé beaucoup de temps à parler de gros sujets comme .Net contre Java, la stratégie XML, la conception de programmes, les stratégies efficaces, l'architecture, et plus encore. Tout ceci est en fait un gâteau fourré [une enveloppe, une carapace], en quelque sorte. Au plus haut niveau, vous avez la stratégie logicielle. Un peu plus bas, on pense aux architectures comme .NET, et encore plus bas, aux programmes individuels et aux logiciels de développement de produits, comme Java ou la plateforme Windows.

Descendez encore de quelques couches, s'il vous plait ! Les DLLs ? Les objets ? Les fonctions ? Non ! Encore plus bas ! À un certain point, vous pensez aux lignes de codes écrites dans un langage de programmation défini.

Ce n'est toujours pas un niveau assez bas. Aujourd'hui, je pense aux processeurs, ces petits bouts de silicone déplaçant des octets par ci par là. Imaginez que vous débutiez en programmation : écartez tout ce que vous avez appris sur la programmation, les logiciels, le management et retrouvez vous au plus bas niveau des fondamentaux de Von Neumann. Effacez J2EE de votre conscience pour un moment, et pensez octets !

Pourquoi faisons-nous ceci ? Parce que je pense qu'une des plus grosses erreurs que les gens font aux niveaux de développement les plus hauts vient d'une lacune ou d'une mauvaise compréhension de choses simples des niveaux plus bas. Vous avez construit un palais merveilleux, mais les fondations sont bancales : au lieu d'une solide dalle en béton, vous avez des débris. Le palais parait joli, mais de temps en temps la baignoire glisse sur le sol de la salle de bain, et vous n'avez aucune idée d'où cela peut venir.

Donc aujourd'hui, prenez une grande inspiration, et suivez moi, s'il vous plait, à travers un petit exercice dans lequel nous allons utiliser le langage C.

Souvenez-vous de la manière dont les chaînes de caractères fonctionnent en C : c'est une série d'octets terminée par le caractère NULL, qui à une valeur de 0. Ceci a 2 implications logiques :

1. Il n'y aucun moyen de connaître la fin de la chaîne (donc sa taille) sans se déplacer à l'intérieur de celle-ci jusqu'à trouver le caractère NULL. 2. Votre chaîne ne peut pas contenir le caractère NULL, donc vous ne pouvez pas stocker des données arbitraires venant d'une image JPEG (par exemple) dans une chaîne en C.

Pourquoi cela fonctionne comme ça ? Parce que le micro-processeur PDP-7, sur lequel UNIX et le langage C ont été inventés, a un type de chaîne de caractères ASCIZ, ce qui signifie "ASCII with a Z (zero) at the end.", ou encore "ASCII avec un 0 (zéro) à la fin."

Est-ce la seule manière de stocker une chaine de caractères ? Non. En fait, c'est même une des pires manières de le faire. Pour des programmes non triviaux : APIs, systèmes d'exploitation, bibliothèques de classes, vous devriez même évitez comme la peste les chaînes ASCIZ. Pourquoi ? Commençons par écrire une version du code pour strcat, la fonction C qui ajoute une chaîne à une autre.

void strcat( char* dest, char* src ) { while (*dest) dest++; while (*dest++ = *src++); }

Étudiez un peu le code et regardez ce qu'on fait :

On parcourt d'abord la première chaîne jusqu'à trouver le caractère de terminaison NULL, puis on parcourt la deuxième en copiant un caractère après l'autre dans la première.

Ce type de traitement des chaînes était assez bon pour Kernighan et Ritchie, mais il avait ses problèmes. En voici un : supposez que vous ayez un ensemble de noms à ajouter ensemble dans une grande chaîne.

char bigString[1000]; /* Je ne sais jamais quelle taille allouer... */ bigString[0] = '\0'; strcat(bigString, "John, "); strcat(bigString, "Paul, "); strcat(bigString, "George, "); strcat(bigString, "Joel ");

Cela fonctionne, non ? Oui, cela semble même propre et joli.

Quelles sont les performances ? Est-ce aussi rapide que ça pourrait l'être ? Si nous avions des millions de chaines à concaténer, serait-ce une bonne manière de le faire ?

Non. Ce code utilise l'algorithme de Toto le peintre. Qui est-il ? C'est la personne de cette blague :

Toto travaille comme peintre routier : il peint les lignes pointillées au milieu de la route. Le premier jour, il prit son bidon de peinture et peignit 300 mètres de route. "C'est très bien !" lui dit son patron, "Tu travailles très vite !", et il le paya un kopeck.

Le deuxième jour, Toto peignit 150 mètres de route. "Bon, ce n'est pas aussi bien que hier, mais tu travailles quand même bien : 150 mètres c'est déjà pas mal !", et il le paya 1 kopeck.

Le jour suivant, Toto peignit seulement 30 mètres de route. "Seulement 30 mètres !" cria le patron. C'est inacceptable ! Le premier jour, tu as peint 300 mètres de route, c'est dix fois moins ! Qu'est-ce qui se passe ?"

"Je ne peux pas faire mieux, patron. De jour en jour, je m'éloigne du bidon de peinture !"

Cette plaisanterie douteuse illustre exactement ce qui se passe lorsque vous utilisez strcat comme je viens juste de le faire. Comme la première partie de strcat a besoin de scanner la chaîne de destination à chaque fois pour chercher ce caractère de terminaison encore et encore, cette fonction est beaucoup plus lente qu'elle ne pourrait. Énormément de codes que vous utilisez tous les jours ont ce problème. Beaucoup de systèmes de fichiers sont implémentés de telle sorte que c'est une mauvaise idée de mettre trop de fichiers dans le même répertoire, parce que les performances chutent horriblement quand vous le faites. Essayer d'ouvrir la corbeille Windows lorsqu'elle déborde de fichiers, et vous verrez l'effet en action : cela met un temps fou à s'afficher, ce qui montre que le temps d'ouverture n'est pas linéaire au nombre de fichiers que la corbeille contient. Il doit y avoir une sorte d'algorithme de Toto le peintre quelque part la dessous. Quand quelque chose devrait avoir des performances linéaires alors qu'elle a en réalité des performances en n carrée, cherchez Toto le peintre qui se cache dans vos algorithme (il est souvent dans vos librairies). Mettre une suite de strcat ou bien strcat dans une boucle n'a pas tout a fait des performances en n carrée, mais en pratique c'est bien ce qui se passe.

Comment résoudre ce problème ? Quelques programmeurs malins C ont implémentés leur propre fonction mystrcat comme ceci :

char* mystrcat( char* dest, char* src ) { while (*dest) dest++; while (*dest++ = *src++); return --dest; }

Que fait-on ici ? Avec un très léger coût supplémentaire, on retourne un pointeur vers la fin de la nouvelle chaîne de caractères, plus longue. De cette manière, le code qui appelle cette fonction peut décider d'ajouter une autre chaîne, sans avoir à la parcourir à nouveau en entier :

char bigString[1000]; /* Je ne sais jamais quelle taille allouer... */ char *p = bigString; bigString[0] = '\0'; p = mystrcat(p,"John, "); p = mystrcat(p,"Paul, "); p = mystrcat(p,"George, "); p = mystrcat(p,"Joel ");

Ce code a bien sûr des performances linéaires, et non en n carrée, donc il ne souffre pas lorsque l'on a beaucoup de chaînes à concaténer.

Les développeurs de Pascal connaissaient ce problème et l'ont "réparé" en stockant la taille en octets de la chaîne dans le premier octet de celle-ci. Ces chaînes sont appelées les chaînes Pascal : elles peuvent contenir le caractère NULL et n'ont pas de caractère de terminaison. Parce qu'un octet peut seulement contenir un nombre entre 0 et 255, les chaînes Pascal sont limitées à 255 octets en longueur ; mais parce qu'elles n'ont pas de caractère de terminaison NULL, elles occupent la même taille mémoire que les chaînes ASCIZ. Ce qui est bien avec une chaîne Pascal, c'est que vous n'avez jamais besoin de faire une boucle pour connaitre sa taille. Vous avez seulement besoin d'une instruction assembleur, au lieu de la boucle complète. C'est beaucoup plus rapide.

L'ancien système d'exploitation Macintosh utilisait les chaînes Pascal partout. Beaucoup de programmeurs C utilisaient aussi les chaînes Pascal sur d'autres systèmes d'exploitation. Excel utilise les chaînes Pascal en interne : c'est pourquoi ses chaînes sont limitées à 255 caractères et c'est aussi une raison qui fait qu'Excel est étonnamment rapide. Pendant longtemps, lorsque vous vouliez utilisez une chaîne Pascal dans votre code C, vous deviez écrire :

char* str = "\006Hello!";

Oui, vous deviez compter les octets à la main, par vous-même et le mettre en dur dans le premier octet de votre chaîne. Les programmeurs plus feignants faisaient ainsi, avec un code plus lent :

char* str = "*Hello!"; str[0] = strlen(str) - 1;

Remarquez que dans ce cas, vous avez une chaîne terminée par le caractère NULL (le compilateur fait ça), mais aussi une chaîne Pascal. J'ai l'habitude de les appeler chaînes foireuses, parce que c'est plus simple que de dire chaîne Pascal terminée par le caractère NULL. Mais comme nous sommes polis, nous devons utiliser le long à rallonge.

J'ai omis une question importante tout à l'heure. Vous vous souvenez de cette ligne de code ?

char bigString[1000]; /* Je ne sais jamais quelle taille allouer... */

Comme nous nous intéressons aux octets, je n'aurais jamais dû l'ignorer. J'aurais dû faire correctement : calculer combien d'octets j'avais besoin et allouer la bonne quantité de mémoire.

N'aurais-je pas dû ?

Sinon, en lisant mon code, un hacker malin va voir que j'alloue 1000 octets en espérant que cela va être suffisant et il va trouver une astuce pour me faire concaténer une chaîne de 1100 octets dans mes 1000 octets de mémoire, provoquant un dépassement de mémoire écrivant dans la pile et changeant l'adresse de retour de la fonction, qui pointerait vers un code écrit par le hacker lui-même. C'est de ça qu’ils parlent en disant qu'un programme a une probabilité de dépassement de tampon. C'était la première cause de virus et autres vers bien avant que Microsoft Outlook rende le hacking suffisamment facile aux adolescents.

Ok, donc ces programmeurs sont des ânes : ils auraient dû calculer combien de mémoire ils devaient allouer.

Mais C ne rend PAS ceci facile pour vous. Revenons à mon exemple Beatles :

char bigString[1000]; /* Je ne sais jamais quelle taille allouer... */ char *p = bigString; bigString[0] = '\0'; p = mystrcat(p,"John, "); p = mystrcat(p,"Paul, "); p = mystrcat(p,"George, "); p = mystrcat(p,"Joel ");

Quelle taille allouer ? Essayons de la calculer de la bonne manière :

char* bigString; int i = 0; i = strlen("John, ") + strlen("Paul, ") + strlen("George, ") + strlen("Joel "); bigString = (char*) malloc (i + 1); /* n’oubliez pas la place pour la terminaison nulle! */ ...

C'est effrayant. Vous êtes surement déjà sur le point partir, mais je ne vous en veux pas : restez avec moi, parce que c’est là que ça devient vraiment intéressant !

Nous devons parcourir toutes les chaînes une première fois juste pour connaître leur taille, puis une deuxième fois pour faire la concaténation. Au moins, si nous avions utilisé les chaînes Pascal, l’opération strlen aurait été rapide. Peut-être pouvons nous écrire une version de strcat qui réalloue la mémoire pour nous ?

Ceci ouvre un autre sujet épineux : les allocations mémoires. Savez-vous comment malloc fonctionne ? Elle utilise une longue liste chaînée des blocs de mémoire disponibles, appelés espace libre. Quand vous utilisez malloc, cette liste est parcourue à la recherche d’un bloc de mémoire suffisamment grand pour satisfaire votre demande. Il coupe ensuite ce bloc de mémoire en deux -- le premier de la taille que vous avez demandé, l’autre avec les octets restants. Elle vous attribue le premier bloc et l’autre bloc est remis dans la liste chaînée (s’il n’est pas vide). Quand vous utilisez free, les blocs que vous libérez sont ajoutés à l’espace libre. Il se peut que l’espace libre soit séparé en petites parties, et que vous demandiez un bloc d’une taille supérieure à celle du plus grand bloc disponible. Malloc appelle alors une temporisation et commence à fouiller l’espace libre : trier les blocs, réunir les blocs adjacents de petites tailles. Cette opération prend 3 jours et demi. Le résultat final de ce joyeux bazar est que les performances de malloc ne sont jamais très bonnes (la liste chaînée est toujours parcourue) et parfois, malloc est même imprévisible et terriblement lente lors du nettoyage. (D’ailleurs, les performances des systèmes ramasse-miettes – garbage collector – sont équivalentes. Donc surprise surprise : toutes les personnes qui prétendent qu’utiliser un ramasse-miettes entraîne une perte de performances n’ont pas entièrement raison, étant donné que la plupart des implémentations de malloc impose cette même perte de performance, même moindre.)

Les programmeurs intelligents minimisent le risque potentiel perturbateur de malloc en allouant toujours des blocs d’une taille égale à une puissance de 2. Vous savez, 4 octets, 8 octets, 16 octets, 18446744073709551616 octets, etc. Pour des raisons intuitives pour n’importe qui ayant joué aux Lego, ceci diminue le taux de fragmentation désordonné de l’espace libre. Même s’il semble que l’on gâche de la place, il est également facile de remarquer que l’on en gâche jamais plus de 50%. Donc votre programme n’utilise pas plus du double de mémoire dont il a besoin, ce qui n’est pas si grave.

Imaginez que vous ayez écrit une fonction strcat intelligente qui réalloue le buffer de destination automatiquement. Mon professeur et mentor Stan Eisenstat suggère que lorsqu’on utilise realloc, on devrait toujours doubler la taille de la mémoire qui était allouer précédemment. Ce qui signifie que vous ne devez jamais faire appel à realloc plus de log n fois, ce qui a des performances assez bonnes, même pour de très longues chaînes, sans jamais gâcher plus de 50% de mémoire.

De toute façon, la vie devient de plus en plus désordonnée en bas dans le « monde-octet ». N’êtes-vous pas heureux de ne plus avoir besoin d’écrire de code en C ? Nous pouvons tous utiliser ces merveilleux langages comme Perl, Java, VB et XLST qui ne vous feront jamais réfléchir à tout ceci : ils s’occupent de tout en quelque sorte. Mais de temps à autre, une architecture plombant les performances refait surface et nous devons réfléchir s’il vaut mieux utiliser une classe String ou plutôt une classe StringBuilder, ou quelque chose du genre, car le compilateur n’est pas assez intelligent pour comprendre tout ce que l’on essaye d’accomplir et essaye de nous aider à ne pas écrire d’algorithmes inadapté comme celui de Toto le peintre. La semaine dernière, j’ai écrit qu’on ne pouvait pas implémenter la requête SQL SELECT auteurs FROM livres de manière rapide lorsqu’on stocke les données à l’aide de XML. Juste au cas où tout le monde n’aurait pas compris de quoi je parlais, et maintenant que j’ai parlé de processeurs tout au long de l’article, cette affirmation devrait avoir plus de sens.

Comment fait une base de données relationnelle pour implémenter SELECT auteurs FROM livres ? C’est simple : chaque ligne de chaque table (par exemple la table livres) a exactement la même longueur en octets, et chaque champ est à un rang fixe par rapport au début de la ligne. Donc par exemple, si chaque enregistrement dans la table livres fait 100 octets et que le champ auteur se situe au rang 23, alors les auteurs sont stockés aux rangs 23, 123, 223, 323, etc. Quel est le code pour se déplacer vers l’enregistrement suivant dans ce jeu de résultats ? Le voici :

pointer += 100

Une seule instruction processeur : rapiiiiiide !

Regardons maintenant la table livres stockée en XML :

<?xml blah blah> <books> <book> <title>UI Design for Programmers</title> <author>Joel Spolsky</author> </book> <book> <title>The Chop Suey Club</title> <author>Bruce Weber</author> </book> </books>

Question rapide : quel est le code pour se déplacer vers l’enregistrement suivant ?

Heu…

A ce moment, les bons programmeurs vont dire : ok, analysons le XML et stockons le dans un arbre en mémoire afin que l’on puisse le manipuler assez rapidement. La quantité de travail à effectuer par le processeur pour SELECT auteurs FROM livres vous ferait pleurer de toutes vos larmes. Comme chaque écrivain de compilateur sait, le lexer et l’analyseur sont les éléments les plus lents de la compilation. Devrais-je rajouter qu’on a besoin de manipuler beaucoup de chaînes de caractères, que nous avons découvert lentes, beaucoup d’allocations mémoires, que nous avons découvert lentes, étant donné que nous lisons et analysons la chaîne pour construire un arbre abstrait en mémoire ? Nous devons également supposer que nous avons assez de mémoire pour charger l’arbre XML en entier en mémoire. Avec une base de données relationnelle, les performances pour se déplacer vers l’enregistrement suivant sont fixes et en réalité, une seule instruction suffit. C’est entièrement dû à leur conception. Grâce aux plans du fichier en mémoire - mapped files – seules les pages utiles sont chargées depuis le disque. En utilisant XML, si vous pré-analyser, les performances pour se déplacer d’un enregistrement à l’autre sont fixes, mais le temps mort avant la recherche est énorme. Si vous ne faites pas la pré-analyse, les performances pour se déplacer d’un enregistrement à l’autre sont variables suivant la longueur des champs précédents, et cela nécessite quelques centaines d’instructions processeur.

Ce qui signifie pour moi que vous ne pouvez pas utiliser XML si vous avez besoin de performances avec beaucoup de données. Si vous n’avez pas beaucoup de données ou que ce que vous faites n’a pas besoin d’être rapide, XML est un format adapté. Et si vous voulez vraiment tirer le meilleur des deux solutions, vous devez vous débrouiller pour stocker des métadonnées à côté de votre XML, un peu comme pour la longueur des chaînes Pascal, qui vous informe où sont les données à l’intérieur du fichier de manière à éviter son analyse lors de la lecture. Bien entendu, vous ne pouvez ensuite plus utiliser un éditeur de texte pour modifier le fichier, car les métadonnées seraient corrompues, donc ce n’est plus vraiment du XML.

Pour ces 3 lecteurs courageux qui sont encore avec moi à ce point, j’espère que vous avez appris quelque chose ou au moins réfléchi à nouveau sur certains points. J’espère que réfléchir aux choses ennuyantes des premières années de l’informatique comme le fonctionnement de strcat et malloc vous ont donné de nouveaux outils pour réfléchir à un plus haut niveau, aux décisions stratégiques ou architecturales à prendre, par exemple lorsque vous voulez utiliser la technologie XML. Pour vos devoirs, pensez à pourquoi les puces Transmeta paraîtront toujours inertes. Ou à pourquoi les premières spécifications HTML pour la balise TABLE étaient si mal concues que les grands tableaux ne pouvaient pas être affichés rapidement pour des personnes en 56k. Ou pourquoi COM est si rapide, sauf quand on doit traverser une frontière de processus. Ou encore pourquoi les concepteurs du noyau NT ont mis le pilote graphique dans le noyau plutôt que dans l’espace utilisateur.

Toutes ces choses nécessitent de réfléchir au niveau des octets, et ont des répercussions sur les décisions que vous faites à pus haut niveau, quel que soit le type d’architecture ou de stratégie employés. C’est pourquoi je pense qu’il faut commencer à apprendre les bases aux étudiants en informatique de première année, en apprenant le C et en établissant ses débuts autour du processeur. Je suis physiquement dégoûté que tant de programmeurs pensent que Java est un bon langage d’introduction car il est « simple » et qu’on n’est pas perdu avec ces histoires de strcat / malloc, mais qu’on peut apprendre des choses cool avec l’orienté objet, et faire de gros programmes super modulaires. C’est un désastre pédagogique à retardement. Des générations de diplômés arrivent dans nos rangs et créent des algorithmes de Toto le peintre à droite à gauche sans même s’en rendre compte, car ils n’ont aucune idée de la difficulté fondamentale des chaînes de caractères à un très bas niveau, même si on ne pourrait jamais se l’imaginer juste en regardant un script Perl. Si vous voulez apprendre d’une bonne manière à quelqu’un, commencez-donc au plus bas niveau possible. C’est comme Karaté Kid : wax on, wax off, wax on, wax off, wax on wax off. Faites-le pendant 3 semaines et frapper du pied la tête de l’adversaire deviendra facile.

Personal tools