循环惯用语的奇怪 JIT 优化失效

Question

循环惯用语的奇怪 JIT 优化失效

18

在分析最近这里的一个问题的结果时，我遇到了一个非常奇怪的现象：显然一层额外的HotSpot JIT优化实际上会使我的机器执行速度变慢。

这是我用于测量的代码：

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.ARRAY_SIZE)
@Warmup(iterations = 2, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(2)
public class Measure
{
  public static final int ARRAY_SIZE = 1024;
  private final int[] array = new int[ARRAY_SIZE];

  @Setup public void setup() {
    final Random random = new Random();
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      final int x = random.nextInt();
      array[i] = x == 0? 1 : x;
    }
  }

  @GenerateMicroBenchmark public int normalIndex() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[i];
      result ^= entry + j;
    }
    return result;
  }

  @GenerateMicroBenchmark public int maskedIndex() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[j];
      result ^= entry + i;
    }
    return result;
  }

  @GenerateMicroBenchmark public int normalWithExitPoint() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }

  @GenerateMicroBenchmark public int maskedWithExitPoint() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[j];
      result ^= entry + i;
      if (entry == 0) break;
    }
    return result;
  }


}

代码相当微妙，让我指出其中重要的部分：

“正常索引”变体使用直接变量i作为数组索引。 HotSpot可以轻松确定循环中i的范围并消除数组边界检查；
“掩码索引”变体通过j进行索引，实际上等于i，但这个事实通过AND掩码操作“隐藏”在HotSpot中；
“带有退出点”的变体引入了明确的循环退出点。这一点的重要性将在下面解释。

循环展开和重新排序

观察到边界检查在两个重要方面起作用：

它具有与运行时相关的开销（比较后跟条件分支）；
它构成一个可以在任何步骤中中断循环的循环退出点。这对适用的JIT优化具有重要影响。

通过检查上述四种方法生成的机器代码，我注意到以下内容：

在所有情况下，循环都被展开了；
就normalIndex而言，它是唯一没有过早循环退出点的方法，所有展开步骤的操作都被重新排序，首先执行所有的数组获取操作，然后将所有值异或到累加器中。

预期和实际测量结果

现在我们可以根据讨论的特性对四种方法进行分类：

normalIndex没有边界检查和退出点；
normalWithExitPoint没有边界检查，但有1个退出点；
maskedIndex有1个边界检查和1个退出点；
maskedWithExitPoint有1个边界检查和2个退出点。

显然，以上列表应该按性能降序列出这些方法；但是，以下是我的实际结果：

Benchmark               Mode   Samples         Mean   Mean error    Units
normalIndex             avgt        20        0.946        0.010    ns/op
normalWithExitPoint     avgt        20        0.807        0.010    ns/op
maskedIndex             avgt        20        0.803        0.007    ns/op
maskedWithExitPoint     avgt        20        1.007        0.009    ns/op

normalWithExitPoint 和 maskedIndex 在测量误差范围内是相同的，尽管只有后者具有边界检查；
最大异常出现在normalIndex上，它本应该是最快的，但显著慢于normalWithExitPoint，除了多了一行代码（引入exit point的那行代码）外，在每个方面都与后者相同。

由于只对normalIndex方法应用了额外的重新排序“优化”，结论是这是减速的原因。

我正在测试：

Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)（Java 7 Update 40）
OS X Version 10.9.1
2.66 GHz Intel Core i7

我也已经成功地在Java 8 EA b118上重现了这些结果。

我的问题:

以上现象是否可以在其他类似的计算机上重现？从一开始提到的问题中，我已经得到一个线索，即至少有一些计算机不能重现这个问题，因此同一CPU的另一个结果将是非常有趣的。

更新1: 受maaartinus的研究启发，进行了更多测试

我收集了以下表格，将执行时间与-XX:LoopUnrollLimit命令行参数相关联。在这里，我只关注两个变体，带有和不带有if (entry == 0) break;行：

LoopUnrollLimit:   14 15 18 19 22 23 60
withExitPoint:     96 95 95 79 80 80 69   1/100 ns
withoutExitPoint:  94 64 64 63 64 77 75   1/100 ns

