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

2022-09-04 07:45:54

考虑长度为 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个过滤器的情况是最佳的,并且在另一个过滤器的情况下仍然可以工作(想象一个简单的构建器):
    。JITC可以做同样的事情吗,如果没有,为什么?return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)
  2. JITC能否检测到“filters.length==2”是最常见的情况,并在预热后生成最适合这种情况的代码?这应该几乎与手动展开的版本一样最佳。
  3. JITC 能否检测到特定实例的使用非常频繁,然后为此特定实例生成代码(它知道筛选器的数量始终为 2)?
    更新:得到一个答案,JITC只在类级别工作。好的,知道了。

理想情况下,我希望从对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);
    }
}

答案 1

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

最先进的编译器不会主动优化它们,因为展开非计数循环通常还涉及复制循环的退出条件,因此,如果后续编译器优化可以优化展开的代码,则只会提高运行时性能。请参阅这篇2017年的论文,了解他们提出如何展开此类内容的建议的详细信息。

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

这将更接近当代展开的机制,并且可能仍然远不及展开的机器代码的样子:

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

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

如果你想获得更多的确定性,有一个jitwatch分析器/可视化工具,可以分析实际的Jit操作,包括机器代码(github)(演示幻灯片)。如果最终有什么要看的,我会更相信自己的眼睛,而不是任何关于JIT可能做什么或可能不会做什么的意见,因为每个案例都有其具体细节。在这里,他们担心就JIT而言,很难为特定情况达成一般陈述,并提供一些有趣的链接。

由于您的目标是最小运行时,因此如果您不想依赖循环展开的希望,那么表单可能是最有效的,至少比任何其他呈现的都更有效。但你不能以一般的方式拥有它。使用java.util.Function的函数组合,再次存在巨大的开销(每个函数都是一个类,每个调用都是需要调度的虚拟方法)。也许在这种情况下,颠覆语言级别并在运行时生成自定义字节代码可能是有意义的。另一方面,逻辑也需要在字节代码级别进行分支,并且可能等效于if/return(如果没有开销,也无法生成)。a && b && c ...&&


答案 2

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

展开策略

实际上,在 HotSpot 术语中,此类循环被视为计数,在某些情况下,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认为即使两次迭代也不值得展开。请注意,无论如何,第一次迭代都会被提取到预循环中(循环剥离优化),因此展开在这里确实不是很有益。

类型推测

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

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

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

有关推测内联的更多信息,请参阅文章 The Black Magic of (Java) Method Dispatch

结论

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

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


推荐