分支预测：避免简单操作中的“else”分支是否能使代码更快（Java示例）？

Question

选项1：

  boolean isFirst = true;
  for (CardType cardType : cardTypes) {
    if (!isFirst) {
      descriptionBuilder.append(" or ");
    } else {
      isFirst = false;
    }
    //other code not relevant to this theoretical question
  }

选项2：

boolean isFirst = true;
for (CardType cardType : cardTypes) {
  if (!isFirst) {
    descriptionBuilder.append(" or ");
  } 
  isFirst = false;
  //other code not relevant to this theoretical question
}

我的分析: 两种代码具有相同的语义。

第一段代码) 我不确定这段代码是否有两个分支（从分支预测的角度来看），还是只有一个分支。我查阅了http://en.wikipedia.org/wiki/X86_instruction_listings，但无法找到类似“如果先前条件值为false，则跳转到此处”的X86指令，以避免两次分支预测（非常糟糕）。

第二段代码) 很可能始终执行简单的MOV操作（移动至寄存器或元素，很可能已经在缓存中），这样比较廉价（最多几个周期）。

因此，我认为除非处理器解码为微码指令时能够做出一些聪明的事情，或者存在X86指令以避免必要的分支预测，否则第二段代码更快。

我知道这纯粹是理论问题，因为在实践中，这个分支可能使应用程序变快0.000000002％或类似的速度。

我错过了什么吗？

编辑：我添加了一个循环，以便更加重视所讨论的分支。

编辑2：这个问题涉及Intel架构的分支预测（Pentium及更高版本处理器）。

- Mladen Adamovic

Answer 1

使用 JMH 在 cardTypes 数组大小为 10，整数递增为逻辑的情况下（Java 15 / AMD 3950X / Windows 10），得到以下数字：

Benchmark          Mode  Cnt          Score         Error  Units
Benchmark.option1  thrpt   25  273369417.720 ± 1618952.179  ops/s
Benchmark.option2  thrpt   25  273415784.192 ±  852618.585  ops/s

"选项2"的平均性能大约快了0.017％（可能会有所不同）。

另请参阅：分支预测，方法调度，内存访问模式，吞吐量和延迟，垃圾收集。

- AlexO

---

请注意，由于误差范围，差异并不具有统计学意义。但是，这正是我所期望的；对寄存器进行异或零操作至少与无条件的jmp相同廉价。当然，更好的方法是编译器将asm循环中的第一次迭代提升/剥离出来，或者在非第一次迭代工作后跳入其中，因此在循环中没有实际的if分支。但是，如果编译器足够聪明以执行此操作，则可能会发生在两个测试中，因此此基准测试不会捕获它（并且与此兼容，因为273... +- 1个数字在误差范围内）。 - Peter Cordes

Answer 2

这段代码的效果是相同的，但它不会产生相同的字节码或汇编（可能）。

这对性能的影响有多大，目前还不清楚，很可能微不足道。

更加重要的是代码的清晰度。我见过更多由于代码在简单情况下难以理解而导致的错误和性能问题。

简而言之，对你来说最清晰、最简单的代码也很可能足够快，或者最容易修复。

- Peter Lawrey

---

这是关于代码性能的理论问题，我知道差异最多只有几个CPU周期，但我想知道哪一个更快，而不是哪一个更易读。 - Mladen Adamovic

@MladenAdamovic 理论上，任何事情都是可能的，这就是为什么我避免给出理论答案的原因。;) - Peter Lawrey

我已经添加了EDIT2：这个问题是关于英特尔架构的分支预测（Pentium和更新的处理器）。所以并不是“任何事情”都可能发生。Java编译器有一定的工作方式，分支预测器也有一定的工作方式。 - Mladen Adamovic

@MladenAdamovic 它需要进行的分支预测数量是相同的。唯一有区别的时候是当一个简单操作可以转化为条件移动时，例如 a > b ? a : b。在这种情况下，没有分支，而是使用了 CMOV 指令。 - Peter Lawrey

