Java:手动展开的循环仍然比原始循环快。为什么？

Question

考虑以下两个长度为 2 的数组的代码片段:

boolean isOK(int i) {
    for (int j = 0; j < filters.length; ++j) {
        if (!filters[j].isOK(i)) {
            return false;
        }
    }
    return true;
}

和

boolean isOK(int i) {
     return filters[0].isOK(i) && filters[1].isOK(i);
}

我会假设这两个部分的性能在充分热身后应该是相似的。
我已经使用 JMH 微基准测试框架检查了这一点，如所述，例如 here和 here并观察到第二个片段的速度快了 10% 以上。

问题:为什么 Java 没有使用基本的循环展开技术优化我的第一个代码段？
特别是，我想了解以下内容:

我可以轻松生成最适合 2 个过滤器的代码，并且在其他数量的过滤器的情况下仍然可以工作(想象一个简单的构建器):return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters) . JITC 可以这样做吗？如果不能，为什么？

JITC 能否检测到 'filters.length==2' 为 最常见的情况并在一些热身后生成最适合这种情况的代码？这应该几乎与手动展开的版本一样最佳。

JITC 能否检测到特定的 实例 使用非常频繁，然后生成代码 对于这个特定的实例 (它知道过滤器的数量总是2)？ 更新:得到的答案是 JITC 仅在类(class)级别上工作。好的，我知道了。

理想情况下，我希望得到对 JITC 工作原理有深刻理解的人的回答。

基准运行详细信息:

在最新版本的 Java 8 OpenJDK 和 Oracle HotSpot 上试过，结果差不多

使用的 Java 标志:-Xmx4g -Xms4g -server -Xbatch -XX:CICompilerCount=2(没有花哨的标志也得到类似的结果)

顺便说一句，如果我只是在一个循环中运行数十亿次(不是通过 JMH)，我会得到类似的运行时间比率，即第二个片段总是明显更快

典型的基准输出:

Benchmark (filterIndex) Mode Cnt Score Error Units
LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44.202 ± 0.224 ns/op
LoopUnrollingBenchmark.runBenchmark 1 avgt 400 38.347 ± 0.063 ns/op

(第一行对应于第一个片段，第二行对应于第二个。

完整的基准代码:

public class LoopUnrollingBenchmark {

    @State(Scope.Benchmark)
    public static class BenchmarkData {
        public Filter[] filters;
        @Param({"0", "1"})
        public int filterIndex;
        public int num;

        @Setup(Level.Invocation) //similar ratio with Level.TRIAL
        public void setUp() {
            filters = new Filter[]{new FilterChain1(), new FilterChain2()};
            num = new Random().nextInt();
        }
    }

    @Benchmark
    @Fork(warmups = 5, value = 20)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public int runBenchmark(BenchmarkData data) {
        Filter filter = data.filters[data.filterIndex];
        int sum = 0;
        int num = data.num;
        if (filter.isOK(num)) {
            ++sum;
        }
        if (filter.isOK(num + 1)) {
            ++sum;
        }
        if (filter.isOK(num - 1)) {
            ++sum;
        }
        if (filter.isOK(num * 2)) {
            ++sum;
        }
        if (filter.isOK(num * 3)) {
            ++sum;
        }
        if (filter.isOK(num * 5)) {
            ++sum;
        }
        return sum;
    }


    interface Filter {
        boolean isOK(int i);
    }

    static class Filter1 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 3 == 1;
        }
    }

    static class Filter2 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 7 == 3;
        }
    }

    static class FilterChain1 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            for (int j = 0; j < filters.length; ++j) {
                if (!filters[j].isOK(i)) {
                    return false;
                }
            }
            return true;
        }
    }

    static class FilterChain2 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            return filters[0].isOK(i) && filters[1].isOK(i);
        }
    }

    private static Filter[] createLeafFilters() {
        Filter[] filters = new Filter[2];
        filters[0] = new Filter1();
        filters[1] = new Filter2();
        return filters;
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

Answer 1

TL;DR 这里性能差异的主要原因与循环展开无关。而是类型推测 和 内联缓存 .

展开策略

事实上，在 HotSpot 术语中，这样的循环被视为 计数 , 在某些情况下 JVM 可以展开它们。但不是你的情况。

HotSpot 有两种循环展开策略: 1) 最大程度地展开，即完全移除循环；或 2) 将几个连续的迭代粘合在一起。

只有在 exact number of iterations is known .

  if (!cl->has_exact_trip_count()) {
    // Trip count is not exact.
    return false;
  }

但是，在您的情况下，该函数可能会在第一次迭代后提前返回。

可能会应用部分展开，但 following condition休息展开:

  // Don't unroll if the next round of unrolling would push us
  // over the expected trip count of the loop.  One is subtracted
  // from the expected trip count because the pre-loop normally
  // executes 1 iteration.
  if (UnrollLimitForProfileCheck > 0 &&
      cl->profile_trip_cnt() != COUNT_UNKNOWN &&
      future_unroll_ct        > UnrollLimitForProfileCheck &&
      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
    return false;
  }

由于在您的情况下，预期的行程计数小于 2，HotSpot 认为即使是两次迭代也不值得展开。请注意，第一次迭代无论如何都会被提取到预循环中( loop peeling optimization)，所以展开在这里确实不是很有用。

类型推测

在您展开的版本中，有两个不同的 invokeinterface字节码。这些站点有两种不同的类型配置文件。第一个接收者总是 Filter1 ，第二个接收者总是 Filter2 .所以，你基本上有两个单态调用站点，HotSpot 可以完美地内联这两个调用——所谓的“内联缓存”，在这种情况下具有 100% 的命中率。

使用循环，只有一个 invokeinterface字节码，只收集一种类型的配置文件。 HotSpot JVM 看到 filters[j].isOK()用 Filter1 调用 86% 次接收器和 14% 次与 Filter2接收者。这将是一个双态调用。幸运的是，HotSpot 也可以推测内联双态调用。它使用条件分支内联两个目标。但是，在这种情况下，命中率最多为 86%，并且性能会受到架构级别相应的错误预测分支的影响。

如果您有 3 个或更多不同的过滤器，情况会更糟。在这种情况下 isOK()将是一个 HotSpot 根本无法内联的超多态调用。因此，编译后的代码将包含一个真正的接口(interface)调用，这会对性能产生更大的影响。

更多关于投机内联的文章 The Black Magic of (Java) Method Dispatch .

结论

为了内联虚拟/接口(interface)调用，HotSpot JVM 收集每个调用字节码的类型配置文件。如果循环中有虚拟调用，则无论循环是否展开，都将只有一种类型的调用配置文件。

为了从虚拟调用优化中获得最佳效果，您需要手动拆分循环，主要是为了拆分类型配置文件。到目前为止，HotSpot 无法自动执行此操作。