Java：手动展开的循环仍然比原始循环快。为什么？
Java: manually-unrolled loop is still faster than the original loop. Why?
考虑长度为 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 and here 并观察到第二个片段的速度提高了 10% 以上。
问题：为什么 Java 没有使用基本循环展开技术优化我的第一个片段？
特别是，我想了解以下内容：
- 我可以很容易地生成一个代码，该代码对于 2 个过滤器的情况是最佳的，并且在其他数量的过滤器的情况下仍然可以工作（想象一个简单的构建器）：
return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)。 JITC 可以做同样的事情吗？如果不能，为什么？
- JITC 能否检测到“filters.length==2”是最常见的情况并生成代码经过一些热身后最适合这种情况？这应该与手动展开的版本几乎一样优化。
- JITC 能否检测到特定 实例 的使用非常频繁，然后为该特定实例 生成代码 （它知道过滤器的数量总是 2)？
更新： 得到了 JITC 仅在 class 级别上工作的答案。好的，知道了。
理想情况下，我希望收到对 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);
}
}
所提供的循环可能属于 "non counted" 循环类别，这些循环的迭代次数既不能在编译时也不能在 运行 时确定。不仅因为@Andreas 关于数组大小的争论，还因为随机条件 break（当我写这个 post 时，它曾经在你的基准中）。
最先进的编译器不会积极地
优化它们，因为展开非计数循环通常涉及
复制循环的退出条件，因此只会提高
运行-time performance 如果后续的编译器优化可以
优化展开的代码。请参阅此 2017 paper 以了解他们提出如何展开此类内容的建议的详细信息。
由此可见，您的假设不成立，您执行了某种 "manual unrolling" 循环。您认为这是一种基本的循环展开技术，可以将具有条件中断的数组上的迭代转换为 && 链式布尔表达式。我会认为这是一个相当特殊的情况，并且会惊讶地发现热点优化器可以即时进行复杂的重构。 Here they're discussing what it actually might do, perhaps this reference 很有趣。
这将更接近地反映当代展开的机制，并且可能仍然远不及展开的机器代码的样子：
if (! filters[0].isOK(i))
{
return false;
}
if(! filters[1].isOK(i))
{
return false;
}
return true;
您的结论是，因为一段代码 运行s 比另一段代码快，所以循环没有展开。即使是这样，您仍然可以看到 运行 时间差异，因为您正在比较不同的实现。
如果您想获得更多的确定性，jitwatch analyzer/visualizer of the actual Jit operations including machine code (github) (presentation slides). If there's something to see eventually I'd trust my own eyes more than any opinion about what JIT may or may not do in general, since every case has its specifics. Here 他们担心就 JIT 而言难以针对特定情况得出一般性陈述并提供一些有趣的链接。
因为你的目标是最短 运行 时间，a && b && c ... 形式可能是最有效的，如果你不想依赖循环展开的希望，至少更有效比其他任何呈现。但是你不能以通用的方式拥有它。在字节码级别也具有 java.util.Function there's huge overhead again (each Function is a class, each call is a virtual method that needs dispatch). Perhaps in such a scenario it might make sense to subvert the language level and generate custom byte code at runtime. On the other hand a && logic requires branching 的功能组合，并且可能等效于 if/return （如果没有开销也无法对其进行泛化）。
TL;DR 这里性能差异的主要原因与循环展开无关。它是 类型推测 和 内联缓存 .
展开策略
事实上，在 HotSpot 术语中，此类循环被视为 counted，并且在某些情况下 JVM can 展开它们。但不是你的情况。
HotSpot 有两种循环展开策略：1) 最大展开，即完全删除循环；或 2) 将几个连续的迭代粘合在一起。
只有 exact number of iterations is known.
才能进行最大程度的展开
if (!cl->has_exact_trip_count()) {
// Trip count is not exact.
return false;
}
但是，在您的情况下，该函数可能 return 在第一次迭代后的早期。
可能会应用部分展开，但 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 可以完美地内联这两个调用——所谓的 "inline cache" 在这种情况下具有 100% 的命中率。
通过循环，只有一个invokeinterface字节码，并且只收集到一个类型配置文件。 HotSpot JVM 发现 filters[j].isOK() 被 Filter1 接收器调用了 86% 次，而 Filter2 接收器被调用了 14% 次。这将是一个双态调用。幸运的是，HotSpot 也可以推测性地内联双态调用。它使用条件分支内联两个目标。然而，在这种情况下，命中率最多为 86%，性能将受到相应的架构级别错误预测分支的影响。
如果您有 3 个或更多不同的过滤器，情况会更糟。在这种情况下 isOK() 将是 HotSpot 根本无法内联的超形态调用。因此，编译后的代码将包含真正的接口调用，对性能的影响更大。
文章 The Black Magic of (Java) Method Dispatch 中有关推测内联的更多信息。
结论
为了内联 virtual/interface 调用，HotSpot JVM 收集每个调用字节码的类型配置文件。如果循环中有虚拟调用，则无论循环是否展开，调用都只有一个类型配置文件。
要从虚拟调用优化中获得最佳效果，您需要手动拆分循环，主要是为了拆分类型配置文件。到目前为止，HotSpot 无法自动执行此操作。
考虑长度为 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 and here 并观察到第二个片段的速度提高了 10% 以上。
问题：为什么 Java 没有使用基本循环展开技术优化我的第一个片段？
特别是，我想了解以下内容：
- 我可以很容易地生成一个代码，该代码对于 2 个过滤器的情况是最佳的，并且在其他数量的过滤器的情况下仍然可以工作（想象一个简单的构建器）：
return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters)。 JITC 可以做同样的事情吗？如果不能，为什么？ - JITC 能否检测到“filters.length==2”是最常见的情况并生成代码经过一些热身后最适合这种情况？这应该与手动展开的版本几乎一样优化。
- JITC 能否检测到特定 实例 的使用非常频繁，然后为该特定实例 生成代码 （它知道过滤器的数量总是 2)？
更新： 得到了 JITC 仅在 class 级别上工作的答案。好的，知道了。
理想情况下，我希望收到对 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);
}
}
所提供的循环可能属于 "non counted" 循环类别，这些循环的迭代次数既不能在编译时也不能在 运行 时确定。不仅因为@Andreas 关于数组大小的争论，还因为随机条件 break（当我写这个 post 时，它曾经在你的基准中）。
最先进的编译器不会积极地 优化它们，因为展开非计数循环通常涉及 复制循环的退出条件，因此只会提高 运行-time performance 如果后续的编译器优化可以 优化展开的代码。请参阅此 2017 paper 以了解他们提出如何展开此类内容的建议的详细信息。
由此可见，您的假设不成立，您执行了某种 "manual unrolling" 循环。您认为这是一种基本的循环展开技术，可以将具有条件中断的数组上的迭代转换为 && 链式布尔表达式。我会认为这是一个相当特殊的情况，并且会惊讶地发现热点优化器可以即时进行复杂的重构。 Here they're discussing what it actually might do, perhaps this reference 很有趣。
这将更接近地反映当代展开的机制，并且可能仍然远不及展开的机器代码的样子：
if (! filters[0].isOK(i))
{
return false;
}
if(! filters[1].isOK(i))
{
return false;
}
return true;
您的结论是，因为一段代码 运行s 比另一段代码快，所以循环没有展开。即使是这样，您仍然可以看到 运行 时间差异，因为您正在比较不同的实现。
如果您想获得更多的确定性，jitwatch analyzer/visualizer of the actual Jit operations including machine code (github) (presentation slides). If there's something to see eventually I'd trust my own eyes more than any opinion about what JIT may or may not do in general, since every case has its specifics. Here 他们担心就 JIT 而言难以针对特定情况得出一般性陈述并提供一些有趣的链接。
因为你的目标是最短 运行 时间，a && b && c ... 形式可能是最有效的，如果你不想依赖循环展开的希望，至少更有效比其他任何呈现。但是你不能以通用的方式拥有它。在字节码级别也具有 java.util.Function there's huge overhead again (each Function is a class, each call is a virtual method that needs dispatch). Perhaps in such a scenario it might make sense to subvert the language level and generate custom byte code at runtime. On the other hand a && logic requires branching 的功能组合，并且可能等效于 if/return （如果没有开销也无法对其进行泛化）。
TL;DR 这里性能差异的主要原因与循环展开无关。它是 类型推测 和 内联缓存 .
展开策略
事实上，在 HotSpot 术语中，此类循环被视为 counted，并且在某些情况下 JVM can 展开它们。但不是你的情况。
HotSpot 有两种循环展开策略：1) 最大展开，即完全删除循环；或 2) 将几个连续的迭代粘合在一起。
只有 exact number of iterations is known.
才能进行最大程度的展开 if (!cl->has_exact_trip_count()) {
// Trip count is not exact.
return false;
}
但是，在您的情况下，该函数可能 return 在第一次迭代后的早期。
可能会应用部分展开，但 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 可以完美地内联这两个调用——所谓的 "inline cache" 在这种情况下具有 100% 的命中率。
通过循环，只有一个invokeinterface字节码，并且只收集到一个类型配置文件。 HotSpot JVM 发现 filters[j].isOK() 被 Filter1 接收器调用了 86% 次，而 Filter2 接收器被调用了 14% 次。这将是一个双态调用。幸运的是，HotSpot 也可以推测性地内联双态调用。它使用条件分支内联两个目标。然而，在这种情况下，命中率最多为 86%，性能将受到相应的架构级别错误预测分支的影响。
如果您有 3 个或更多不同的过滤器，情况会更糟。在这种情况下 isOK() 将是 HotSpot 根本无法内联的超形态调用。因此，编译后的代码将包含真正的接口调用，对性能的影响更大。
文章 The Black Magic of (Java) Method Dispatch 中有关推测内联的更多信息。
结论
为了内联 virtual/interface 调用，HotSpot JVM 收集每个调用字节码的类型配置文件。如果循环中有虚拟调用，则无论循环是否展开，调用都只有一个类型配置文件。
要从虚拟调用优化中获得最佳效果，您需要手动拆分循环，主要是为了拆分类型配置文件。到目前为止，HotSpot 无法自动执行此操作。