Have you ever wondered, what is the best performing way to execute some random esoteric programming language? If not, this is the perfect time to do so. Let’s build a simple interpreter running Brainfuck and try to figure out how to make it faster!🚀

Brainfuck

At this point, the programming language Brainfuck is quite well known. It’s a full-on Turing complete language capable of computing any mathematical problem, at least hypothetically. But as the whole point of its design is to be purposefully hard on the programmer to the point of utter impracticability, but still being a real language it definitely deserves to be called esoteric .

If you have ever heard of the term “Turing machine” and the principle by which it works, Brainfuck should be quite easy to grasp. Like a Turing machine, Brainfucks works by interacting with memory cells laid out like a tape of indefinite length. You can only interact with the cell currently selected, and the only thing you can do is increment or decrement its value.

If you want to add or subtract a larger number than just one, you need to do multiple in/decrements in a row. To select another cell, you can only move to one of the two directly neighboring cells. If you want to move by more than one cell, again you have to do multiple moves to the right or left.

Like every command in Brainfuck, these simple instructions are only made up of single characters. Intuitively the operators for inc- and decrement are + and - . Moving the context to the left or right neighboring cell is done using < and > .

To allow a Brainfuck program to make decisions based on data in the cells, loops can be programmed. Brainfuck loops work basically like ‘while’-loops found in C or other programming languages. The loop is only entered if a certain checked condition is met, and the code inside gets executed repeatedly until the condition is false and execution moves on directly after the loop.

Brainfuck uses [ and ] to indicate loops. If an opening bracket is encountered, the currently selected cell is checked whether its value is not zero (like C). If so, the code inside the loop is run. The condition is checked again, to see if the loop should be run again and so on.

Loops can be nested of course, and as the condition can be reset immediately inside the loop, they can act as ‘if’-statements. Furthermore, if the cell context is moved inside the loop the cell checked after each run can be a different one, allowing for pretty complicated setups.

The final thing missing making up this super stripped-down language is input and output. Like before, Brainfuck offers plenty, if an ASCII based shell is all you desire of course. The comma command , allows for reading in a single character from the standard input like your command line, and . will print a single one. By using ASCII, printing a cell containing the number 41 will result in a capital ‘A’ on your screen and the other way around when reading.

A taste of applied Brainfuck

When I first encountered Brainfuck I was kind of confused, how you could achieve anything at all with such simplicity. But later on I got very much intrigued when I learned what is actually possible with just 8 basic operators.

So how do you now write anything “useful” in Brainfuck?

 ++++++++[>++++++<-]++++++++++[>.+<-] 

This program prints out the numbers 0 to 9 to the console. Although being primitive, it is pretty verbose in typical Brainfuck fashion. Let’s examine it and figure out how it does its magic, in case printing numbers is magical to you.

In the beginning, we start of incrementing the first cell eight times before we check if we can enter the following loop. As the cell is containing the number eight now, we enter it and immediately change the currently active cell to the second one, which is incremented six times. Moving on, the context is switched back to the first cell to subtract one from it. Since its value is now seven, we rerun the loop.

This happens six more times until the first cell reaches zero and the interpreter steps out of the loop. Now the second cell contains 48 which is the ‘0’ character in ASCII, as six was added eight times to it. The first cell is then set to 10 and another loop is entered. On every run, the context switches to the second cell first to print it to the console, before incrementing it. Then the first cell, used as a counter, is decremented.

The ASCII code makes writing this program easy because it conveniently lays out all number characters in the correct order from 0 to 9 as code points from 48 to 57. Therefore by incrementing the second cell on every run, the next number is printed out.

++++++++++
[
 >+++++++>++++++++++>+++>+<<<<-
]                       Loop to setup cells
>++.                    Print 'H'
>+.                     Print 'e'
+++++++.                'l'
.                       'l'
+++.                    'o'
>++.                    Print space
<<+++++++++++++++.      'W'
>.                      'o'
+++.                    'r'
------.                 'l'
--------.               'd'
>+.                     '!'
>.                      Print New Line
+++.                    Print Carriage Return

Of course, there is no way we can skip the obligatory “Hello world” program. If you look closely you will see that it works on the same principle as the previous example. First, a loop sets up multiple cells with code points near the ones later used by the message. Then these code points are just adjusted slightly to print out the correct characters.

Running Brainfuck not particularly fast

Let’s get a baseline to start with. Luckily things are easy and building a working Brainfuck interpreter isn’t a large undertaking. There are really only five things to do:

• Load the file with the Brainfuck code
• Make an array representing the cells and a variable that points to the currently selected cell
• Go through each character and check which command it corresponds to
• Implement addition, subtraction, movement of the pointer, and IO
• Implement loops

I will be coding this project in JavaScript with Node, as it allows for some interesting optimizations later on. But if you want to follow along you can use whatever language you like, as most things described are nothing unique to JavaScript or if so could be easily replicated.

// Get the fs module to access the filesystem
const fs= require('fs');

// Load the file
const src= fs.readFileSync('./mandelbrot.b');

//Read every byte inside the buffer
for( let i= 0; i!= src.length; i++ ) {
  const byte= src.readUInt8(i);

  //...
}

First things first, let’s load a file and go through its contents. fs.readFileSync() returns an ArrayBuffer that holds the file data as bytes. We can read each byte at an arbitrary position using readUInt8() .