以下突然的变化可以被观察到：

从14到15的转换中，withoutExitPoint 变种获得了有益的LCM¹ 转换，并明显加快。由于循环展开限制，所有加载的值都适合于寄存器；
在18->19时，withExitPoint 变种获得了加速，但比上面的要小；
在22->23时，withoutExitPoint 变体变慢了。此时我看到堆栈位置中开始发生“溢出”，如 maaartinus 的答案所述。

我的设置中默认的loopUnrollLimit为60，因此我在最后一列呈现了它的结果。

¹ LCM = Local Code Motion，是指使所有数组访问在顶部发生，随后处理加载的值的转换。

更新2：实际上这是一个已知的问题

https://bugs.openjdk.java.net/browse/JDK-7101232

附录：在机器代码中展开和重新排序的`normalIndex`循环

0x00000001044a37c0: mov    ecx,eax
0x00000001044a37c2: and    ecx,esi            ;*iand
                                              ; - org.sample.Measure::normalIndex@20 (line 44)
0x00000001044a37c4: mov    rbp,QWORD PTR [rsp+0x28]  ;*iload_3
                                              ; - org.sample.Measure::normalIndex@15 (line 44)
0x00000001044a37c9: add    ecx,DWORD PTR [rbp+rsi*4+0x10]
0x00000001044a37cd: xor    ecx,r8d
0x00000001044a37d0: mov    DWORD PTR [rsp],ecx
0x00000001044a37d3: mov    r10d,esi
0x00000001044a37d6: add    r10d,0xf
0x00000001044a37da: and    r10d,eax
0x00000001044a37dd: mov    r8d,esi
0x00000001044a37e0: add    r8d,0x7
0x00000001044a37e4: and    r8d,eax
0x00000001044a37e7: mov    DWORD PTR [rsp+0x4],r8d
0x00000001044a37ec: mov    r11d,esi
0x00000001044a37ef: add    r11d,0x6
0x00000001044a37f3: and    r11d,eax
0x00000001044a37f6: mov    DWORD PTR [rsp+0x8],r11d
0x00000001044a37fb: mov    r8d,esi
0x00000001044a37fe: add    r8d,0x5
0x00000001044a3802: and    r8d,eax
0x00000001044a3805: mov    DWORD PTR [rsp+0xc],r8d
0x00000001044a380a: mov    r11d,esi
0x00000001044a380d: inc    r11d
0x00000001044a3810: and    r11d,eax
0x00000001044a3813: mov    DWORD PTR [rsp+0x10],r11d
0x00000001044a3818: mov    r8d,esi
0x00000001044a381b: add    r8d,0x2
0x00000001044a381f: and    r8d,eax
0x00000001044a3822: mov    DWORD PTR [rsp+0x14],r8d
0x00000001044a3827: mov    r11d,esi
0x00000001044a382a: add    r11d,0x3
0x00000001044a382e: and    r11d,eax
0x00000001044a3831: mov    r9d,esi
0x00000001044a3834: add    r9d,0x4
0x00000001044a3838: and    r9d,eax
0x00000001044a383b: mov    r8d,esi
0x00000001044a383e: add    r8d,0x8
0x00000001044a3842: and    r8d,eax
0x00000001044a3845: mov    DWORD PTR [rsp+0x18],r8d
0x00000001044a384a: mov    r8d,esi
0x00000001044a384d: add    r8d,0x9
0x00000001044a3851: and    r8d,eax
0x00000001044a3854: mov    ebx,esi
0x00000001044a3856: add    ebx,0xa
0x00000001044a3859: and    ebx,eax
0x00000001044a385b: mov    ecx,esi
0x00000001044a385d: add    ecx,0xb
0x00000001044a3860: and    ecx,eax
0x00000001044a3862: mov    edx,esi
0x00000001044a3864: add    edx,0xc
0x00000001044a3867: and    edx,eax
0x00000001044a3869: mov    edi,esi
0x00000001044a386b: add    edi,0xd
0x00000001044a386e: and    edi,eax
0x00000001044a3870: mov    r13d,esi
0x00000001044a3873: add    r13d,0xe
0x00000001044a3877: and    r13d,eax
0x00000001044a387a: movsxd r14,esi
0x00000001044a387d: add    r10d,DWORD PTR [rbp+r14*4+0x4c]
0x00000001044a3882: mov    DWORD PTR [rsp+0x24],r10d
0x00000001044a3887: mov    QWORD PTR [rsp+0x28],rbp
0x00000001044a388c: mov    ebp,DWORD PTR [rsp+0x4]
0x00000001044a3890: mov    r10,QWORD PTR [rsp+0x28]
0x00000001044a3895: add    ebp,DWORD PTR [r10+r14*4+0x2c]
0x00000001044a389a: mov    DWORD PTR [rsp+0x4],ebp
0x00000001044a389e: mov    r10d,DWORD PTR [rsp+0x8]
0x00000001044a38a3: mov    rbp,QWORD PTR [rsp+0x28]
0x00000001044a38a8: add    r10d,DWORD PTR [rbp+r14*4+0x28]
0x00000001044a38ad: mov    DWORD PTR [rsp+0x8],r10d
0x00000001044a38b2: mov    r10d,DWORD PTR [rsp+0xc]
0x00000001044a38b7: add    r10d,DWORD PTR [rbp+r14*4+0x24]
0x00000001044a38bc: mov    DWORD PTR [rsp+0xc],r10d
0x00000001044a38c1: mov    r10d,DWORD PTR [rsp+0x10]
0x00000001044a38c6: add    r10d,DWORD PTR [rbp+r14*4+0x14]
0x00000001044a38cb: mov    DWORD PTR [rsp+0x10],r10d
0x00000001044a38d0: mov    r10d,DWORD PTR [rsp+0x14]
0x00000001044a38d5: add    r10d,DWORD PTR [rbp+r14*4+0x18]
0x00000001044a38da: mov    DWORD PTR [rsp+0x14],r10d
0x00000001044a38df: add    r13d,DWORD PTR [rbp+r14*4+0x48]
0x00000001044a38e4: add    r11d,DWORD PTR [rbp+r14*4+0x1c]
0x00000001044a38e9: add    r9d,DWORD PTR [rbp+r14*4+0x20]
0x00000001044a38ee: mov    r10d,DWORD PTR [rsp+0x18]
0x00000001044a38f3: add    r10d,DWORD PTR [rbp+r14*4+0x30]
0x00000001044a38f8: mov    DWORD PTR [rsp+0x18],r10d
0x00000001044a38fd: add    r8d,DWORD PTR [rbp+r14*4+0x34]
0x00000001044a3902: add    ebx,DWORD PTR [rbp+r14*4+0x38]
0x00000001044a3907: add    ecx,DWORD PTR [rbp+r14*4+0x3c]
0x00000001044a390c: add    edx,DWORD PTR [rbp+r14*4+0x40]
0x00000001044a3911: add    edi,DWORD PTR [rbp+r14*4+0x44]
0x00000001044a3916: mov    r10d,DWORD PTR [rsp+0x10]
0x00000001044a391b: xor    r10d,DWORD PTR [rsp]
0x00000001044a391f: mov    ebp,DWORD PTR [rsp+0x14]
0x00000001044a3923: xor    ebp,r10d
0x00000001044a3926: xor    r11d,ebp
0x00000001044a3929: xor    r9d,r11d
0x00000001044a392c: xor    r9d,DWORD PTR [rsp+0xc]
0x00000001044a3931: xor    r9d,DWORD PTR [rsp+0x8]
0x00000001044a3936: xor    r9d,DWORD PTR [rsp+0x4]
0x00000001044a393b: mov    r10d,DWORD PTR [rsp+0x18]
0x00000001044a3940: xor    r10d,r9d
0x00000001044a3943: xor    r8d,r10d
0x00000001044a3946: xor    ebx,r8d
0x00000001044a3949: xor    ecx,ebx
0x00000001044a394b: xor    edx,ecx
0x00000001044a394d: xor    edi,edx
0x00000001044a394f: xor    r13d,edi
0x00000001044a3952: mov    r8d,DWORD PTR [rsp+0x24]
0x00000001044a3957: xor    r8d,r13d           ;*ixor
                                              ; - org.sample.Measure::normalIndex@34 (line 46)
