A repository to play with different brainfuck implementations.
I am currently working on a jit compiler generator as my bachelor thesis so I wanted to actually implement some jit compilers to get a feeling for it and brainfuck is a small enough language that it suits itself as a target.
In the future I might use this repository to benchmark the generated JIT from my bachelor thesis and compare with other JIT libraries.
At the moment we only have a naive interpreter and a byte code interpreter. I am currently researching how I can include jit libraries to compile the opcodes to machine instructions.
brainint is a naive interpreter that doesn't do any code analysis etc. The only optimization is that it only calculates all jump targets once and caches the results.
brainbyte is a bytecode compiler and interpreter. It archives better performance than brainint by doing code analysis and merging multiple brainfuck instructions into single bytecodes which reduces the overhead of interpreting the instructions.
Here are all the patterns it detects:
- Repeating increment/decrement instructions (
>,<,+,-) are merged into one opcode with an aditional byte storing the count. - Clear loop detection
[-]. - Copy loop detection (something like
[->>+<<]). Copy loops add the value of the current cell to another one. In this example we add the current value to the cell two to the right. - Simple loop
detection (something like
[->>+>-->>+<<<<]). These can be optimized to a series of copy or multiplication opcodes followed by a single clear instruction. Note: clear loops and copy loops are a special case of simple loops. - Jump instructions (
[,]) store with eight bytes which store the target position (this should just as effective as brainint's jump target caching).
For brainbytes OpCodes I was inspired by this article.
braindyn is a jit compiler that uses luajit's DynASM library. It first compiles to the same bytecode as brainbyte but instead of executing it, it compiles the instruction to native x86 or amd64 instructions and later executes them.
One disadvantage of braindyn is that the generated code is written in assembly which limits it to x86 and amd64 and porting to other architectures is quite some work. (Yes it would be possible to port it to arm64 for example but I don't have a computer to test it right now.)
You need the following requirements: clang, ldd (not needed on macOS), cmake, ninja
git submodule update --init
mkdir build
cd build
cmake -G Ninja ..
ninjaAll interpreters/compilers can be invoked the same way, so we just show here how
to use brainint:
./brainint mandelbrot.bf