jvm如何优化循环代码？

Question

有一种方法可以从文本中搜索子字符串(使用蛮力算法，请忽略空指针)。

public static int forceSearch(String text, String pattern) {
    int patternLength = pattern.length();
    int textLength = text.length();

    for (int i = 0, n = textLength - patternLength; i <= n; i++) {
        int j = 0;
        for (; j < patternLength && text.charAt(i + j) == pattern.charAt(j); j++) {
            ;
        }
        if (j == patternLength) {
            return i;
        }
    }
    return -1;
}

奇怪的是！使用相同的算法，但下面的代码更快！

public static int forceSearch(String text, String pattern) {
    int patternLength = pattern.length();
    int textLength = text.length();

    char first = pattern.charAt(0);
    for (int i = 0, n = textLength - patternLength; i <= n; i++) {
        if (text.charAt(i) != first) {
            while (++i <= n && text.charAt(i) != first)
                ;
        }

        int j = 0;
        for (; j < patternLength && text.charAt(i + j) == pattern.charAt(j); j++) {
            ;
        }
        if (j == patternLength) {
            return i;
        }
    }
    return -1;
}

如果我通过jvm运行第二段代码，那么第二段代码显然要比第一段要快。但是，当我用c写它并运行时，这两个函数的时间几乎相同。所以我认为原因是jvm优化了循环代码

if (text.charAt(i) != first) {
    while (++i <= max && text.charAt(i) != first)
        ;
}

我说的对吗？如果我是对的，我们应该如何使用jvm优化策略来优化我们的代码？

希望有人帮忙，谢谢：)

Answer 1

如果您真的想了解这一点，您可能需要指示JVM打印程序集。根据我的经验，对循环的小调整可能会导致惊人的性能差异。但这不一定是由于循环本身的优化。

有许多因素可以影响您的代码如何编译JIT。例如，调整方法的大小可能会影响您的内联树，这可能意味着性能更好或更差，这取决于调用堆栈的外观。如果方法在调用堆栈上进一步内联，则可能会防止嵌套调用站点内联到同一帧中。如果那些嵌套的呼叫站点特别“热”，则增加的呼叫开销可能很大。我并不是说这就是原因；我只是指出，控制JIT如何安排您的代码的阈值很多，性能差异的原因并不总是很明显。

使用JMH进行基准测试的一个好处是，您可以通过显式设置内联边界来减少此类更改的影响。但是您可以使用-XX:CompileCommand手动实现相同的效果。

当然，还有其他因素，比如缓存友好性，需要更直观的分析。考虑到您的基准可能没有特别深的调用树，我倾向于将缓存行为作为更可能的解释。我想，您的第二个版本表现得更好，因为您的比较器(pattern的第一个块)通常在L1缓存中，而您的第一个版本会造成更多的缓存混乱。如果您的输入是长的(听起来是这样的)，那么这是一个可能的解释。如果不是，原因可能更微妙，例如，您的第一个版本可能是“诱骗”CPU使用更积极的缓存预取，但实际上损害了性能(至少对于您正在基准测试的输入)。无论如何，如果缓存行为是为了解释，那么我想知道为什么在C版本中看不到类似的区别。您用什么优化标志编译C版本？

死代码消除也可能是一个因素。我必须了解您的输入是什么，但是您的手工优化版本可能会导致某些指令块在仪器化解释阶段永远不会被击中，从而导致JIT将它们排除在最终程序集之外。

我重申:如果您想深入了解这一点，您将需要强制JIT为每个版本转储程序集(并与C版本进行比较)。

Answer 2

这个if语句简化了很多工作(特别是当模式在输入字符串的末尾找到时)。

   if (text.charAt(i) != first) {
        while (++i <= n && text.charAt(i) != first)
            ;
    }

在第一个版本中，在比较第一个字符之前，必须检查每个I的j < patternLength。

在第二个版本中，您不需要。

但奇怪的是，我认为对于小的投入，它并没有多大的不同。

你能和我分享一下你用来做基准测试的物品的长度吗？

Answer 3

如果在internet上搜索JVM编译器优化，则

“回路展开”或“回路展开”

应该跳出来。再一次，标杆是很棘手的。你会为同样的问题找到很多这样的答案。