function main() {
  const data= [ 0 ];
  let ptr= 0;

  for( let i= 0; i!= src.length; i++ ) {
    switch( src.readUInt8(i) ) {
      case ASCII.Plus:
        data[ptr] += 1;
        break;

      case ASCII.Minus:
        data[ptr] -= 1;
        break;

      case ASCII.Left:
        if( !ptr ) {
          throw Error('Pointer underflow');
        }
        ptr--;
        break;

      case ASCII.Right:
        ptr++;
        if( ptr >= data.length ) {
          data.push( 0 );
        }
        break;

      //... -> IO & loops
      

      // Ignore character
      default:
        break;
    }
  }
}

Depending on the byte read we can do multiple cases in a switch-statement. Left and right just change the index ptr , pointing to the currently selected cell. Plus and minus on the other hand inc/decrement said cell. The only thing we have to check is, that when moving the index, we don’t allow for negative values and when moving outside of the bounds of the array we have to increase the array's size, as Brainfuck expects an indefinite number of cells at its disposal.

In and output are also nothing too special. As requesting user input while blocking the execution of the JavaScript program is a pain, I will omit it for now, as none of the programs I show require it anyway. If you use python or any other more sensible language than JS, feel free to implement it. 😉

const ASCII= {
  Plus: 43,     // +
  Minus: 45,    // -
  Dot: 46,      // .
  Comma: 44,    // ,
  Left: 60,     // <
  Right: 62,    // >
  OBracket: 91, // [
  CBracket: 93  // ]
}

Also, having how all the characters correspond to their ASCII codes in a constant like this, is pretty handy.

Now last but definitely not least, we need loops and for now I will keep it simple. Whenever the interpreter reaches an opening bracket it checks whether the current cell is not zero. If this is the case, the loops inner block of code is entered and the following character gets evaluated. More interesting stuff happens, if the cell is zero and the loop has to be skipped. Then the interpreter has to find the closing bracket that belongs to the head of the loop. As loops can be nested, the interpreter, therefore, has to keep track of how many more open brackets it encounters until it reaches the correct closing one.

  case ASCII.OBracket:
    // Jump over loop if current cell is 0
    if( !data[ptr] ) {

      // Count the number of inner loops to find matching ]
      let ctr= 0;
      while( i!= src.length ) {
        const c= src.readUInt8(i);

        // Inner loop starts
        if( c === ASCII.OBracket ) {
          ctr++;

        // (Inner) loop ends
        } else if(  c === ASCII.CBracket ) {
          if( !--ctr ) {
            break;
          }
        }
        i++;
      }
    }
    break;

The same principle applies when reaching the end of a loop. Either step out of the loop and evaluate the following character if the current cell is zero, else find the corresponding opening bracket by searching in reverse direction to restart the loop.

  case ASCII.CBracket:
    // Find the begin of the loop if the current cell is not 0
    if( data[ptr] ) {

      let ctr= 0;
      while( i > 0 ) {

        const c= src.readUInt8(i);
        if( c === ASCII.CBracket ) {
          ctr++;
        } else if(  c === ASCII.OBracket ) {
          if( !--ctr ) {
            break;
          }
        }
        i--;
      }
    }
    break;

Mandelbrot madness

Since we now wield the power of brainfuck, a suitable program written in this fine language is required to show the world the superior computing performance of such a program and moreover test our interpreter.

As I want to measure the execution speed our little interpreter reaches while we improve it over time a large program with lots of computing and many loops is needed. A great project that’s this long and hard to run is the Mandelbrot renderer written by Erik Bosman that prints out the famous fractal image as ASCII art.

If you follow the link above, you can't only get different versions of the renderer, that draw the fractal in various sizes, but also look at the source code. It is written in C/C++ Macros utilizing the Preprocessor as a kind of compiler. I don’t know what’s more mind-boggling, the program itself or the fact that it’s created with C-Macros of all things. Commonly known as the most evil thing in the realm of programming.

To time the execution duration I threw together the probably most basic performance testing system the world has ever seen. It uses the performance.now() function to get a high-resolution timestamp before and after calling a provided function.

const {performance}= require('perf_hooks');

function meassure( fn ) {
  // Time a single run
  const a= performance.now();

  fn();

  return performance.now()- a;
}

function benchmark( fn, num= 100 ) {
  // Time multiple runs
  let accu= 0, min= Number.POSITIVE_INFINITY, max= 0, x= num;
  const arr= new Array(num);

  while( x-- ) {
    const t= meassure( fn );
    arr[num-x-1]= t;
    accu+= t;
    min= Math.min( min, t );
    max= Math.max( max, t );
  }

  accu /= num;

  console.log('Avg:', accu+ 'ms');
  console.log('Min:', min+ 'ms');
  console.log('Max:', max+ 'ms');

  return arr;
} 

// Timing 'main' 10 times
benchmark( main, 10 ).forEach( t => console.log(t) );

To get a more accurate result I take an average value from ten runs. Loading the source code from disk is not included as I’m solely interested in the execution speed.

As you can see, the first run is considerably slower. My guess is the fact that v8, the JavaScript runtime used by Node, takes the first execution to generate the fully optimized version of the JITed code. But even seven seconds are unexpectable and definitely don’t live up to the standard that Brainfuck deserves. Therefore, we will look at the generation of byte code in the next article in this series. Stay tuned!

Closing note:
Finally, my first article is here! Like most of the things I do, it took way too long to complete. I hope the result didn’t turn out too rambly.
On the state of the webpage itself, there is still a lot of work left to do. Tobias and I have many ideas that we would like to implement.