Brainf*** interpreter optimization excercise (part 2)

In part 1, I looked at a reference implementation for Brainf*** and a first optimization.

The execution time was reduced from 2 minutes, 16 seconds to 1 minute, 6 seconds.

Now we'll look at another optimization, one that actually didn't work very well.

Optimization 2: Combine instructions

In the code there are a lot of things like this +++++++++++++. This increments the value at the pointer by 1, thirteen times.

So the following code is executed 13 times:

memory[pointer]++;

Not much, but it would make sense to call the following statement instead:

memory[pointer] += 13;

However, to know the value that must be added, we must know how many "+" instructions there are.

So whenever I encountered a "+" I would go through the code further and count how many consequitive "+" instructions follow:

memory[pointer] += GetSumFromSeries(cr, '+');

Cache

In trying to be clever, I also made sure that for one position in the source code, I would only count this once and store it in a cache.

So that if the interpreter reaches the same code twice, it doesn't have to count the + instructions again.

Code

The code for the GetSumFromSeries ended up looking like this:

    public byte GetSumFromSeries(CharReader cr, Char lookupChar)
    {
        var startPosition = cr.Position;
        var cachedCount = _seriesCache[startPosition];

        if (cachedCount != 0)
        {
            cr.Position += cachedCount - 1;
            return cachedCount;
        }

        byte count = 1;

        cr.Forward();
        while (cr.GetChar() == lookupChar) { count += 1; cr.Forward(); }
        cr.Back();

        _seriesCache[startPosition] = count;

        return count;
    }

What happened?

This added a few seconds to the run-time.

The counting of the "+" instructions was more expensive than the simple increments by 1.

It requires keeping a cache and navigating through the code, which added up to costing us more time.

Conclusion

Not every optimization that seems reasonable actually results in a win.

We'll see later how this strategy of combining instructions to one more complex instruction can help though.