Ten thousand orders an hour
The shop's price rule from the last lesson now runs for ten thousand orders an hour. Walking the tree each time is too slow.
So the shop translates the tree once into a flat list of tiny steps, and runs the list for every order. That translation is the last job of a compiler.
By the end of this lesson
Note
I can turn a syntax tree into instructions for a stack machine.
Key words
| Word | What it means | Example |
|---|---|---|
| Code generation | turning a syntax tree into instructions | |
| Stack | a pile where the last value in is the first out | |
| Stack machine | a machine whose instructions take values from a stack | PUSH 2 |
| Bytecode | instructions for a stack machine run by software | |
| Optimisation | changing code so it does the same thing with less work | -O2 |
| Constant folding | working out a sum at compile time | 6 * 7 becomes 42 |
The cells students fill in are left blank in this preview.
A stack machine keeps values on a stack
A stack machine keeps its working values on a stack. PUSH 2 puts 2 on top. ADD takes the top two off, adds them, and pushes the answer.
To turn a tree into stack code, generate each child's code first, then the node's own instruction. When the code runs, each child leaves its value on the stack, ready for the node.
Worked example: the code for 2 + 3 * 4
| Instruction | Stack after it, top on the right |
|---|---|
| PUSH 2 | 2 |
| PUSH 3 | 2, 3 |
| PUSH 4 | 2, 3, 4 |
| MUL | 2, 12 |
| ADD | 14 |
The cells students fill in are left blank in this preview.
A code generator for + and *
# Code generation: children first, then the operation.
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(["ADD"])
else:
code.append(["MUL"])
code = []
generate(["+", 2, ["*", 3, 4]], code)
for line in code:
print(line)
# Change the tree to ["*", ["+", 2, 3], 4] and run again.
Python runs a stack machine too
Python does not walk your tree each time. It compiles the tree to bytecode, instructions for a stack machine inside Python, and runs those.
The module dis prints the bytecode of a file. The Runs write a one-line file, sum.py, and show its bytecode. Ignore RESUME at the top and the two lines at the end: every file has them.
Go into the compiler folder
cd ~/compilerShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Write a one-line program
echo "total = price * count + 1" > sum.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Its bytecode
python3 -m dis sum.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: the bytecode of sum.py
| Bytecode | Our stack code | What it does |
|---|---|---|
| LOAD_NAME price | LOAD price | Push the value of price |
| LOAD_NAME count | LOAD count | Push the value of count |
| BINARY_OP (*) | MUL | Take two off, push the product |
| LOAD_SMALL_INT 1 | PUSH 1 | Push the number 1 |
| BINARY_OP (+) | ADD | Take two off, push the sum |
| STORE_NAME total | None yet | Take the top off and bind it to total |
The cells students fill in are left blank in this preview.
An optimiser does work at compile time
gcc makes code for a real processor, with registers as well as a stack. With -O2 it also optimises.
The Runs write the assembly twice, once plain and once optimised. Then grep -w looks for the whole number 49, the answer to square(7), in each. The program never says 49 anywhere. Watch where it turns up.
Assembly with no optimisation
gcc -S -O0 -o plain.s hello.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Assembly at -O2
gcc -S -O2 -o fast.s hello.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Lines with 49 in the plain version
grep -c -w 49 plain.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
And in the optimised version
grep -w 49 fast.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Where 7 is in the plain version
grep -w 7 plain.sShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Python folds constants as well
echo "total = 6 * 7" > folded.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The bytecode of the folded sum
python3 -m dis folded.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think optimisation runs the same instructions faster. At -O2 gcc rewrote the work: it worked out square(7) itself, so main never multiplies at all. The program prints the same line either way. An optimiser may change any instruction, as long as what the program does stays the same.
Going further
Add constant folding to your compile_tree. Before you generate code for an operation, check whether both children are plain numbers. If they are, work the sum out and emit one PUSH.
Fold from the bottom up, so ["+", 2, ["*", 3, 4]] becomes [["PUSH", 14]]. Then say why a tree with a name in it can only be folded in part.