Cuatro mil nóminas cada mes
Una gestoría calcula cada mes la nómina de cuatro mil personas con la regla hours * rate - 5. Recorrer el árbol de la regla para cada persona funciona, pero cada visita a un nodo cuesta.
Así que traduce el árbol una vez a una lista plana de pasos muy pequeños, y ejecuta esa lista para cada persona. Esa traducción es el último trabajo de un compilador.
Al final de esta lección
Nota
Puedo convertir un árbol sintáctico en instrucciones para una máquina de pila.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Generación de código | convertir un árbol sintáctico en instrucciones | |
| Pila | un montón donde el último valor en entrar es el primero en salir | |
| Máquina de pila | una máquina cuyas instrucciones toman valores de una pila | PUSH 5 |
| Bytecode | instrucciones de una máquina de pila que ejecuta un programa | |
| Optimización | cambiar el código para que haga lo mismo con menos trabajo | -O2 |
| Plegado de constantes | calcular una cuenta al compilar | 60 * 60 pasa a 3600 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una máquina de pila trabaja sobre una pila
Una máquina de pila guarda los valores con los que trabaja en una pila. PUSH 5 pone 5 arriba. SUB saca los dos de arriba, resta y mete el resultado.
Para convertir un árbol en código de pila, genera primero el código de cada hijo y después la instrucción del nodo. Al ejecutarse, cada hijo deja su valor en la pila, listo para el nodo.
Ejemplo: hours * rate - 5, con 8 y 12
| Instrucción | Pila después, la cima a la derecha |
|---|---|
| LOAD hours | 8 |
| LOAD rate | 8, 12 |
| MUL | 96 |
| PUSH 5 | 96, 5 |
| SUB | 91 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un generador de código para - y *
# Generación de código: primero los hijos, después la operación.
def generate(tree, code):
if type(tree) == int:
code.append(["PUSH", tree])
return
generate(tree[1], code)
generate(tree[2], code)
if tree[0] == "-":
code.append(["SUB"])
else:
code.append(["MUL"])
code = []
generate(["-", ["*", 8, 12], 5], code)
for line in code:
print(line)
# Cambia el árbol por ["*", 8, ["-", 12, 5]] y vuelve a ejecutar.
Python también ejecuta una máquina de pila
Python no recorre tu árbol cada vez. Lo compila a bytecode, instrucciones para una máquina de pila que lleva dentro, y ejecuta eso.
El módulo dis imprime el bytecode de un archivo. Los Runs escriben un archivo de una línea, pay.py, y enseñan su bytecode. No hagas caso de RESUME arriba ni de las dos líneas del final: salen en todos los archivos.
Entra en la carpeta del compilador
cd ~/compilerSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Escribe un programa de una línea
echo "pay = hours * rate - 5" > pay.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Su bytecode
python3 -m dis pay.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ejemplo: el bytecode de pay.py
| Bytecode | Nuestro código | Qué hace |
|---|---|---|
| LOAD_NAME hours | LOAD hours | Mete el valor de hours |
| LOAD_NAME rate | LOAD rate | Mete el valor de rate |
| BINARY_OP (*) | MUL | Saca dos y mete el producto |
| LOAD_SMALL_INT 5 | PUSH 5 | Mete el número 5 |
| BINARY_OP (-) | SUB | Saca dos y mete la resta |
| STORE_NAME pay | Todavía nada | Saca la cima y la liga a pay |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El compilador sabe cuánto crece la pila
Antes de ejecutar nada, el compilador de Python cuenta la altura máxima que alcanzará la pila. Así reserva el sitio justo.
Mira la tabla del principio: la pila nunca tiene más de dos valores. El Run pide a Python esa cuenta para pay.py. Se guarda en el código compilado, en co_stacksize.
La altura máxima de la pila
python3 -c "print(compile(open('pay.py').read(), 'pay.py', 'exec').co_stacksize)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un optimizador trabaja al compilar
gcc genera código para un procesador real, con registros además de pila. Con -O2 también optimiza.
Los Runs escriben el ensamblador dos veces, una normal y otra optimizada. Después grep -c -w cuenta las líneas con el número entero 49, el resultado de square(7). El programa nunca escribe 49. Fíjate en dónde aparece.
Ensamblador sin optimizar
gcc -S -O0 -o plain.s hello.cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ensamblador con -O2
gcc -S -O2 -o fast.s hello.cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Líneas con 49 en la versión normal
grep -c -w 49 plain.sSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Y en la versión optimizada
grep -c -w 49 fast.sSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Python también pliega constantes
echo "seconds = 60 * 60 * 24" > day.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El bytecode de la cuenta plegada
python3 -m dis day.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que optimizar es ejecutar las mismas instrucciones más deprisa. Con -O2, gcc reescribió el trabajo: calculó square(7) él mismo, y main ya no multiplica. Un optimizador puede cambiar cualquier instrucción, siempre que el programa haga lo mismo.
Para ir más lejos
Haz que tu generador ahorre pila. En un + o un *, el orden de los hijos no cambia el resultado. Genera primero el hijo que más pila necesita.
Compara max_depth antes y después con ["+", 1, ["*", 2, 3]]. Después explica por qué con - y / no puedes cambiar el orden sin más.