Brainfuck Interpreter: Slower than a Snail?

Question

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

1. Removes all non-command characters
2. Optimizes commands (removing +- and <> pairs)
3. Executes each command one-by-one

Speed:

1. 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 < len; i++) {
            switch (commands[i]) {
            case '+':
                bfMemory[pointer]++;
                break;
            case '-':
                bfMemory[pointer]--;
                break;
            case '<':
                if (--pointer == -1) {
                    pointer += BF_MEMORY_SIZE;
                }
                break;
            case '>':
                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 = indexOfMatchingOpenBracket(commands, i);
                }
            }
        }
    }

    private static boolean hasErrors(String bfCode) {
        // each [ must have a ]
        char[] commands = bfCode.toCharArray();
        int diff = 0;
        for (char command : commands) {
            if (command == '[') {
                diff++;
            } else if (command == ']') {
                diff--;
            }
            if (diff < 0) {
                return false;
            }
        }
        return diff != 0;
    }

    private static int indexOfMatchingCloseBracket(char[] commands, int currentIndex) {
        int index = currentIndex;
        int numOfOpeningBrackets = 1;
        while (numOfOpeningBrackets != 0) {
            index++;
            if (commands[index] == ']') {
                numOfOpeningBrackets--;
            } else if (commands[index] == '[') {
                numOfOpeningBrackets++;
            }
        }
        return index;
    }

    private static int indexOfMatchingOpenBracket(char[] commands,
            int currentIndex) {
        int index = currentIndex;
        int numOfClosingBrackets = 1;
        while (numOfClosingBrackets != 0) {
            index--;
            if (commands[index] == ']') {
                numOfClosingBrackets++;
            } else if (commands[index] == '[') {
                numOfClosingBrackets--;
            }
        }
        return index;
    }

}

BFCode.java

public class BFCode {

    private final String code;

    public BFCode(String code) {
        this.code = code;
    }

    public String getCode() {
        return code;
    }

    public String getOptimizedCode() {
        return BFOptimizer.optimize(code);
    }

}

BFOptimizer.java

public class BFOptimizer {

    public static final String NOT_BF_REGEX = "[^\\Q><+-.,[]\\E]";
    public static final String EMPTY_STRING = "";

    public static String optimize(String bfCode) {
        bfCode = bfCode.replaceAll(NOT_BF_REGEX, EMPTY_STRING);
        while (true) {
            String result = bfCode.replaceAll("(\\+\\-)|(\\-\\+)|(<>)|(><)", EMPTY_STRING);
            if (result.equals(bfCode)) {
                return result;
            }
            bfCode = result;
        }
    }

}

Concerns:

1. It's really slow executing each command one-by-one. I was thinking of grouping all same commands together, but that will have to wait until the next revision.
2. Naming?
3. Anything?

Answer 1

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.