Brainfuck Interpreter: Slower than a Snail?

Inspired by FizzBuzz by Brainfuck, I decided to write an interpreter for Brainfuck. It:

• Removes all non-command characters

• Optimizes commands (removing +- and <> pairs)

• Executes each command one-by-one

Speed:

• FizzBuzz by Brainfuck: about 10 milliseconds

Code:

BFInterpreter.java

```
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BFInterpreter {

public static final int BF_MEMORY_SIZE = 30000;

private static final InputStreamReader INPUT = new InputStreamReader(
System.in);

private static final int BYTE_SIZE = 256;
private static final int HALF_BYTE = BYTE_SIZE / 2;

public static void interpret(BFCode code) {
// Check for errors
if (hasErrors(code.getCode())) {
throw new IllegalArgumentException(
"code has at least one error in it");
}
// -128 = 0, 0 = 128, 127 = 255 etc.
byte[] bfMemory = new byte[BF_MEMORY_SIZE];
Arrays.fill(bfMemory, Byte.MIN_VALUE);
char[] commands = code.getOptimizedCode().toCharArray();
for (int i = 0, pointer = 0, len = commands.length; i ':
if (++pointer == BF_MEMORY_SIZE) {
pointer = 0;
}
break;
case '.':
System.out.print((char) (bfMemory[pointer] + HALF_BYTE));
break;
case ',':
try {
bfMemory[pointer] = (byte) (INPUT.read() - HALF_BYTE);
} catch (IOException e) {
// EOF? no change
}
break;
case '[':
if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0
i = indexOfMatchingCloseBracket(commands, i);
}
break;
case ']':
if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0
i = indexOfMatchingOpenBrack

Performance

It looks like the biggest performance problem is in

case '[':
            if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0
                i = indexOfMatchingCloseBracket(commands, i);
            }
            break;
        case ']':
            if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0
                i = indexOfMatchingOpenBracket(commands, i);
            }

Each time the interpreter hits the bracket, it performs a linear search over the source code. You may want to memoize a target address once the branch is taken.

Bug?

hasErrors returning false on diff < 0 sounds like a bug. The diff < 0 is an error, no?

Missing diagnostics

I'd want to know an exact position of a faulty bracket. In any case, checking for errors prior to execution is questionable. You may consider a interpretation-time exception.

StackExchange Code Review Q#108630, answer score: 7