Java是否通过2的幂来优化除法?
Java编译器或 JIT编译器是否通过2的恒定功率优化除法或乘法到位移位?
例如,以下两个语句是否被优化为相同?
int median = start + (end - start) >>> 1; int median = start + (end - start) / 2;
(基本上这个问题,但对于Java)
不,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
虽然接受的答案是正确的,因为分裂不能简单地由右移代替,但基准是非常错误的。 任何运行时间不到一秒的Java基准测试都可能会测量解释器的性能 – 而不是您通常关心的问题。
我无法抗拒并写了一个自己的基准 ,主要表明它更复杂。 我不是要完全解释结果 ,但我可以这么说
- 一般司是一个该死的慢操作
- 尽可能避免它
- 通过常数除法得到AFAIK总是以某种方式进行优化
- 以2的幂除法被右移和负数的调整所取代
- 手动优化的表达式可能会更好
如果JVM没有这样做,您可以轻松地自己完成。
如上所述,负数的右移与分割的行为不同,因为结果在错误的方向上四舍五入。 如果您知道红利是非负数,则可以通过class次安全地替换除法。 如果它可能是否定的,您可以使用以下技术。
如果您能用以下表格表达原始代码:
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。
如果移位为1(即,您除以2),则可以在第一个公式中删除>> 31
,以提供这个非常整洁的片段:
int result = (x + (x >>> 31)) >> 1;
我发现这些技术即使在换档非常不变时也会更快,但是如果换档是恒定的,它们显然会受益最多。 注意:对于long
x
而不是int
,将31和32分别更改为63和64。
检查生成的机器代码显示(不出所料)HotSpot Server VM可以在转换不变时自动执行此优化,但(也不出所料)HotSpot Client VM太愚蠢了。