未优化的Brainfuck代码为何比优化后的运行更快？

你遇到的核心矛盾是：通过正则移除注释和冗余代码后，Brainfuck代码的解释执行时间反而比未优化版本更长，多次测试后未优化版本总耗时少约1秒。结合你的代码实现，以下是具体原因分析和解决建议：

核心原因：跳转表构建的开销抵消了执行收益 #

你的计时范围包含了Interpreter.interpret的全部逻辑，而其中的preloadJumpTable方法是关键影响因素：

• 未优化代码：虽然字符总数多（4400个），但绝大多数是注释字符，preloadJumpTable遍历过程中只有极少数[/]需要栈操作，几乎是“空遍历”，耗时极短。
• 优化后代码：字符总数减少到400个，但有效指令（尤其是[/]）的密度大幅提升，preloadJumpTable需要频繁执行栈的push/pop操作，这部分开销远超过了run阶段因循环次数减少节省的时间，最终导致总耗时更高。

此外还有两个次要因素：

1. JIT编译的差异：未优化代码中大量无效字符的连续出现，JIT可能会生成“批量跳过无效字符”的高效优化代码；而优化后代码每个循环迭代都要处理分支逻辑，JIT优化空间反而更小。
2. 自行实现的栈性能：你使用的ReducedIntStack如果没有做足够的性能优化，频繁的push/pop操作会比JDK自带的栈（如ArrayDeque）产生更高开销。

解决建议 #

1. 拆分计时，定位耗时瓶颈 #

修改interpret方法，分别统计跳转表构建和代码执行的耗时，确认瓶颈所在：

public static void interpret(String c) {
    char[] commands = c.toCharArray();
    Interpreter interpreter = new Interpreter();
    
    // 单独统计跳转表构建时间
    long preloadStart = System.nanoTime();
    interpreter.preloadJumpTable(commands);
    System.out.println("跳转表构建耗时：" + (System.nanoTime() - preloadStart) + "ns");
    
    // 单独统计执行时间
    long runStart = System.nanoTime();
    interpreter.run(commands);
    System.out.println("代码执行耗时：" + (System.nanoTime() - runStart) + "ns");
}

2. 优化跳转表构建逻辑 #

• 替换自定义栈：将ReducedIntStack换成JDK自带的ArrayDeque<Integer>，它的栈操作经过JVM优化，性能更稳定。
• 提前收集跳转标记：在优化代码阶段就记录[/]的位置，直接生成跳转表，避免解释器二次遍历。

3. 重构优化器，替代正则替换 #

当前的多次正则替换不仅生成中间字符串，还无法合并连续的冗余指令（如+++可以直接保留为+++，而非只抵消单个+-）。改为手动遍历优化，效率更高：

public static String apply(String in) {
    StringBuilder sb = new StringBuilder();
    int len = in.length();
    int i = 0;

    while (i < len) {
        char c = in.charAt(i);
        switch (c) {
            // 合并连续的增减指令
            case '+':
            case '-':
                int delta = 0;
                while (i < len && (in.charAt(i) == '+' || in.charAt(i) == '-')) {
                    delta += in.charAt(i) == '+' ? 1 : -1;
                    i++;
                }
                if (delta > 0) sb.append("+".repeat(delta));
                else if (delta < 0) sb.append("-".repeat(-delta));
                break;
            // 合并连续的指针移动指令
            case '>':
            case '<':
                int ptrDelta = 0;
                while (i < len && (in.charAt(i) == '>' || in.charAt(i) == '<')) {
                    ptrDelta += in.charAt(i) == '>' ? 1 : -1;
                    i++;
                }
                if (ptrDelta > 0) sb.append(">".repeat(ptrDelta));
                else if (ptrDelta < 0) sb.append("<".repeat(-ptrDelta));
                break;
            // 保留有效指令
            case '[':
            case ']':
            case '.':
                sb.append(c);
                i++;
                break;
            // 跳过注释
            default:
                i++;
                break;
        }
    }

    // 移除空循环
    String result = sb.toString();
    while (result.contains("[]")) {
        result = result.replace("[]", "");
    }
    return result;
}

4. 优化解释器执行逻辑 #

将有效指令提前过滤为指令数组，避免run阶段遍历无效字符：

// 先过滤出有效指令
public static List<Character> filterValidCommands(String source) {
    List<Character> commands = new ArrayList<>();
    for (char c : source.toCharArray()) {
        if ("<>+-[].".indexOf(c) != -1) {
            commands.add(c);
        }
    }
    return commands;
}

// 修改解释器接收指令列表
public static void interpret(List<Character> commands) {
    char[] cmdArr = new char[commands.size()];
    for (int i = 0; i < commands.size(); i++) {
        cmdArr[i] = commands.get(i);
    }
    Interpreter interpreter = new Interpreter();
    interpreter.preloadJumpTable(cmdArr);
    interpreter.run(cmdArr);
}

内容的提问来源于stack exchange，提问作者Setvizan