8

Java 编译器或JIT 编译器是否通过恒定的 2 次幂优化除法或乘法以进行位移？

例如，以下两个语句是否优化为相同？

int median = start + (end - start) >>> 1;
int median = start + (end - start) / 2;

（基本上这个问题，但对于Java）

4

3 回答 3

17

虽然在除法不能简单地用右移代替的意义上，公认的答案是正确的，但基准是非常错误的。任何运行不到一秒的 Java 基准测试都可能测量解释器的性能——这不是您通常关心的事情。

我无法抗拒并编写了一个自己的基准，主要表明这一切都更加复杂。我不想完全解释结果，但我可以这么说

  • 一般师是一个该死的缓慢操作
  • 尽可能避免它
  • 除以常数得到AFAIK总是以某种方式优化
  • 除以 2 的幂被右移和负数调整所取代
  • 手动优化的表达式可能会更好
于 2014-02-07T00:50:49.137 回答
8

不，Java 编译器不会那样做，因为它不能确定 的符号是什么(end - start)。为什么这很重要？负整数的位移产生与普通除法不同的结果。在这里你可以看到一个演示：这个简单的测试：

System.out.println((-10) >> 1);  // prints -5
System.out.println((-11) >> 1);  // prints -6
System.out.println((-11) / 2);   // prints -5

另请注意，我使用>>而不是>>>. A>>>是无符号位移，而>>有符号。

System.out.println((-10) >>> 1); // prints 2147483643

@Mystical：我写了一个基准测试，表明编译器/JVM 没有进行优化：https ://ideone.com/aKDShA

于 2013-09-01T17:17:45.927 回答
2

如果 JVM 不这样做，您可以轻松地自己进行。

如前所述，负数的右移与除法的行为不同，因为结果以错误的方向四舍五入。如果您知道股息是非负的，则可以安全地用班次替换除法。如果它可能是负面的，您可以使用以下技术。

如果你可以用这种形式表达你的原始代码：

int result = x / (1 << shift);

您可以用这个优化的代码替换它：

int result = (x + (x >> 31 >>> (32 - shift))) >> shift;

或者，或者：

int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift;

这些公式通过添加一个从被除数的符号位计算的小数来补偿不正确的舍入。这适用于x所有移位值从 1 到 30 的任何对象。

如果 shift 为 1（即，您除以 2），则>> 31可以在第一个公式中删除 以给出这个非常整洁的片段：

int result = (x + (x >>> 31)) >> 1;

我发现这些技术即使在变化不恒定的情况下也更快，但显然如果变化是恒定的，它们会受益最大。注意：对于long x代替int，将 31 和 32 分别更改为 63 和 64。

检查生成的机器代码表明（不出所料）HotSpot Server VM 可以在班次不变时自动执行此优化，但（同样不出所料）HotSpot Client VM 太愚蠢了。

于 2014-02-09T22:47:18.313 回答