代码之家 › 专栏 › 技术社区 › Sam

jvm如何优化循环代码?

jvm optimization algorithm string java

Sam · 技术社区 · 7 年前

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

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优化策略优化我们的代码?

希望有人帮忙,谢谢:)

3 回复 | 直到 6 年前

Mike Strobel 6 年前

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

有很多因素会影响代码的JIT编译方式。例如,调整方法的大小可能会影响内联树,这可能意味着更好或更差的性能,具体取决于调用堆栈的外观。如果一个方法内联到调用堆栈的更高层,它可能会阻止嵌套的调用站点内联到同一框架中。如果这些嵌套的呼叫站点特别“热门”,那么增加的呼叫开销可能会很大。我并不是说这就是原因;我只是指出,有许多阈值控制JIT如何安排代码,性能差异的原因并不总是显而易见的。

将JMH用于基准测试的一个好处是,可以通过显式设置内联边界来减少此类更改的影响。但你可以使用 -XX:CompileCommand

当然,还有其他因素,如缓存友好性,需要更直观的分析。考虑到你的基准可能没有特别深入的调用树,我倾向于将缓存行为作为更可能的解释。我猜你的第二个版本表现更好,因为你的比较对象( pattern )通常在一级缓存中,而第一个版本会导致更多的缓存搅动。如果您的输入很长(听起来好像很长),那么这就是一种可能的解释。如果不是,原因可能更为微妙,例如,您的第一个版本可能会“欺骗”CPU使用更具攻击性的缓存预取,但实际上伤害性能(至少对于您正在进行基准测试的输入)。无论如何,如果要解释缓存行为,那么我想知道为什么在C版本中看不到类似的差异。编译C版本时使用的优化标志是什么?

消除死代码也可能是一个因素。我必须看看您的输入是什么,但您的手动优化版本可能会导致某些指令块在插入指令的解释阶段永远不会被命中,从而导致JIT将其从最终组装中排除。

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

Máº¡nh Quyáº¿t Nguyá»n 7 年前

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

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

在第一个版本中,您必须检查 j < patternLength 在比较第一个字符之前,为每个i。

在第二个版本中,您不需要这样做。

但奇怪的是,我认为对于较小的输入,它并没有带来太大的不同。

您能否分享您用于基准测试的项目的长度?

Baski 7 年前

“循环展开”或“循环展开”

应该跳出去。同样,基准测试很棘手。你会发现同样的问题有很多答案。