Programming Pearls

1Le coup de fil de quinze minutes (et le bitmap)

Un programmeur appelle Bentley avec une question qui semble banale : comment trier un fichier sur disque ? Bentley ébauche un tri fusion sur disque, environ 200 lignes et une semaine de travail. Puis il pose des questions. Le fichier contient au plus 10 millions de numéros de téléphone à 7 chiffres, sans doublons, sans données associées, et « environ un mégaoctet » de mémoire libre. Le problème change de forme : ce n'est plus « trier un fichier », c'est « ordonner 10 millions de petits entiers distincts dans 1 Mo ».

La réponse : représenter les données par 10 millions de bits : un tableau alloué d'un bloc en mémoire vive, où la case numéro i vaut 1 si le numéro de téléphone i est dans le fichier. Rien n'est jamais trié : la position dans le tableau joue le rôle de valeur. Dix millions de bits font 1,25 Mo, et le livre montre comment les faire tenir dans le mégaoctet disponible. On lit l'entrée, on allume les bits, puis on parcourt le bitmap une fois et on réécrit les numéros, triés gratuitement. Quelques dizaines de lignes, quelques heures de travail, environ dix secondes d'exécution. « Le programmeur m'a exposé son problème par téléphone ; il nous a fallu environ quinze minutes pour arriver au vrai problème et trouver la solution bitmap » (Column 1). Et la morale, en une ligne : « définir le problème représentait environ quatre-vingt-dix pour cent de cette bataille ». Saint-Exupéry a le dernier mot : la perfection est atteinte quand il n'y a plus rien à retirer.

2Aha ! : le retournement de mains et la signature triée

La colonne 2 s'intitule « Aha ! » : le déclic, cette seconde où la bonne idée saute aux yeux et rend trivial un problème qui semblait dur. Elle réunit des solutions qui ressemblent à des tours de magie, dont la mécanique tient en trois lignes une fois qu'on l'a vue. Premier exemple : décaler un tableau de n éléments de d positions vers la gauche. Prendre [1, 2, 3, 4, 5], décaler de d = 2, doit donner [3, 4, 5, 1, 2]. La solution évidente recopie tout dans un nouveau tableau (nouveau[i] = ancien[(i + d) % n]) : elle marche, mais elle double la mémoire. Bentley refuse ce luxe et pose la vraie contrainte : la même rotation sur place, sans un octet de mémoire en plus. Sa réponse, en trois renversements et toujours en temps linéaire :

// Étape 1 : renverser les d premiers éléments
[1, 2, 3, 4, 5]  →  [2, 1, 3, 4, 5]
// Étape 2 : renverser les n-d éléments restants
[2, 1, 3, 4, 5]  →  [2, 1, 5, 4, 3]
// Étape 3 : renverser tout le tableau
[2, 1, 5, 4, 3]  →  [3, 4, 5, 1, 2]  ✓

Zéro allocation. L'astuce : voir le tableau comme deux blocs, [1, 2] puis [3, 4, 5], qu'on veut intervertir. Renverser chaque bloc, puis renverser le tout : les deux blocs ont échangé leur place sans qu'on ait jamais rien copié. Doug McIlroy le montrait avec ses mains : retourner la gauche, retourner la droite, retourner les deux.

function reverse(a, lo, hi) {
  while (lo < hi) {
    const t = a[lo]; a[lo] = a[hi]; a[hi] = t;   // swap sur place, zéro allocation
    lo++; hi--;
  }
}
// rotation à gauche de d : reverse(a,0,d-1) ; reverse(a,d,n-1) ; reverse(a,0,n-1)

Deuxième tour de magie : trouver toutes les familles d'anagrammes d'un dictionnaire de 230 000 mots. La force brute compare tous les couples de mots : 14,7 heures selon le calcul du livre. Le déclic tient en une fonction : donner à chaque mot une signature en triant ses lettres par ordre alphabétique.

signature = lambda mot: "".join(sorted(mot))
signature("deposit")   # → "deiopst"
signature("dopiest")   # → "deiopst"  ← même signature → ce sont des anagrammes

Trier les mots par signature : les anagrammes tombent côte à côte automatiquement. Un pipeline Unix en trois étages ; à la 2e édition, le dictionnaire entier passe en 18 secondes. La leçon commune aux deux tours : la bonne représentation rend l'algorithme trivial.

