Brainf*** interpreter optimization excercise (part 3)

In Part 2 I described an attempted optimization to the interpreter that made it slower again.

In this part, we continue with an optimization that does work. And get the runtime of the mandelbrot example from 1 minute and 7 seconds to 43 seconds.

More Jump Tables

In Part 1 I introduced a "jump table".

When the interpreter reached the end of a loop ] it didn't have to search for the opening bracket. The jump table could "instantly" tell it where in the code the loop had to jump to to start the next iteration.

However, when the loop requires no more iterations, the interpreter has to "jump" to the end of the loop (the ] character).

This still happens by iterating through the code until the closing bracket is found and then continuing the execution:

if (memory[pointer] == 0)
{
    while (cr.HasCharacters())
    {
        cr.Forward();
        var tempChar = cr.GetChar();
        if (tempChar == ']' && nesting == 0) { break; }
        if (tempChar == '[') { nesting++; }
        if (tempChar == ']') { nesting--; }
    }
}

Instead of this while loop, it would be nice if we knew where the closing bracket was.

Another jump table would be convenient.

The jump table

In the first part, the jump table was a "Stack". Whenever we reach an opening bracket, we'd "push" the position to the stack.

When we read a closing bracket, we'd "pop" the position from the stack and jump to it directly.

For this "forward jump" table we'll do it a little different.

I'll make a list of positions, the list can contain a position for each location in the source code:

var cr = new CharReader(source);
_jumpTableForward = new int[cr.Length];

Finding the closing bracket

A problem is, since the closing bracket lies further in the code, we don't know where it is yet when we first read the opening bracket and start the loop.

When a loop ends (we have to skip past the end of it), check if there is an ending bracket location in the jump table.

If not, use the previous loop to find the end of the loop. When we reach the end of the loop, we make sure to save the location of the ending bracket. If we then come into the loop again, we'll find it in the lookup table.

case '[':
    var nesting = 0;
    if (memory[pointer] == 0)
    {
        var startPosition = cr.Position;
        if (_jumpTableForward[startPosition] > 0)
        {
            cr.Position = _jumpTableForward[startPosition] - 1;
        } else
        {
            while (cr.HasCharacters())
            {
                cr.Forward();
                var tempChar = cr.GetChar();
                if (tempChar == ']' && nesting == 0) {
                    _jumpTableForward[startPosition] = cr.Position + 1;
                    break;
                }
                if (tempChar == '[') { nesting++; }
                if (tempChar == ']') { nesting--; }
            }
        }
    } else
    {
        jumpTable.Push(cr.Position);
    }
    break;

Results

Running this optimization results in a mandelbrot generated in 43 seconds, coming from 1 minute 7 seconds.

Conclusion

This was a good win, but we didn't really do anything new here. As the optimization is very similar to the first one that was done.

Next, we'll look at an optimization that shaves off a few more seconds.

Still far away from the final 7 seconds.