Cinq mille réservations par heure
La règle de prix du loueur de vélos tourne maintenant pour cinq mille réservations par heure. Parcourir l’arbre à chaque fois devient trop lent.
Le site traduit donc l’arbre une seule fois en une liste plate de petites instructions. Il exécute ensuite cette liste pour chaque réservation. Cette traduction est le dernier travail d’un compilateur.
À la fin de cette leçon
Remarque
Je peux traduire un arbre syntaxique en instructions pour une machine à pile.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Génération de code | traduire un arbre syntaxique en instructions | |
| Pile | un tas où la dernière valeur posée sort la première | |
| Machine à pile | une machine dont les instructions prennent leurs valeurs sur une pile | EMPILER 2 |
| Bytecode | des instructions pour une machine à pile faite de logiciel | |
| Optimisation | changer le code pour faire la même chose avec moins de travail | -O2 |
| Repliement de constantes | faire un calcul dès la compilation | 60 * 60 devient 3600 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Les valeurs vivent sur une pile
Une machine à pile garde ses valeurs de travail sur une pile. EMPILER 8 pose 8 au sommet. SOUS retire les deux valeurs du sommet, fait la soustraction et pose la réponse.
Pour traduire un arbre, produisez d’abord le code de chaque enfant, puis l’instruction du nœud. À l’exécution, chaque enfant laisse sa valeur sur la pile, prête pour le nœud.
Exemple travaillé : le code de 8 - 2 * 3
| Instruction | La pile après, sommet à droite |
|---|---|
| EMPILER 8 | 8 |
| EMPILER 2 | 8, 2 |
| EMPILER 3 | 8, 2, 3 |
| MUL | 8, 6 |
| SOUS | 2 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un générateur de code pour + et *
# Génération de code : les enfants d'abord, puis l'opération.
def generer(arbre, code):
if type(arbre) == int:
code.append(["EMPILER", arbre])
return
generer(arbre[1], code)
generer(arbre[2], code)
if arbre[0] == "+":
code.append(["ADD"])
else:
code.append(["MUL"])
code = []
generer(["*", ["+", 1, 2], 5], code)
for ligne in code:
print(ligne)
# Remplacez l'arbre par ["+", 1, ["*", 2, 5]], puis relancez.
Python fait tourner une machine à pile
Python ne parcourt pas votre arbre à chaque exécution. Il le traduit en bytecode, des instructions pour une machine à pile cachée dans Python, puis il les exécute.
Le module dis affiche le bytecode d’un fichier. Les Runs écrivent un fichier d’une ligne, solde.py, puis montrent son bytecode. Ignorez RESUME en haut et les deux lignes de la fin : tout fichier les a.
Aller dans le dossier du compilateur
cd ~/compilerAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Écrire un programme d’une ligne
echo "solde = credit - debit * 2" > solde.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Son bytecode
python3 -m dis solde.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Exemple travaillé : le bytecode de solde.py
| Bytecode | Notre code à pile | Ce qu’il fait |
|---|---|---|
| LOAD_NAME credit | CHARGER credit | Empile la valeur de credit |
| LOAD_NAME debit | CHARGER debit | Empile la valeur de debit |
| LOAD_SMALL_INT 2 | EMPILER 2 | Empile le nombre 2 |
| BINARY_OP (*) | MUL | Retire deux valeurs, empile le produit |
| BINARY_OP (-) | SOUS | Retire deux valeurs, empile la différence |
| STORE_NAME solde | Pas encore | Retire le sommet et le lie à solde |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un optimiseur travaille pendant la compilation
gcc produit du code pour un vrai processeur, avec des registres en plus de la pile. Avec -O2, il optimise aussi.
Les Runs écrivent l’assembleur deux fois, une fois sans optimisation et une fois avec. grep -c -w 49 compte ensuite les lignes qui contiennent le nombre 49, la réponse de square(7). Le programme n’écrit 49 nulle part.
L’assembleur sans optimisation
gcc -S -O0 -o lent.s hello.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
L’assembleur à -O2
gcc -S -O2 -o rapide.s hello.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Combien de 49 dans la version lente ?
grep -c -w 49 lent.sAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Et dans la version optimisée ?
grep -c -w 49 rapide.sAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Python replie aussi les constantes
echo "secondes = 60 * 60 * 24" > jour.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le bytecode du calcul replié
python3 -m dis jour.pyAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens pensent qu’optimiser, c’est exécuter les mêmes instructions plus vite. À -O2, gcc a réécrit le travail : il a calculé square(7) lui-même, et main ne multiplie plus rien. Le programme affiche la même ligne. Un optimiseur peut changer n’importe quelle instruction, tant que le programme fait la même chose.
Pour aller plus loin
Ajoutez le repliement de constantes à votre compiler. Avant de produire le code d’une opération, regardez si ses deux enfants sont de simples nombres. Si oui, faites le calcul et produisez un seul EMPILER.
Repliez de bas en haut, pour que ["+", 2, ["*", 3, 4]] devienne [["EMPILER", 14]]. Expliquez ensuite pourquoi un arbre qui contient un nom ne se replie qu’en partie.