0x00000001044a395a: add    esi,0x10           ;*iinc
                                              ; - org.sample.Measure::normalIndex@36 (line 43)
0x00000001044a395d: cmp    esi,DWORD PTR [rsp+0x20]
0x00000001044a3961: jl     0x00000001044a37c0  ;*if_icmpge
                                              ; - org.sample.Measure::normalIndex@12 (line 43)

- Marko Topolnik

你使用的Java版本是哪个？我使用的是Java 7更新45，它显示为“build 24.45-b08”。 - Peter Lawrey

@PeterLawrey，这是Java 7更新40版（1.7.0_40-b43）。 - Marko Topolnik

@HotLicks 对不起，那是复制粘贴错误。请检查编辑。 - Marko Topolnik

更新40与更新25相比是一个很大的变化，例如增加了“飞行记录器”，并且更新得非常快。我建议尝试更新51，可能更加稳定。 - Peter Lawrey

@HotLicks 但是那个程序拥有最干净的流水线——在整个展开循环的范围内没有任何 jXX 指令。 - Marko Topolnik

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- maaartinus · Accepted Answer

JITC试图将所有内容分组在一起的原因对我来说不是很清楚。据我所知，有些架构（过去还是现在？）将两个负载分组可以获得更好的性能（我想是一些早期的Pentium）。由于JITC知道热点位置，因此它可以比预编译编译器更积极地进行内联，因此在这种情况下它会这样做16次。我看不出在这里有任何明显的优点，除了使循环相对较便宜外。我还怀疑是否有任何架构能从将16个负载分组中受益。该代码计算16个临时值，每次迭代计算一个。