3Le calcul au dos de l'enveloppe

La colonne la plus réutilisable du livre apprend à estimer un ordre de grandeur avant de construire, sur un coin de nappe, en trente secondes. Le but n'est pas un chiffre exact, c'est de savoir si une idée tiendra en une seconde ou en mille ans, avant d'écrire la moindre ligne.

Deux règles suffisent. D'abord, « deux réponses valent mieux qu'une » : estimez la même quantité par deux chemins indépendants, et si les deux concordent, fiez-vous-y. Bentley calcule ainsi le débit du Mississippi de deux manières, la largeur du fleuve fois sa vitesse, puis la surface de terres dont la pluie s'y déverse fois les précipitations annuelles. Les deux tombent dans le même ordre de grandeur, donc l'estimation tient.

Ensuite, gardez quelques repères en tête pour convertir vite. Le plus utile ici : une année fait environ π × 10⁷ secondes, soit 31,5 millions, à un demi pour cent près. C'est la perle de Bentley, qu'on retient sous une forme amusante, π secondes pour un « nanosiècle » (un milliardième de siècle).

Le réflexe en action. Vous hésitez à comparer toutes les paires d'un jeu d'un milliard d'éléments. Un milliard au carré, c'est 10¹⁸ opérations, et à un milliard d'opérations par seconde :

# un milliard d'éléments comparés deux à deux
(10⁹)²  =  10¹⁸ opérations
10¹⁸ ops ÷ 10⁹ ops/s         =  10⁹ secondes
# une année ≈ π × 10⁷ secondes
10⁹ s ÷ (3,15 × 10⁷ s/an)    ≈  32 ans

Trente-deux ans pour une boucle qu'on croyait anodine : verdict rendu avant le déjeuner, sur le dos de l'enveloppe, sans une ligne de code.

L'anecdote qui justifie toute la colonne : Bob Martin, à la tête d'une grosse boutique logicielle, en revue d'un système proposé pour les Jeux olympiques, chronomètre l'envoi d'un message d'un seul caractère à lui-même et conclut que le design ne marche que s'il y a « au moins cent vingt secondes dans chaque minute ». Design refusé ; le système livré un an plus tard a fonctionné sans accroc.

L'annexe qui pique : un quiz de dix questions où l'on donne des fourchettes à 90 % de confiance ; la plupart des gens en réussissent 3 à 6 au lieu des 9 attendues. Nous sommes tous trop sûrs de nous, et c'est mesurable.

4Le TRS-80 qui bat l'Alpha

