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微基准测试框架（如此处和此处所述）进行了检查，并观察到第二个片段的运行速度提高了10％以上。

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

1. 我可以很容易地产生一个代码，为2个滤波器的情况下最佳的，仍然可以在过滤器另一个号码的情况下工作（想象一个简单的建造者）：
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)。JITC可以这样做吗？如果不能，为什么？
2. JITC是否可以检测到'filters.length == 2 '是最常见的情况，并在预热后产生最适合这种情况的代码？这应该几乎与手动展开的版本一样最佳。
3. JITC是否可以检测到某个特定实例被非常频繁地使用，然后为该特定实例生成代码（对于该实例，它知道过滤器的数量始终为2）？

理想情况下，我想从对JITC的工作有深刻理解的人那里得到答案。

基准运行细节：

• 在最新版本的Java 8 OpenJDK和Oracle HotSpot上进行了尝试，结果相似
• 使用的Java标志：-Xmx4g -Xms4g -server -Xbatch -XX：CICompilerCount = 2（在没有花哨标志的情况下也得到了类似的结果）
• 顺便说一句，如果我简单地在一个循环中运行数十亿次（而不是通过JMH），我将获得类似的运行时比率，即第二个片段总是明显更快

典型基准输出：

基准（filterIndex）模式Cnt得分错误单位
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

呈现的循环可能属于“非计数”循环类别，即无法在编译时或在运行时确定其迭代计数的循环。不仅因为有关数组大小的@Andreas参数，还因为随机条件break（在我撰写本文时，它曾经在您的基准测试中使用）。

最先进的编译器不会积极地优化它们，因为展开非计数循环通常还涉及复制循环的退出条件，因此，只有在后续的编译器优化可以优化展开的代码时，它才能提高运行时性能。请参阅此2017年论文，以了解他们在提案中也提出如何展开此类内容的详细信息。

由此可见，您的假设并不意味着您确实进行了循环的“手动展开”。您正在考虑它是一种基本的循环展开技术，用于将具有条件中断的数组上的迭代转换为&&链接的布尔表达式。我认为这是一个非常特殊的情况，如果发现一个热点优化器可以动态地进行复杂的重构，我会感到惊讶。在这里，他们正在讨论它实际上可能会做什么，也许此参考很有趣。

这将更紧密地反映当代展开的机制，也许仍远未达到展开的机器代码的样子：

if (! filters[0].isOK(i))
{
   return false;
} 
if(! filters[1].isOK(i))
{
   return false;
}
return true;

您得出的结论是，由于一段代码的运行速度比另一段代码的运行速度快，因此循环没有展开。即使这样做，由于您正在比较不同的实现，您仍然可以看到运行时差异。

如果您想获得更多的确定性，可以使用实际的Jit操作的jitwatch分析器/可视化器，包括机器代码（github） （演示幻灯片）。如果最终有什么值得一看的东西，那么我会比其他任何人都更相信JIT，因为每种情况都有其具体情况，因此我对JIT总体上可能会或可能不会做什么有任何看法。在这里，他们担心就JIT而言很难得出针对特定案例的一般性陈述，并提供了一些有趣的链接。

由于您的目标是最小化运行时，因此a && b && c ...，如果您不想依靠循环展开的希望，那么该表单可能是最高效的表单，至少比其他任何形式的表单效率更高。但是您不能以一般的方式拥有它。有了java.util.Function的函数组成，再次会有巨大的开销（每个Function是一个类，每个调用都是需要调度的虚拟方法）。也许在这种情况下，在运行时破坏语言级别并生成自定义字节代码可能是有意义的。另一方面，&&逻辑也需要在字节码级别上分支，并且可能等效于if / return（也不能没有开销就不能生成）。

Answer 2

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

展开策略

实际上，在HotSpot术语中，此类循环被视为counted，并且在某些情况下JVM 可以展开它们。不过，您的情况并非如此。

HotSpot有两种循环展开策略：1）最大化展开，即完全删除循环；或2）将几个连续的迭代粘合在一起。

只有知道确切的迭代次数，才能进行最大展开。

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

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

可能会应用部分展开，但是以下条件会中断展开：

  // 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假设即使展开两次迭代也不值得。请注意，无论如何，第一个迭代都被提取到了预循环中（循环剥离优化），因此在这里展开确实不是很有益。

类型推测

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

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

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

“（Java）方法派遣的黑魔法 ”一文中有关投机内联的更多信息。

结论

为了内联虚拟/接口调用，HotSpot JVM按调用字节码收集类型概要文件。如果循环中存在虚拟调用，则无论循环是否展开，该调用都只有一个类型配置文件。

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