Un moteur de recherche d'hôtels correct mais lent. Avec perf et un flame graph, on trouve où part le temps, on corrige, on re-mesure, et le point chaud se déplace. De 11,7 s à 2,1 s en Python, 0,28 s en Java.
Ne jamais optimiser à l'intuition sur un gros programme : on profile. perf échantillonne la pile d'appel très régulièrement, un flame graph montre où le temps se concentre (largeur = temps). On corrige uniquement le point chaud, on re-profile, et le point chaud change. Ici : tri O(n^2), puis double boucle, puis calcul inutile pour 85 % des hôtels. La loi d'Amdahl prédit le gain de chaque étape à partir du profil. Java gagne encore x7,5 (types statiques, JIT), Rust va plus loin (compilé en avance, inlining total).
01 · L'outil
perf est le profileur du noyau Linux. Il ne trace pas chaque appel (trop lent) : il échantillonne. Très régulièrement (la fréquence est réglable), il regarde quelle fonction tourne et toute la chaîne d'appel qui y mène. Sur un programme assez long, les fonctions les plus lourdes ressortent statistiquement.
L'option -g (--call-graph=fp) enregistre à chaque échantillon qui a appelé qui, pas seulement la fonction courante. Sans elle, on sait qu'on est dans haversine, pas d'où on vient.
Self : temps passé dans le code de la fonction elle-même. Children : self plus tout ce qu'elle appelle. Une fonction chef d'orchestre a un petit self et un gros children.
Chaque case est une fonction, empilées par profondeur d'appel. Plus c'est large, plus ça coûte. Le mode Left Heavy de speedscope agrège et trie pour lire d'un coup d'oeil.
La recette exacte du lab, du terminal à la lecture :
Sans PYTHONPERFSUPPORT=1, Python est du code interprété que perf ne sait pas nommer : on voit des cases [unknown] à la place des fonctions du script. Pour Java, l'équivalent est -XX:+DumpPerfMapAtExit.
02 · Le programme à optimiser
Une base de 5000 hôtels générée en mémoire (prix, position sur une grille, services, note, avis) et 1000 appels à search_hotels qui cherchent les meilleurs hôtels selon un prix, des services voulus et un rayon de 30 km.
Le programme est correct et petit : on pourrait deviner où optimiser. Sur un vrai projet de milliers de lignes, non. C'est tout l'intérêt de la méthode : on ne devine pas, on mesure.
03 · Le voyage des hotspots
À chaque version, on regarde le profil, on prend la fonction la plus lourde et on ne modifie qu'elle. Choisis une version : les barres du haut sont la part de temps de chaque fonction (children), celles du bas les temps totaux.
Temps total (barre pleine = original)
Parts recomptées sur les vraies traces stack_traces_v0..v3.txt du lab (à environ 1 point près des valeurs de speedscope). Temps mesurés au lab (moyenne sur 3 runs pour v1 à v3). Les parts se chevauchent : elles comptent les children, donc calc_svc_score est inclus dans calc_score.
À l'original, sorth pèse 48 %. Une fois corrigé, il disparaît du profil et calc_svc_score devient le plus lourd (55 %). Après sa correction, c'est haversine qui monte (de 12 % à 63 %), non pas parce qu'elle a ralenti mais parce que tout le reste a fondu autour d'elle. C'est normal : le point chaud est toujours relatif.
Les versions 1 et 2 réparent des fonctions. La v3 change l'ordre des opérations : elle calcule la distance avant le score et ne score que les hôtels du rayon. C'est le levier le plus puissant du lab, et aucun profileur de fonction isolée ne l'aurait suggéré : il faut regarder le flame graph en entier et se demander pourquoi calc_score est appelée 5000 fois par recherche.
04 · Prédire le gain
Si une partie représentant la fraction p du temps devient s fois plus rapide, le programme entier est plus rapide d'un facteur :
gain = 1 / ( (1 - p) + p / s ) // plafond quand s tend vers l'infini : 1 / (1 - p)
Le profil dit donc avant même de coder ce qu'on peut espérer. Si une fonction ne pèse que 5 % du temps, même infiniment rapide, le gain est plafonné à 1,05. Vérifions sur le lab, avec les vraies mesures :
Original vers v1 : sorth pèse 48 %, remplacée par un tri natif quasi gratuit : prédit 1,9 x, mesuré 1,95 x. v1 vers v2 : s = 1,8 est déduit du gain mesuré (le profil ne le donne pas). v2 vers v3 : voir l'exercice 4, s = 6,7 vient du calcul du nombre d'hôtels dans le rayon.
05 · Autres langages
La v3 portée en Java (même architecture : HashSet, List.sort, Math.*) tourne en 0,278 s contre 2,1 s : x7,5. Le nombre d'appels à haversine et calc_score est identique, seul le coût par appel change : types primitifs statiques, compilation JIT vers du code natif, pas de typage dynamique à chaque opération.
Sur un run aussi court (0,28 s), plus de la moitié des échantillons tombent dans les threads de compilation JIT de la JVM (CompileBroker, C2Compiler), pas dans le code métier. Démarrage et warmup ne sont pas gratuits.
Compilé en avance (AOT) : pas de JIT, pas de garbage collector, code optimisé dès le premier appel. Et l'inlining fond toutes les fonctions du programme dans main.
Dans la trace Rust fournie, on ne voit plus haversine ni calc_svc_score : elles ont disparu par inlining. On retrouve leurs équivalents dans la bibliothèque standard. Compteurs cumulés de la trace :
| Fonction du programme | Équivalent visible dans la trace Rust |
|---|---|
| calc_svc_score (ensembles) | HashMap::contains_key, hash_one, Hasher::write |
| sorth (tri) | slice::sort::stable::quicksort, driftsort_main, smallsort |
| tout le reste | best_offer::main (inlining complet) |
Ne compare pas les temps. La trace Rust vient d'une machine x86_64 (symboles comme __memcmp_avx2_movbe), la trace Java d'un conteneur arm64 (Apple Silicon). Seule une analyse structurelle est honnête : Rust cumule les avantages de Java (compilé, typé) et retire JIT, GC et warmup. Ordre attendu : Rust, puis Java, puis Python.
06 · Questions du lab corrigées
Variable d'environnement, option -g et call graph.
sudo PYTHONPERFSUPPORT=1 perf record -g -o ~/perf.data python3 best_offer.py
Active dans CPython un support qui écrit dans /tmp/perf-PID.map les noms des fonctions Python. C'est plus fiable dans ce conteneur que l'option -X conseillée dans certains tutoriels.
Le code exécuté est du code généré à la volée que perf ne sait pas associer à un nom : les fonctions du script restent invisibles.
Une structure qui capture, à chaque échantillon, toute la chaîne d'appel (qui a appelé qui, sur quelle profondeur), pas seulement la fonction en cours. Elle permet de distinguer le temps propre (self) du temps hérité des fonctions appelées (children), et sert de base au flame graph.
Lecture du profil de l'original.
| Fonction | Children |
|---|---|
| sorth | 47 % |
| calc_score | 37 % |
| calc_svc_score | 29 % |
| haversine | 12 % |
sorth : la plus lourde. C'est un tri par insertion écrit à la main (boucle et list.insert), en O(n^2).
def sorth(results): return sorted(results, key=lambda x: x["score"], reverse=True)
11,702 s devient 6,000 s, soit x1,95, ce qu'Amdahl prévoit pour une part de 48 %.
calc_svc_score puis comparaison v1 contre v2.
sorth a disparu, calc_svc_score est la plus lourde (55 % en children). Elle fait une double boucle en O(n*m) et refait lower().strip() à chaque paire.
def calc_svc_score(reqservcs, availservcs): req_norm = {s.lower().strip() for s in reqservcs} avail_norm = {s.lower().strip() for s in availservcs} return float(len(req_norm & avail_norm))
O(n+m) au lieu de O(n*m). Nuance : les ensembles dédupliquent, donc un service en double dans la requête compterait 1 point au lieu de plusieurs. Sans conséquence ici (aucune liste du script n'a de doublon), mais à vérifier dans un vrai projet.
| run 1 | run 2 | run 3 | |
|---|---|---|---|
| best_offer_1.py | 6,050 s | 6,077 s | 6,098 s |
| best_offer_2.py | 4,634 s | 4,566 s | 4,655 s |
Trois mesures chacune, séries disjointes (la plus lente de v2 est plus rapide que la plus rapide de v1). Et le profil confirme que le gain vient de la fonction modifiée : calc_svc_score passe de 55 % à environ 40 %. La preuve d'une optimisation, ce sont des temps répétés plus un profil qui change là où on a agi.
Pourquoi filtrer avant de scorer, et combien ça gagne, chiffres à l'appui.
Dans search_hotels, calc_score est appelée pour les 5000 hôtels à chaque recherche, même ceux hors du rayon de 30 km, dont le score est ensuite jeté.
Les hôtels sont sur une diagonale : position i % 150, latitude et longitude qui avancent de 0,01 degré par pas. Chaque pas fait environ 1,37 km depuis le point de recherche, donc seuls les pas 0 à 21 sont à moins de 30 km. C'est 22 positions sur 150, soit 748 hôtels sur 5000, 15 % (calculé avec la vraie formule haversine).
calc_score pèse 59 % du temps de v2 et n'est plus appelée que pour 15 % des hôtels, donc s = 1 / 0,15 = 6,7. Gain = 1 / (0,41 + 0,59 / 6,7) = 2,0. Mesuré : 4,491 s vers 2,100 s = 2,14. Le petit écart vient de la partie du tri et des copies, elles aussi réduites.
Un bon changement d'architecture évite du travail au lieu de le rendre plus rapide. C'est le levier le plus puissant, et il se prédit à partir des données du problème (ici, la géométrie de la grille).
Commande, résultat, explication.
sudo perf record -g -o ~/perf.data java -XX:+PreserveFramePointer \ -XX:+UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints -XX:+DumpPerfMapAtExit BestOffer
-XX:+DumpPerfMapAtExit est l'équivalent de PYTHONPERFSUPPORT : il écrit le perf-PID.map des méthodes compilées à la volée. Si speedscope affiche mal les symboles JIT, utiliser profiler.firefox.com.
Java 0,278 s contre 2,100 s pour Python v3 (moyenne de 3 runs) : x7,5. Java est donc le plus performant des deux.
Types statiques et primitifs, compilation JIT vers du code natif, pas d'objets ni de typage dynamique à chaque opération. Le nombre d'appels aux fonctions coûteuses est le même : seul le coût par appel change avec le langage. Dans le profil Java, search_hotels pèse 31 %, calc_score 19 %, haversine 2 %, et plus de la moitié des échantillons sont dans la compilation JIT.
Lire une trace Rust fournie, sans pouvoir comparer les temps.
Aucune fonction du programme (haversine, calc_score, sorth) : tout est fondu dans best_offer::main par l'inlining agressif de LLVM en release. On retrouve des fonctions de la bibliothèque standard : HashMap::contains_key (test d'appartenance de calc_svc_score), driftsort (le tri de sorth).
| Java | Rust | |
|---|---|---|
| Compilation | JIT, à l'exécution | AOT, en avance |
| Warmup | Oui, progressif | Non, optimisé dès le premier appel |
| Mémoire | Garbage collector | Pas de GC |
| Profil | Fonctions séparées visibles | Tout fondu dans main |
Rust est attendu plus rapide. Mais la trace Rust est x86_64 et la trace Java arm64 : on ne peut pas comparer les temps bruts, seulement la structure. Une bonne réponse le dit explicitement.
07 · Réviser
Le QCM tire un échantillon au hasard dans le pool ; chaque réponse est corrigée et expliquée.
Entraîneur Pour un QCM qui s'adapte à ton niveau, revient sur tes erreurs et explique chaque réponse avec une fiche illustrée : s'entraîner sur ce chapitre.
Pool de 23 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.