Un seul problème (la sous-séquence contiguë de somme maximale), quatre algorithmes, du cubique au linéaire. O(n³), « ordre n cube », veut dire : le problème double de taille, le temps est multiplié par huit. O(n) : le temps double avec la taille, pas plus. (Si le Big O est neuf pour vous, Grokking Algorithms le déroule de zéro, dessins à l'appui.) Puis le livre organise le combat que personne n'oublie. Dans un coin : l'algorithme cubique, en C compilé, sur une station Alpha à 533 MHz. Dans l'autre : l'algorithme linéaire, en BASIC interprété, sur un TRS-80 des années 1970 à 2,03 MHz. Le croisement se joue entre n = 1 000 et n = 10 000 ; au-delà, la pièce de musée gagne. À n = 1 000 000 : 19 ans pour l'Alpha, 5,4 heures pour le TRS-80.

L'épilogue de la 2e édition ajoute un clin d'œil : en relançant les mesures de la 1re édition quatorze ans plus tard, Bentley a trouvé son Pentium II « presque exactement mille fois plus rapide que le vénérable VAX », avec des coefficients algorithmiques quasi identiques. Les machines changent par puissances de dix ; les maths ne bougent pas.

5La recherche binaire est publiée en 1946. Une version juste a pris bien plus longtemps.

Chercher un mot dans un dictionnaire papier, vous ne commencez pas page 1 : vous ouvrez au milieu, et selon que le mot tombe avant ou après, vous ne fouillez plus qu'une moitié. La recherche binaire fait pareil dans un tableau trié : regarder l'élément du milieu, jeter la moitié qui ne peut pas contenir la cible, recommencer. Chaque coup divise l'espace par deux, donc un million d'éléments se fouillent en une vingtaine d'essais.

Idée enfantine, et pourtant : la première recherche binaire est publiée en 1946, la première version vraiment correcte des années plus tard. Bentley s'en sert justement parce qu'elle est piégeuse. Le bug le plus célèbre se cache dans la ligne qui calcule le milieu :

lo = 0; hi = n - 1;
while (lo <= hi) {
  mid = (lo + hi) / 2;       // ✗ lo + hi peut dépasser le plafond des entiers
  mid = lo + (hi - lo) / 2;  // ✓ même milieu, sans jamais l'approcher
}

Pourquoi ce piège ? Un entier machine a un plafond. Sur un très grand tableau, la somme lo + hi le dépasse et « repasse » dans les négatifs, ce qui fausse le milieu sans la moindre alerte : boucle sans fin ou mauvais résultat. La forme lo + (hi - lo) / 2 donne exactement le même nombre, l'algèbre le prouve : lo + (hi - lo)/2 = lo + hi/2 - lo/2 = (lo + hi)/2. Mais elle ne manipule que des valeurs déjà dans les bornes, car hi - lo est plus petit que hi : jamais elle n'approche le plafond.

Ce bug précis a dormi neuf ans dans la bibliothèque standard de Java, repéré seulement en 2006.

Bentley se sert de cet algorithme « simple » pour enseigner une discipline rare : prouver le code au lieu de l'essayer. Son outil, l'invariant de boucle : une phrase qui doit rester vraie à chaque tour de la boucle, quoi qu'elle vienne de faire. Ici : « si la cible est dans le tableau, elle se trouve forcément entre les indices lo et hi. » On écrit cette phrase d'abord, puis on en déduit chaque ligne. Le code n'est plus une supposition qu'on vérifie après coup, c'est une preuve qu'on construit.

La colonne 5 ajoute l'outillage qui rend cette preuve praticable : un harnais de test (un petit programme jetable qui lance la fonction sur des centaines de cas), des assertions (des contrôles qui stoppent net dès qu'un invariant se brise), et un chronométrage automatique. Neuf versions de la recherche binaire accompagnent le livre, dont une fausse exprès, pour que le harnais prouve qu'il sait l'attraper. C'est déjà du TDD (Test-Driven Development, écrire les tests avant le code), deux décennies avant que le mot existe, en C de l'époque.

6Déboguer est un exercice d'incrédulité

La section sur le débogage est une petite anthologie de bugs « impossibles » qui cachaient tous une explication banale. Un programmeur se connecte sans souci assis, jamais debout : assis, il tape par automatisme, sans regarder, et tombe sur les bonnes touches ; debout, il regarde le clavier, où deux capuchons de touches avaient été échangés, et suit les fausses étiquettes. Un système bancaire de Chicago plante chaque fois qu'un client se nomme « Quito » : le terminal lit ces lettres comme sa commande quit (quitter) et se coupe. Un programme « marche une fois, puis deux » et échoue ensuite : une variable préparée au lancement n'était jamais remise à zéro avant le passage suivant.

L'attitude tient en une image, que Bentley emprunte à Rick Lemons : la meilleure leçon de débogage de sa vie lui est venue d'un spectacle de magie, une demi-douzaine de tours impossibles à la suite. Aucun n'était vraiment impossible, et votre bug non plus. Dans les deux cas, vous regardez la mauvaise main. « Déboguer, c'est d'habitude refuser de croire » : écartez l'explication surnaturelle et l'explication logique remonte. Au quotidien, le bug qui n'apparaît qu'en production, ou seulement après le déploiement du vendredi, n'a rien de magique. Cherchez ce qui a changé : l'environnement, le cache, l'ordre des requêtes.

7Chaînes de perles : la Bible, l'Iliade et le grand-père des LLM

La colonne 15, ajoutée en 2000, s'attaque à de gros textes, et chaque problème se règle en choisissant la bonne structure de données. D'abord, compter combien de fois chaque mot apparaît dans la Bible du roi Jacques (789 616 mots en tout, 29 131 différents, « the » à lui seul 62 053 fois). L'outil naturel : une table de hachage, la structure qui associe à chaque clé sa valeur en un accès direct, exactement ce qu'est un tableau associatif en PHP ou un objet en JavaScript. Ici la clé est un mot, la valeur son compteur. Bentley en écrit une maison, 30 lignes, taillée pour des mots anglais, et elle bat la version générique de la bibliothèque C++ d'un facteur dix. La leçon : quand on connaît la forme exacte de ses données, une petite structure sur mesure écrase l'outil universel.

