Correctness comes first
An interpreter that is fast and wrong is not much use. Get the behavior right, with a set of tests that pass, before you spend time on speed. The tests are what let you optimize without worrying: if a change breaks something, you find out immediately.
Also ask whether speed matters at all. Many programs written for grid languages finish in a blink. Speed becomes interesting for long-running puzzles, benchmarks, large loops or programs that print a lot. If the interpreter is already fast enough, the best optimization is none.
Measure before changing anything
Guessing which part is slow is unreliable. Use your language’s profiler, or add simple counters and timers, and run a representative program. Typical findings in a simple interpreter are that most time goes to the inner loop: looking up the current cell, deciding which instruction it is, and moving the pointer. Those are the places worth improving.
Try a few different programs. A program with long loops of arithmetic stresses different code than one that prints thousands of characters, where output buffering may dominate. Record the numbers, make one change, and measure again. Without that discipline, it is easy to add complexity that gains nothing.
Make dispatch cheap
Dispatch means choosing what to do for the current instruction. A long chain of comparisons tests many conditions before it reaches the right one. Better options include:
- A lookup table, such as a dictionary or array that maps a character to a function.
- A switch statement in languages where the compiler turns it into a jump table.
- Putting the most common instructions first, if you do keep a chain.
The speed difference depends on the language, so test in yours. In some languages a table of function calls is no faster than a well-ordered chain.
Decode cells once
Each step, the interpreter reads a character and works out what it means. For a given cell this work is the same every time, so you can store the decoded form: for example, a small object or number that names the operation, or the numeric value of a digit. A decoded copy of the grid is built once at load time, and the main loop uses it instead of the characters.
There is one important catch. Grid programs can write to their own cells, as covered in the topic of self-modifying code. When a write happens, the decoded entry for that cell must be updated as well. The simplest rule is to route all writes through a single function that updates both the character and its decoded form. If the interpreter forgets this, the program will run old instructions that no longer exist in the grid, and the bug will be hard to spot. A test program that overwrites a cell and then runs it protects against that.
Precompute straight-line runs and jumps
A pointer moving in a straight line through plain instructions visits many cells in a row. If the grid has not changed, the interpreter can work out in advance where each such run stops, for instance at the next direction-changing instruction, and skip ahead. This is a small step toward the kind of block analysis a grid compiler does.
A related trick is to precompute the skip distance for jump instructions, so the trampoline instruction does not need to step through cells one at a time. Precomputed tables are only valid until the grid changes, so these optimizations suit programs that never write to executed cells. A common approach is to detect the first write to code and fall back to the slow, safe path from then on.
Reduce work in the loop
Small things add up when a loop runs millions of times:
- Keep state in local variables instead of object attributes, if your language makes locals quicker.
- Avoid creating temporary objects, such as tuples, on every step.
- Replace the remainder used for wrap-around by a comparison. Check whether the position has gone past an edge and adjust it only then.
- Make the stack a plain list or array with an index, instead of a heavier structure.
- Avoid formatting or logging when tracing is off, including building strings that are never printed.
Output and input costs
Printing one character at a time through an unbuffered stream can be far slower than the computation itself. Collect output in a buffer and write it in chunks, taking care to flush before input reads, as described under interpreter input output. When a program is slow only because it prints a lot, no loop optimization will help.
Choosing a different tool
If a fast host language is available, the same interpreter written in it may be faster with no clever tricks. A compiler that translates the grid into another language removes decoding costs entirely. Both involve more effort, and both should be weighed against the actual need.
A sensible order
- Write tests and get correct behavior.
- Profile on a few real programs.
- Fix the biggest cost, such as dispatch or output.
- Add caching only with a plan for invalidation.
- Re-run the tests and measure again.
Stop when the program is fast enough. Extra speed rarely justifies code that is harder to understand.