Skip to content

Comparison

Jump to bottom
Kang Seonghoon edited this page Jan 26, 2016 · 1 revision

Comparison

The following list is the comparison of various Brainfuck compilers and optimizers. The implementation listed later provides more advanced optimization compared to the former. I also made some section to describe certain class of optimization.

No optimization at all

This class of optimizer doesn't do any attempt to optimization.

C code generation:

  • dbf2c (date unknown, Daniel B Cristofani) generates POSIX-compatible C code. It doesn't do any optimization. It is written in Brainfuck.
  • BF2C 1.0 (2003, Thomas Cort) generates standard ISO C code. It doesn't do any optimization. There is a same program written in Java.

Other code generation:

  • BF2Java 1.0 (2003, Thomas Cort) generates Java code. It doesn't do any optimization. There is a same program written in Java.

Binary generation:

  • bfcc (1997, Ben Olmstead) generates MS-DOS .COM executable. It prints fixed x86 binary for each commands.

Compression of consecutive commands

This class of optimizer is so far very popular, given the fact that Brainfuck program contains lots of duplicated commands. It should convert +++++[->+++++++<] to something like 5+[->7+<]. It might not be capable to convert >>><<< into no-op, though.

Interpreter:

  • bff 1.0.3.1 (2004, Alex Pankratov) is the fast Brainfuck interpreter written in C. It recognizes the consecutive commands only, but its internal representation is designed to be efficient to generate and also execute.

Binary generation:

  • dbc 1.1 (date unknown, Daniel B Cristofani) generates an executable for Sun machines (SPARC v8). It recognizes the consecutive commands.
  • BF2X86Asm 1.0 (2003, Thomas Cort) generates x86 assembly. It recognizes the consecutive +, -, < and >. It is written in Java.
  • BF2MIPSAsm 1.0 (2003, Thomas Cort) is a same program for MIPS assembly. It is written in Java.

Multi-target compiler:

  • awib 0.1 (2008, Mats Linander) is a multi target compiler: it generates standard ISO C code or Linux executable for IA-32, depending on @TARGET xxx directive in the input code. It is written in Brainfuck (hence the name, Also written in Brainfuck) and one of good Brainfuck compiler written in Brainfuck.

Special casing for cell copy or clear

Another effective optimization is to recognize common idiom: [-] (or [+] if wrapping is allowed) sets the current cell to zero, [>+<-] (or [<<<+>>>-] etc.) copies the current cell to other cell with destructing (i.e. setting to zero) the current cell.

C code generation:

  • wbf2c 0.1-alpha (2007, Chris Wellons) recognizes cell copy and clear, and treats them as single command. It also features multiple Brainfuck program with shared memory for that matters.

Simple loop detection

Simple loop is defined as a loop with the following constraints:

  1. It only has a memory operations: +, -, < and >. Sometimes other simple loop can be recognized inside it.
  2. After the loop body is executed, the memory pointer remains same.
  3. The loop body alters the target (normally the "current") cell by 1 or -1.

Simple loop is very common, as it is used to implement constant multiplication. [-] is also a simple loop, so the optimizer doesn't have to need to special-case it.

Interpreter:

  • bff4 (2004, Oleg Mazonka) is a refinement of aforementioned bff interpreter. Given -DLNR compile option, it recognizes the simple loop (called the linear loop there) too.

Pointer propagation

This class of optimizer flattens out the pointer operation < and > as much as possible. For example, >++++>>>>>--<<<<++>->>+++ may be represented as 1:+4, 2:+2, 3:-1, 5:+3, 6:-2 with final pointer adjustment by 5. This optimization is quite necessary to enable other optimizations.

Multi-target compiler:

  • Hamster BF Compiler 0.4 (2008, Jon Simons) is a multi-target compiler, supporting ISO C, Java, MIPS assembly, MASM IA-16 assembly, and LLVM intermediate language. Its intermediate representation keeps the target cell out of pointer, so it can do some optimizations. Its optimization passes, however, are too basic IMHO. It is written in PLT Scheme.
  • BF Online (date unknown, Frans Faase) generates standard ISO C code. Its pointer propagation seems perfect, but it fails to recognize some obvious nested loops. It is written in Javascript (or ECMAScript if you prefer).

Advanced loop optimization

This class of optimizer recognizes broader range of loops, outlined below:

  1. If loop, which sets the target cell to zero inside it, thus only get executed at most one time.
  2. Repeat loop, whose repeat count is fixed but cannot be flattened. Some complex multiplication loop uses nested loop and cannot be classified as simple.
  3. Almost-simple loop, which is simple except that the target cell is altered by constant but not -1 nor 1. Some almost-simple loop results in the infinite loop (e.g. +[--]), and optimizer should insert some check for it.
  4. Seek loop, whose body moves the pointer by fixed amount. Most common one is [>] or [<], and the former can be replaced by memchr library function in C, for example.

It doesn't need to support all of them, but this list is roughtly sorted by importance so it should optimize at least if loop. Note that optimizing almost-simple loop involves some mathematical (number-theoretic) calculations. :p

C code generation:

  • bf2c.hs (2002, Bertram Felgenhauer) generates standard ISO C code. It recognizes if loop, and it's capable for generating computed adjustment such as data[p+4] += (-3 + (9 * data[p+5]));. It doesn't propagate constants yet. It is written in Haskell.

Postscript (2016): This entire section turns out to be the Scalar Evolution optimization pass. You can probably get a good chunk of dedicated codes for the further inspection.

State-of-the-art optimization

Here I included the most advanced optimizer I have ever seen. Note that I'm using state-of-the-art in the sense of Brainfuck optimization: in my opinion, almost every Brainfuck compiler even doesn't attempt the basic principle of compiler construction. So this measure is quite relative.

C code generation:

  • bfdb 0.02 (2006, David Moews) does great job: it recognizes if loop and almost-simple loop, provides many options controlling execution environment, detects many possible infinite loop and so on. There are some ILs remaining unused (e.g. IT_CheckAnd) and doesn't compile in the recent GCC (you'll have to insert typename somewhere in the code), but it was the most optimizing compiler I could found. It is written in C++.
  • Esotope Brainfuck compiler (2009, Kang Seonghoon) is my attempt to make the most optimizing Brainfuck compiler. It does all optimizations mentioned in this page, and propagates all constants (something other compiler doesn't do). Its goal includes the readable output, so technically this is a decompiler rather than a compiler. It is written in Python.

Postscript (2016)

It seems that there are now a class of BF compilers that leverage mature compiler frameworks like LLVM. It is demonstrated that they are as performant as the Esotope Brainfuck Compiler, and sometimes slightly better. Many optimization techniques applicable to BF are, unfortunately, not really suitable for real world programs and it will need several dedicated optimization passes to make a significant progress there (I had some planned but never managed to write them). I'm currently not aware of such compilers.

Clone this wiki locally