Deuxième problème : trouver le plus long passage qui se répète dans un texte, mettons l'Iliade. Comparer toutes les positions deux à deux serait bien trop lent. L'astuce passe par un tableau de suffixes (suffix array). Un suffixe, c'est la fin du texte à partir d'une position donnée ; pour « ILIADE », les suffixes sont ILIADE, LIADE, IADE, ADE, DE, E. On les trie tous par ordre alphabétique. Le truc : si un passage apparaît deux fois, les deux suffixes qui démarrent à ses deux occurrences commencent par les mêmes mots, donc le tri les colle l'un à côté de l'autre. Il ne reste qu'à comparer chaque suffixe à son voisin et à garder le plus long début commun. Sur l'Iliade (807 503 suffixes), 4,8 secondes suffisent à débusquer une phrase entière que Junon prononce et que Minerve répète mot pour mot à Ulysse.

Le clou du spectacle : fabriquer du faux texte qui sonne comme une source. La méthode est une chaîne de Markov : à chaque étape, on regarde les k derniers mots produits (k vaut souvent 2), puis on tire le mot suivant au hasard, en respectant les fréquences observées dans la source. Si « la mer » est suivi de « était » deux fois sur trois dans le texte d'origine, on le choisira deux fois sur trois. À l'ordre 2 (k = 2), entraînée sur le livre lui-même, la prose obtenue est troublante de plausibilité ; Bentley note que « pour la parodie, le texte d'ordre 2 est en général le plus savoureux ». En 2000, ça s'écrivait en une soirée. Reprenez exactement ce principe, gonflez-le à quelques milliards de paramètres, entraînez-le sur tout l'internet, et vous obtenez les assistants à qui nous parlons toute la journée. La perle est devenue fonds de pension.

8Les règles qui restent

Les deux épilogues sont des interviews fictives où Bentley se cuisine lui-même (« les gens qui s'interviewent eux-mêmes ne devraient pas critiquer les styles d'écriture »). La liste de design du premier épilogue est l'ADN du livre en six réflexes : travailler sur le bon problème avant tout. Regarder les données avant de concevoir. Estimer sur une enveloppe pour tuer les mauvaises idées tôt. Prototyper avant de s'engager. Rester simple. Viser l'élégance.

Chacun est évident après coup. Chacun est sauté en routine.

La loi de Tom Duff mérite une citation complète, présentée comme la meilleure réponse à « bibliothèque ou fait main ? » : « chaque fois que possible, volez le code. » En 2026 ça s'appelle composer require, npm install et Stack Overflow, mais la frontière a bougé : chaque dépendance est devenue une surface d'attaque et une responsabilité (left-pad, la backdoor xz de 2024), si bien que pour un petit besoin, l'implémentation maison, que l'IA rend bon marché, bat souvent le paquet qui en tire quarante autres. L'exception se durcit en banque ou en santé : la sécurité critique, chiffrement, hachage des mots de passe, authentification, se vole toujours à une bibliothèque auditée, jamais elle ne se bricole maison.

La ligne qui résume le mieux l'esthétique du livre : « les composants les moins chers, les plus rapides et les plus fiables d'un système informatique sont ceux qui n'existent pas. » Chaque colonne finit par prouver ça. Le tri bitmap marche parce qu'il n'y a aucune comparaison. Le pipeline d'anagrammes marche parce qu'une transformation bien choisie rend le tri trivial. L'absence de mécanisme est le mécanisme.

L'annexe de tuning de code (annexe 4) liste des gains de performance mesurés sur des opérations spécifiques, avec un avertissement imprimé en gras : mesurez sur VOTRE machine, parce que le modèle de coûts change à chaque génération de processeur. L'exemple propre du livre : une réservation mémoire de 12 octets en C consomme réellement 48, parce que l'allocateur arrondit à sa taille de bloc interne. Connaître le vrai coût, c'est tout le sujet.