登录
当前位置： 首页 > 面试题库 >

循环习语的奇怪JIT悲观化

东郭宏朗
2023-03-14
问题内容：

在分析这里最近一个问题的结果时，我遇到了一个非常奇怪的现象：显然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整个循环的范围并消除数组边界检查；
  • by的“ masked index”变体索引j实际上等于i，但是通过AND-masking操作从HotSpot中“隐藏”了这一事实；
  • “带有出口点”变体引入了显式循环出口点。下面将说明其重要性。

循环展开和重新排序

观察边界以两种重要方式检查数字：

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

通过检查以上四种方法发出的机器代码，我注意到了以下几点：

  • 在所有情况下，循环都是展开的；
  • 在的情况下normalIndex，它是唯一一个没有过早循环出口点的循环，对所有展开步骤的操作进行重新排序，以便首先执行所有数组提取，然后将所有值进行XOR运算到累加器中。

预期和实际测量结果

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

  • 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它慢得多，在各个方面都与之相同，只不过 多了一行代码 ，这是引入出口点 的代码 。

由于normalIndex是唯一对其应用了额外的重新排序“优化”的方法，因此得出的结论是，这是速度下降的原因。

我正在测试：

  • Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode) （Java 7更新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机器代码中的展开和重新排序的循环

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有（曾经）架构，将两个负载组合在一起可以带来更好的性能（我认为是一些早期的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

限制16normalIndex是最快的变种，这表示我对“超额分配罚金”是正确的。根据Marko的说法，在其他方面，生成的装配也会随着展开限制而变化，因此事情变得更加复杂。



 类似资料：
  • Java上的奇怪循环0.1到2

    问题内容： 我尝试从0.1循环到2.0，然后将输出打印到控制台。但是我得到了如下奇怪的输出： 源代码： 为什么它不打印确切的数字而不是像点呢？另外，使用代替还有什么区别，因为我不知道如何增加0.1？ 问题答案： 这是正常的。它是浮点型固有的；像0.3这样的数字不能作为精确值存储在二进制文件中，因此您会逐渐积累错误。参考资料： Python手册，Wikipedia，Princeton CS的技术说明

  • gcc：为简单循环生成的奇怪 asm

    我非常困惑为什么gcc会为const数组上的简单for循环生成这种（看似）非最佳代码。 结果： 我主要关心的是: 为什么无用的第一个元素比较在？这永远不会命中，也永远不会被分支回。它最终只是第一次迭代的重复代码。 < li >有没有更好的方法来编写这个非常简单的循环，这样gcc就不会产生这种奇怪的代码？ < li >有没有我可以利用的编译器标志/优化？< code>O3只是展开循环，我也不希望这样

  • JIT未优化涉及Integer.MAX_VALUE的循环

    问题内容： 在写另一个问题的答案时，我注意到用于JIT优化的奇怪边框。 以下程序 不是 “ Microbenchmark”， 也不 旨在可靠地衡量执行时间（如对另一个问题的回答所指出）。它仅用作MCVE来重现此问题： 它基本上运行相同的循环，其中将限制一次设置为，将一次设置为。 当在Win7 / 64上使用JDK 1.7.0_21和 计时结果如下： 显然，对于JIT 的情况，JIT可以完成预期的工

  • Postgres：乐观锁定的奇怪行为

    我正在调试使用JPA / Hibernate和Postgres（9.6.2）的Java应用程序的奇怪行为。 应用程序有 3 个实体：用户、国家/地区、用户事件。 Hibernate将其映射到4个表：users、countries、userevent、Hibernate_sequences。 用户实体具有版本列 （@Version） 和用于乐观锁定的主题。@GeneratedValue（strate

  • Java JIT循环展开策略？

    问题内容： JIT的循环展开策略是什么？或者，如果没有简单的答案，那么有什么方法可以检查循环中展开循环的位置/时间？ 基本上，我上面有一段代码，具有静态的迭代次数（八），当我保持for循环不变时，它的效果很差。但是，当我手动展开循环时，效果会更好。我有兴趣了解JIT是否确实展开了循环，如果没有，那么为什么。 问题答案： 如果 JVM展开，则可以通过实际打印生成的程序集来最好地解决该循环。请注意，这

  • spring悲观锁定

    问题内容： 我在java下有spring项目，使用hibernate查询，我喜欢使用悲观锁定。 在Spring + Hibernate中如何进行悲观锁定？ 编辑： 问题： 我想在一个方法中使用悲观锁定，并且我将此方法称为从不同的方法。当我从第一个方法调用它时，悲观的工作效果很好，但是当我从第二个方法调用它时，它给出了（无法提交事务） 例外： 问题答案： http://www.amicabile.c

相关阅读

新的/奇怪的Java“ try（）”语法？奇怪的INNER JOIN语法和封装说一下乐观锁和悲观锁？Java好奇循环性能用JavaScript创建范围-奇怪的语法

相关文章

4.7 Verilog 循环语句Python while循环语句C语言for循环C语言while循环Go语言键值循环

相关问答

Spring data CrudRepository和悲观锁Hibernate悲观锁定模式Codingbat前背部练习奇怪的结果奇怪的行为JPA悲观锁不起作用

相关工具

循环ScrollViewtailwindcss-jit循环洞穴2循环洞穴 2循环滚动视图

相关文档

学习 C 语言Rust 语言学习笔记JavaScript 的 12 个怪癖通过实例学习 C 语言深度学习进阶：自然语言处理
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.