Java性能：manuallyunrolled循环仍然比原始循环快。为什么？

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没有使用基本循环展开技术优化我的第一个代码片段
我特别想了解以下几点：

1. 我可以很容易地生成一个代码，该代码对于两个过滤器的情况是最佳的，并且仍然可以在另一个过滤器的情况下工作（想象一个简单的构建器）：
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)。JITC能做到同样的事情吗？如果不能，为什么
2. JITC能否检测到“过滤器。length==2'是最常见的情况并且在一些预热后生成最适合这种情况的代码？这应该和手动展开的版本一样好
3. JITC能否检测到一个特定的实例被频繁使用，然后为这个特定实例生成一个代码（它知道过滤器的数量总是2）
   更新：得到的答案是JITC只在类级别上工作。好的，明白了

理想情况下，我希望能从对JITC工作原理有深入了解的人那里得到答案

基准运行详细信息：

• 在最新版本的Java8OpenJDK和OracleHotSpot上试用，结果类似
• 使用的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这里性能差异的主要原因与循环展开无关。而是类型推测和内联缓存

展开策略

事实上，在热点术语中，这样的循环被视为计数的，在某些情况下，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%，被Filter2接收器调用的次数为14%。这将是一个双晶型呼叫。幸运的是，HotSpot也可以推测地内联双晶型调用。它使用条件分支将两个目标内联。然而，在这种情况下，命中率将最多为86%，并且性能将受到架构级别上相应的预测失误分支的影响

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

更多关于投机性内联的信息，请参阅文章The Black Magic of (Java) Method Dispatch

结论

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

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

Answer 2

所呈现的循环可能属于“未计数”循环类别，这些循环的迭代计数既不能在编译时确定，也不能在运行时确定。这不仅是因为@Andreas关于数组大小的争论，还因为随机条件break（我写这篇文章时，你的基准测试中就有这个）

最先进的编译器不会太过激进 优化它们，因为展开未计数的循环通常需要 复制循环的退出条件，这样只会改善 如果后续的编译器优化能够 优化展开的代码。查看此2017 paper了解他们在哪里提出如何展开此类内容的建议的详细信息

由此可知，您的假设并不支持您对循环进行了某种“手动展开”。您将其视为一种基本的循环展开技术，可以将具有条件中断的数组上的迭代转换为&&链式布尔表达式。我认为这是一个非常特殊的情况，惊奇地发现一个热点优化程序正在进行一个复杂的重构。{a2}他们正在讨论它实际上可能做什么，也许{a3}很有趣

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

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

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

如果你想获得更多的确定性，可以使用jitwatch分析器/可视化工具来分析实际的Jit操作，包括机器代码(github){a6}。如果最终有什么事情要看，我会相信我自己的眼睛，而不是关于JIT通常可以做什么或不可以做什么的任何意见，因为每种情况都有它的具体情况Here他们担心就JIT而言，很难就具体案例得出一般性陈述，并提供了一些有趣的链接

由于您的目标是最小运行时间，a && b && c ...表单可能是最有效的一种，如果您不想依赖于循环展开的希望，至少比目前介绍的任何其他表单都更有效。但你不能用一般的方式来表达。函数组合为java.util.Function时，又会产生巨大的开销（每个函数都是一个类，每个调用都是一个需要分派的虚拟方法）。也许在这种情况下，颠覆语言级别并在运行时生成custom byte code是有意义的。另一方面，字节码级别的&&逻辑requires branching也可能相当于if/return（在没有开销的情况下也无法泛化）