Understanding the Machine

1Penser bas niveau, écrire haut niveau#

Le livre refuse le faux choix entre code haut niveau élégant et code bas niveau rapide. Le grand code, selon la définition de Hyde, est « un logiciel écrit selon un ensemble cohérent et hiérarchisé de bonnes caractéristiques » (p. 8) : on choisit ses priorités, puis on les tient avec constance. Un seul attribut ne se négocie pas : ne pas gaspiller sans raison.

Les inefficacités qui font mal sont rarement volontaires. Elles viennent d'un écart entre ce que le développeur imagine et ce que la machine fait réellement :

// vous IMAGINEZ : "diviser par 8, c'est une opération"
y = x / 8;     // une DIVISION entière : souvent 20 à 40 cycles CPU

// la machine, et donc le bon code, préfère :
y = x >> 3;    // un DÉCALAGE de 3 bits : 1 cycle (pour un entier non signé)

Corrigez le modèle mental, et le code s'améliore sans une ligne d'assembleur.

2Un nombre n'est pas sa représentation#

« Un nombre est un concept intangible et abstrait » (p. 10) : ce qui vit en mémoire est toujours une représentation choisie. L'hexadécimal, par exemple, n'est pas vraiment un autre système de numération : c'est du binaire avec des lunettes, un chiffre pour quatre bits.

Et la représentation a des pièges bien concrets. Deux exemples avec le complément à deux, le format universel des entiers signés :

• son asymétrie est intégrée : sur 8 bits, la plage va de -128 à +127. Donc +128 n'existe pas, et l'opposé de -128 donne… -128 ;
• dans ce format, le bit le plus à gauche porte le signe : -1 sur 8 bits s'écrit 11111111. Pour l'élargir à 16 bits, il faut répéter ce bit de signe à gauche (11111111 11111111, toujours -1). Remplissez de zéros à la place, et 00000000 11111111 se lit désormais +255 : le nombre négatif est devenu positif en silence.

Et ce ne sont pas des cas d'école. En 2014, YouTube est passé à un compteur de vues 64 bits parce que Gangnam Style dépassait 2 147 483 647 vues, le maximum d'un entier signé 32 bits. Le même plafond guette tout id auto-incrémenté déclaré INT dans votre base, et c'est lui qui fixe le bug de l'an 2038 : les timestamps Unix stockés sur 32 bits débordent le 19 janvier 2038. Quand vous choisissez un type de colonne, vous choisissez une représentation, donc un plafond.

3Le flottant est une approximation, avec des règles de survie#

Un flottant est stocké comme une notation scientifique : 1.23e3 veut dire 1,23 × 10³. La partie chiffres (1,23) s'appelle la mantisse, la partie échelle (e3) l'exposant. Détail crucial : la mantisse a un nombre de chiffres fixe. Tout ce qui ne rentre pas est jeté.

C'est pour ça que 0.1 + 0.2 ne vaut pas 0.3 : en binaire, 0,1 et 0,2 sont des fractions périodiques, comme 1/3 en décimal. La mantisse stocke une approximation tronquée, et les erreurs s'additionnent.

Le mécanisme se voit le mieux en décimal, avec une mantisse de 3 chiffres. Pour ajouter 1.00e0 à 1.23e3, il faut d'abord aligner les exposants : la petite valeur glisse hors de la fenêtre des 3 chiffres. Résultat : 1.23e3, inchangé. L'addition n'a silencieusement rien fait.

Hyde en tire des règles de survie (ch. 4). L'absolue : « ne comparez jamais deux valeurs flottantes pour voir si elles sont égales » (p. 70) ; testez abs(a - b) <= epsilon à la place. Les autres :

