奇怪的JIT对循环习语的悲观化

在这里分析最近一个问题的结果时 ，我遇到了一个非常奇怪的现象：显然，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“隐藏”的;
  • “with exit point”变体引入了一个explict循环退出点。 下面将解释这一点的重要性。

循环展开和重新排序

观察边界检查数据有两个重要方面：

  • 它具有与之关联的运行时开销（比较后跟条件分支）;
  • 它构成一个循环退出点 ，可以在任何步骤中断循环。 结果certificate这对适用的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上观察到最大的exception，它应该是最快的，但是比normalWithExitPoint慢得多，在各个方面都相同，除了有一行代码 ，引入出口点的代码 。

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

我正在测试：

  • Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode) （Java 7 Update 40）
  • OS X版本10.9.1
  • 2.66 GHz英特尔酷睿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 1变换并且显着加速。 由于循环展开限制，所有加载的值都适合寄存器;

  • 在18-> 19， withExitPoint变种获得加速，小于上述;

  • 在22-> 23， withoutExitPoint变种减慢了。 在这一点上，我看到溢出到堆栈位置，如maaartinus的回答中所述，开始发生。

我的设置的默认loopUnrollLimit是60，所以我在最后一列中显示其结果。

1 LCM =本地代码运动。 正是转换导致所有数组访问发生在顶部，然后处理加载的值。

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

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

附录： normalIndex中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)

JITC试图将所有内容组合在一起的原因对我来说还不清楚。 AFAIK有（有？）架构，其中两个负载的分组导致更好的性能（我认为一些早期的奔腾）。

由于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:LoopUnrollLimitvalidation这个-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的说法，生成的程序集在其他方面也随着展开限制而变化，因此事情变得更加复杂。

    Interesting Posts

    如何获取Java7应用程序的CPU，RAM和网络使用情况

    使用Java检测CPU速度/内存/ Internet速度？

    基于no的线程配置。 CPU核心

    Java限制资源使用

    什么是’cpumin.exe’进程在后台运行并占用100％的CPU？ 每当我运行Java程序时都会发生这种情况

    是否有在微码中运行Java的CPU？

    如何让Java使用机器上的所有CPU电源？

    Android app的理想cpu百分比

    在CPU上的Java中可以并发运行的最大线程数

    为什么这个Java代码不使用所有CPU内核？