javabrainfuck

Unoptimized Brainfuck code runs faster than optimized Brainfuck code


I am currently trying to program a Brainfuck interpreter in Java. I try to optimize the Brainfuck code by removing comments and code that is redundant (I use regex for this). However, my unoptimized code runs about a few milliseconds faster than my optimized code, which in my opinion shouldn't even be possible as I am only timing the execution time of the Brainfuck code.

Here's the Brainfuck interpreter itself (ReducedIntStack is basically a self-implementation of a stack):

package io.github.setvizan.brainfuck;

import io.github.setvizan.utils.ReducedIntStack;

public class Interpreter {
    private static final int   MAX_LENGTH = 65535;
    private final        int[] jmp        = new int[MAX_LENGTH];
    private final        int[] arr        = new int[MAX_LENGTH];
    private              int   ptr        = 0;

    public static void interpret(String c) {
        char[]      commands    = c.toCharArray();
        Interpreter interpreter = new Interpreter();
        interpreter.preloadJumpTable(commands);
        interpreter.run(commands);
    }

    private void run(char[] commands) {
        for (int i = -1, size = commands.length; ++i < size; ) {
            switch (commands[i]) {
                case '+':
                    arr[ptr]++;
                    break;
                case '-':
                    arr[ptr]--;
                    break;
                case '<':
                    if (ptr != 0) ptr--;
                    break;
                case '>':
                    ptr++;
                    break;
                case '[':
                    if (arr[ptr] == 0) i = jmp[i];
                    break;
                case ']':
                    if (arr[ptr] != 0) i = jmp[i];
                    break;
                case '.':
                    System.out.print((char) arr[ptr]);
                    break;
            }
        }
    }

    private void preloadJumpTable(char[] commands) {
        ReducedIntStack stk = new ReducedIntStack(MAX_LENGTH);
        for (int i = -1; ++i < commands.length; ) {
            if (commands[i] == '[') {
                stk.push(i);
            } else if (commands[i] == ']') {
                jmp[i] = stk.pop();
                jmp[jmp[i]] = i;
            }
        }
    }
}

Optimizer class:

package io.github.setvizan.brainfuck;

import java.util.regex.Pattern;

public class Optimizer {
    private static final Pattern ENDLESS_LOOP_PATTERN = Pattern.compile("\\[\\]");

    private static final Pattern INCREMENT_DECREMENT_PATTERN = Pattern.compile("\\+-|-\\+");

    private static final Pattern FORWARD_BACKWARD_PATTERN = Pattern.compile("><|<>");

    private static final Pattern REMOVE_USELESS_CHARACTERS = Pattern.compile("[^<>\\.,\\[\\]\\+-]");

    public static String apply(String in) {
        String optimized = in;
        optimized = removeUselessCharacters(optimized);
        optimized = removeEndlessLoops(optimized);
        optimized = removeForwardBackwards(optimized);
        optimized = removeIncrementDecrements(optimized);
        return optimized;
    }

    private static String removeEndlessLoops(String input) {
        return ENDLESS_LOOP_PATTERN.matcher(input).replaceAll("");
    }

    private static String removeIncrementDecrements(String input) {
        return INCREMENT_DECREMENT_PATTERN.matcher(input).replaceAll("");
    }

    private static String removeForwardBackwards(String input) {
        return FORWARD_BACKWARD_PATTERN.matcher(input).replaceAll("");
    }

    private static String removeUselessCharacters(String input) {
        return REMOVE_USELESS_CHARACTERS.matcher(input).replaceAll("");
    }
}

This is how I time my code in Java:

public static void run(String file, boolean optimize){
    File bfFile = new File(file);
    try {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(bfFile));

        String source = bufferedReader.lines().collect(Collectors.joining());
        if (optimize) source = Optimizer.apply(source);
        long t1 = System.nanoTime();
        Interpreter.interpret(source);
        long t2 = System.nanoTime();
        System.out.println("\n"+(t2 - t1) + "ns - this program was optimized? "+optimize);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

I tried to take a file with a lot of comments like (4000 symbols that are not used in Brainfuck and 400 that are used in Brainfuck) and the unoptimized script still runs faster.

I also checked if the Brainfuck interpreter wouldn't really run the optimized version when needed.

I made a script that runs the Java exactly 100 times and the unoptimized was around a full second faster.


Solution

  • Turns out as @Sweeper said, I didn't write my benchmark correctly.
    After setting up JMH and learning how to use it.
    It turns out that the optimized code runs about 0.4ms faster.