为什么一样呢？我正在研究CMOV指令，该指令似乎是为了避免这种示例 a > b ? a : b 的两个分支而添加的。http://www.rcollins.org/p6/opcodes/CMOV.html我的示例1）有额外的“else”，可能比我的示例2）多一个分支。 - Mladen Adamovic

@MladenAdamovic 你的第二个例子与 if (!isFirst) { descriptionBuilder.append(" or "); } else { } 相同，即可能错过预测的数量相同。 - Peter Lawrey

Answer 3

不同的硬件对汇编指令的成本不同，在现代硬件上，由于流水线和缓存的影响，即使是一个指令的成本也很难预测。

从你所提供的示例中，无法清楚地了解到流水线和缓存在if和if/else之间的区别。如果只运行该代码一次，则不太可能看到任何差异。但是，如果在紧密循环中重复运行它，则if本身的性能将受到以下两个因素的支配：a）检查的成本和b）检查结果的可预测性。换句话说，分支预测将成为主导因素，并且if或if/else代码块的存在不会受到影响。

有关分支预测效果的出色讨论，请参见此处（查看得分最高的答案）。

- Chris K

---

我在示例中添加了外部for循环，以便分支预测可以工作（至少在理论上）。在这段代码中，“else”是否会为CPU带来额外的分支预测？ - Mladen Adamovic

@MladenAdamovic 快速的答案是否定的，添加 else 会增加一个额外的 无条件 跳转（根据定义很容易预测）。请参见 http://www.eventhelix.com/realtimemantra/basics/CToAssemblyTranslation3.htm#.VNJY9_jbClM 了解 if/else 如何被翻译成汇编代码的示例。 - Chris K

@MladenAdamovic 但是请看我的另一个答案；Hotspot 喜欢展开 for 循环的第一次迭代，特别是针对这种情况。这样它就避免了在循环的后续迭代中重复检查和条件分支，从而提供了更快的解决方案，从而回避了您的问题。 - Chris K

@MladenAdamovic 可预测跳跃的成本将用时钟周期来衡量（可能是1或更少 - 也就是说比人类能感知的快很多个数量级）。所有细节都可以在以下链接找到，但请注意...它需要耐心仔细阅读：http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html - Chris K

@mladenadamovic。我已经警告过你了 :). 最快的收获是附录，其中列出了汇编指令的延迟和吞吐量时间。此外，在3ghz芯片上，1个时钟周期为0.3ns，或0.0000000003秒。因此，如果由于循环展开而仅调用无条件跳转一次，则其成本几乎可以忽略不计。 - Chris K

Answer 4

假设您的代码片段是for循环内部的if块。Hotspot能够展开for循环，包括将常见的“循环的第一次迭代”检查内联到循环外部。因此避免了在循环的每次迭代中重新检查条件的成本。因此避免了if和if/else哪个更快的问题。Oracle文档在此处记录了这种行为。

- Chris K

Answer 5

两段代码的语义相同。

不，这两段代码是不同的，

第一段代码中，如果条件if (!isFirst)不匹配，则将标志设置为false：isFirst = false; 第二段代码每次都会将标志更改为false，即使条件满足或不满足。

- atish shimpi

---

但是为了满足条件，标志必须为“false”。因此，在这两种情况下，标志在代码片段的结尾处都具有值“false”。 - Jon Skeet

Answer 6

if/else结构中有两个分支：顶部的条件分支和在if部分末尾的else部分周围的分支。在else部分中没有分支，至少在任何一个合理实现的编译器中都不会有。

相对于总是执行isFirst = false;语句的成本，你需要权衡一下。

在你提到的具体情况中，与方法调用的成本相比，它不太可能产生丝毫差异。

- user207421

---

我不理解“else部分没有分支，至少在任何一个合理实现的编译器中都不会有分支”。你能否解释一下为什么呢？（给出汇编代码示例也可以）。 - Mladen Adamovic