int j = i & array.length-1;
int entry = array[i];
int tmp = entry + j;
result ^= tmp;

每个计算都相当简单，一个AND，一个LOAD和一个ADD。这些值需要映射到寄存器，但寄存器不足。因此，这些值必须稍后存储和加载。

这发生在16个寄存器中的7个中，大大增加了成本。

更新：

我不太确定是否可以使用-XX：LoopUnrollLimit进行验证：

LoopUnrollLimit Benchmark   Mean   Mean error    Units

 8 ..normalIndex           0.902        0.004    ns/op
 8 ..normalWithExitPoint   0.913        0.005    ns/op
 8 ..maskedIndex           0.918        0.006    ns/op
 8 ..maskedWithExitPoint   0.996        0.008    ns/op

16 ..normalIndex           0.769        0.003    ns/op
16 ..normalWithExitPoint   0.930        0.004    ns/op
16 ..maskedIndex           0.937        0.004    ns/op
16 ..maskedWithExitPoint   1.012        0.003    ns/op

32 ..normalIndex           0.814        0.003    ns/op
32 ..normalWithExitPoint   0.816        0.005    ns/op
32 ..maskedIndex           0.838        0.003    ns/op
32 ..maskedWithExitPoint   0.978        0.002    ns/op

 - ..normalIndex           0.830        0.002    ns/op
 - ..normalWithExitPoint   0.683        0.002    ns/op
 - ..maskedIndex           0.791        0.005    ns/op
 - ..maskedWithExitPoint   0.908        0.003    ns/op

限制为16使得normalIndex成为最快的变体，这表明我在“过度分配惩罚”方面是正确的。但是根据Marko的说法，生成的汇编代码也会随着展开限制而在其他方面发生变化，因此事情变得更加复杂。

循环惯用语的奇怪 JIT 优化失效

循环展开和重新排序

预期和实际测量结果

我的问题:

更新1: 受maaartinus的研究启发，进行了更多测试

更新2：实际上这是一个已知的问题

附录：在机器代码中展开和重新排序的normalIndex循环

附录：在机器代码中展开和重新排序的`normalIndex`循环