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

Alexander 10 java optimization performance jit

考虑下面两个长度为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);
    }
}

gurioso.. 11

呈现的循环可能属于“非计数”循环类别,即无法在编译时或在运行时确定其迭代计数的循环。不仅因为有关数组大小的@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(也不能没有开销就不能生成)。


apangin.. 5

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无法自动执行此操作。