• additionnez d'abord les valeurs de grandeur comparable : l'ordre d'évaluation change le résultat ;
• soustraire deux valeurs très proches détruit la précision (l'annulation) ;
• un float 32 bits porte environ 6,5 chiffres décimaux ; un double 64 bits environ 14,5. C'est peu, sur une chaîne de calculs ;
• pour l'argent : des entiers en centimes, jamais des flottants.

4Les opérations sur les bits sont des outils, pas de la magie#

Décor minimal d'abord. Dans la machine, tout nombre est une rangée de bits, des cases qui valent 0 ou 1. Chaque case pèse une puissance de 2 (en partant de la droite : 1, 2, 4, 8, 16…), et le nombre est la somme des cases allumées : 0010 1011, c'est 32 + 8 + 2 + 1 = 43. Les opérateurs bit à bit travaillent colonne par colonne, comme une addition posée : AND (&) garde un 1 seulement si les deux cases en ont un, OR (|) allume la case dès qu'une des deux est à 1, XOR (^) l'allume si les deux diffèrent. Et c'est natif : le CPU fait ça en une seule instruction, l'opération la moins chère qui existe.

Le chapitre 3 se lit ensuite comme une boîte à outils. AND masque des bits, OR les force, XOR les bascule, et ces motifs marchent à l'identique en JS, PHP et Python :

// pair/impair sans modulo
if (n & 1) { /* impair */ }

// index de buffer circulaire, si la taille est une puissance de 2
i = (i + 1) & (taille - 1);   // remplace (i + 1) % taille

// ASCII : majuscule et minuscule ne diffèrent que d'un bit (le bit 5)
'A' | 0x20  // → 'a'
'a' & 0x5F  // → 'A'

La leçon plus profonde porte sur la conception de formats compacts : rangez les champs du plus significatif au moins significatif (année, mois, jour), et deux dates se comparent avec une simple comparaison d'entiers. La représentation fait le travail que le code aurait dû faire.

5La mémoire est une hiérarchie, pas un tableau uniforme#

Le modèle mental qui paie pour tout le livre : la mémoire n'a pas une vitesse uniforme. Lire une donnée déjà au plus près du CPU prend une nanoseconde. La même lecture prend plusieurs millisecondes si la donnée doit remonter du disque. C'est ce que le livre appelle « plus de six ordres de grandeur » (p. 300) d'écart : un facteur d'un million. À notre échelle, c'est la différence entre une seconde et douze jours.

Deux conséquences à mémoriser :

• le désalignement : une donnée à cheval sur les frontières du bus double les accès mémoire, invisiblement ;
• les wait states : « tourner avec un wait state à chaque accès mémoire, c'est presque comme diviser la fréquence du processeur par deux » (p. 152).

Toute cette hiérarchie n'existe que pour exploiter un fait statistique : un programme passe son temps sur une petite fraction de ses données. Ce fait a un nom : la localité.

Et si ce schéma vous rappelle quelque chose, c'est normal : le web entier rejoue la même hiérarchie un cran au-dessus. Redis devant MySQL, OPcache devant le disque, un CDN devant votre serveur. À chaque fois, la même idée : placer une mémoire petite et rapide devant une mémoire grande et lente, et parier que la donnée demandée est déjà dans la petite. Comprendre la version CPU, c'est comprendre d'un coup pourquoi toutes ces couches existent, et pourquoi elles marchent.

6La ligne de cache décide de la vitesse de vos boucles#

Sous le cache L1, la mémoire ne circule jamais octet par octet : elle circule par lignes de cache de 16 à 64 octets consécutifs. Touchez un élément, et ses voisins arrivent gratuitement. C'est pourquoi l'ordre de deux boucles imbriquées, à logique identique, peut tout changer :

// lent : saute de 1 024 octets à chaque itération (colonne par colonne)
for (i = 0; i < 256; ++i)
  for (j = 0; j < 256; ++j)
    tableau[j][i] = i * j;

// rapide : parcourt la mémoire séquentiellement (ligne par ligne)
for (i = 0; i < 256; ++i)
  for (j = 0; j < 256; ++j)
    tableau[i][j] = i * j;

La mesure de Hyde : « cette petite modification peut être responsable d'un ordre de grandeur (ou deux) de différence dans le temps d'exécution de ces deux séquences ! » (p. 315). Même algorithme, dix à cent fois plus rapide, juste en parcourant la mémoire dans le sens où elle est rangée.

Les habitudes qui vont avec :

• déclarer ensemble les variables utilisées ensemble ;
• préférer les variables locales : la pile est presque toujours en cache ;
• allouer par gros blocs : les micro-allocations peuvent brûler l'essentiel de leurs octets en frais de gestion.

7Le pipeline déteste vos sauts#

Un CPU n'exécute pas une instruction à la fois : il fait tourner une chaîne de montage (chercher, décoder, adresser, charger, calculer, ranger), avec une instruction à chaque poste. En régime de croisière, une instruction sort par cycle. Le prix : un branchement pris jette tout ce qui est déjà sur la chaîne, et le pipeline se remplit depuis zéro. Le conseil de Hyde est direct : « si vous voulez écrire du code rapide, évitez autant que possible de sauter partout dans votre programme » (p. 242).

Même logique pour les dépendances de données : une instruction qui lit une valeur que la précédente est encore en train d'écrire bloque la chaîne.

Les CPU modernes se défendent avec la prédiction de branchement, l'exécution dans le désordre et le renommage de registres, tout cela invisible pour votre code. Mais ils adoucissent la règle, ils ne l'abrogent pas : des branchements prévisibles et des calculs indépendants restent ce que la machine préfère manger.

L'exemple le plus parlant du phénomène : parcourir un grand tableau en testant if (valeur > seuil) peut être plusieurs fois plus rapide si le tableau est trié. Mêmes données, même boucle. Mais trié, le prédicteur devine juste presque à chaque tour ; mélangé, il se trompe une fois sur deux, et chaque erreur vide la chaîne de montage. C'est le sujet d'une des questions les plus votées de l'histoire de Stack Overflow (« Why is processing a sorted array faster than processing an unsorted array? »).

8Ce que la 2ᵉ édition (2020) corrige#

J'ai lu la 1ʳᵉ édition (2004), et son âge se voit à deux endroits. Le chapitre caractères décrit Unicode comme du 16 bits fixe, et ne mentionne jamais UTF-8, le standard du web qui code chaque caractère sur une largeur variable :

// ce que la 1ʳᵉ éd. enseigne : "un caractère = 16 bits, point"
// la réalité UTF-8 : la largeur dépend du caractère
'A'   → 1 octet    (41)
'é'   → 2 octets   (C3 A9)        // d'où strlen("é") = 2 en PHP
'😀'  → 4 octets   (F0 9F 98 80)

Le chapitre entrées-sorties, lui, est un musée du SCSI, de l'IDE et des ports parallèles. Les mécanismes fondamentaux qu'il enseigne à travers eux (interruptions contre polling, DMA, le séquentiel bat l'aléatoire) sont intacts, mais le matériel a disparu.

La 2ᵉ édition (No Starch, juillet 2020, 472 p.) est celle à acheter. Selon l'éditeur, elle ajoute ce que deux décennies ont changé :

• la génération de code sur les CPU 64 bits modernes et les processeurs ARM ;
• des exemples en Swift et Java à côté du C ;
• les périphériques récents et les grandes mémoires avec SSD.

Le squelette du livre, ce qui l'a fait durer, est le même.