考虑以下两个长度为 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 没有使用基本的循环展开技术优化我的第一个代码段?
特别是,我想了解以下内容:
return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)
. JITC 可以这样做吗?如果不能,为什么? 理想情况下,我希望得到对 JITC 工作原理有深刻理解的人的回答。
基准运行详细信息:
典型的基准输出:
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);
}
}
最佳答案
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 无法自动执行此操作。
关于Java:手动展开的循环仍然比原始循环快。为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58995731/