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.
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.