This article highlights the first optimizations I made while redesigning and semi-porting the runtime from C to Rust. These aren’t benchmarked or verified, since the virtual machine is currently under construction and will probably be finished this week.
At a high level, purple-garden current works like this, with 2+3*4-1 as an exemplary input:
TEXT
1 . 2 +- Tokenizer 3 | 4 ]: Token(2) Token(+) Token(3) 5 ]: Token(*) 6 ]: Token(4) Token(-) Token(1) 7 | 8 \ 9 +- Parsing (Tokens -> Abstract Syntax Tree) 10 | 11 ]: (Asteriks 12 ]: (Plus 13 ]: Integer("2") 14 ]: Integer("3") 15 ]: ) 16 ]: (Minus 17 ]: Integer("4") 18 ]: Integer("1") 19 ]: ) 20 ]: ) 21 | 22 | 23
Peephole Optimizations
Peephole optimisations are, as the name implies, optimisations performed on a small section of a larger input. For a virtual machine, like purple-garden this means using a window of size 3 (anything larger is no longer local subject to IR optimisation, not peephole and will have happened before peephole optimisation is reached in the compilation pipeline) and merging operators, rewriting redundant or useless operations.
So to summarize:
peephole optimisations are done on the bytecode in a local setting (non-global)
in this case they are fallback optimisations for things the IR optimisation rewriting missed
these are local, single-pass, and meant only to catch what the IR opt didn’t
... continue reading