Stream: compiler development

Topic: bf interpreter analysis

Ayaz Hafiz (Jul 18 2023 at 20:00):

Looking at #beginners > Help optimising my BF interpreter - a few things I think we should be able to address hopefully easily

1. the tokinizer step compiles to a very poor if/else chain rather than a switch (https://gist.github.com/ayazhafiz/9669cbf36cf33001f794a0cab4db95f5). I think we should be able to eliminate the decs on constant strings here as well (https://github.com/roc-lang/roc/issues/5594)

Ayaz Hafiz (Jul 18 2023 at 20:02):

looking at the compilation of run: https://gist.github.com/ayazhafiz/edfb055da1082f8f42f352846222bd3e
I think we would benefit strongly from even naive LICM, escape analysis, and inline passes. If we inline List.get and run LICM we should be able to see that Interpreter.221 can be hoisted outside the joinpoint, needs no inc, and the bounds check can be hoisted as well

Qqwy / Marten (Jul 18 2023 at 20:30):

The interpreter is currently written in an indirect-threaded/subroutine-threaded style rather than in a direct-threaded style.

Or at least the compiled code looks this way (every branch has its own call to goToNextCommand)

I wonder whether the performance of a version of the code where goToNextCommand |> run is moved outside of the whenis different or not. An inlining or duplicate code removal pass would do that automatically.

Qqwy / Marten (Jul 18 2023 at 20:51):

Folkert asked about the different ways blocks (the BF equivalent of loops) are implemented in various BF interpreters.
I had to refresh my memory on it, but seems like the main two ways are (according to a brief skimming of RosettaCode):

• whenever a [ is encountered and you need to skip to the ], read every next byte until the matching ] is encountered at runtime and vice-versa (slow but simple)
• do a pass over the program beforehand to build up a separate dictionary structure whose keys are the cells containing a [ and whose values are the matching ]. Jumping [ to ] is done by looking in this dictionary. Keeping track of the [ matching a ] is even simpler because you're certain to have passed the matching [ before, so you can add the location to a [ on a stack and pop from this stack when you encounter a ]. (little more involved, but much faster)

I have not seen the technique of turning the BF AST into a tree before or elsewhere, though it is of course a very popular approach when interpreting any more complicated language :D

Last updated: Jul 06 2025 at 12:14 UTC