在Java中乘法和除法比移位更快吗? 。净?

如果碰巧使用的是2的幂,那么左右移位比显然要快于大部分甚至全部CPU的乘法和除法操作。然而,这会降低某些读者和一些algorithm的代码的清晰度。 对于性能来说,位移是非常必要的,还是我希望编译器或虚拟机能够注意到这种情况并对其进行优化(特别是当“2的幂”是文字时)? 我主要对Java和.NET的行为感兴趣,但也欢迎对其他语言实现的见解。

13 Solutions collect form web for “在Java中乘法和除法比移位更快吗? 。净?”

今天的大多数编译器不仅仅是将乘以或除以二的幂乘以转换操作。 在进行优化时,许多编译器可以用编译时间常数优化乘法或除法,即使它不是2的乘方。通常可以将乘法或除法分解为一系列的移位和相加,如果这一系列的操作将更快比乘法或除法,编译器将使用它。

对于一个常数的除法,编译器通常可以把这个操作转换成一个“幻数”,然后是一个移位。 这可能是主要的时钟周期保护,因为乘法常常比分频操作快得多。

亨利·沃伦(Henry Warren)的书“黑客的喜悦”(Hacker's Delight)有关于这个话题的大量信息,在同伴网站上也有很好的介绍:

另见下面的讨论(带有一两个链接):

  • 读取汇编代码

无论如何,这一切都归结为允许编译器照顾微观优化的繁琐细节。 自己的class次超过了编译器已经有好几年了。

几乎任何值得它的盐的环境都会为你优化这一点。 如果不是这样,你就有更大的鱼来炒。 严重的是, 不要再浪费一秒思考这个问题了。 你会知道什么时候有性能问题。 在运行一个分析器之后,你会知道是什么原因造成的,应该相当清楚如何解决这个问题。

你永远不会听到有人说:“我的应用程序太慢了,于是我开始随机用x << 1replacex * 2 ,所有东西都是固定的! 性能问题一般可以通过find一种减less工作量的方法来解决,而不是通过find一种方法来以比原来快1%的速度完成相同的工作。

在这些情况下,人类是错误的。

当他们尝试第二次猜测一个现代(以及所有将来的)编译器时,这个数字是99%。
99.9%的时候,他们试图第二次猜测现代(和所有未来)的JIT在同一时间。
99.999%,当他们试图第二次猜测现代(和所有未来)的CPU优化。

以一种准确的方式描述你想要完成的事情,而不是如何去做。 JIT,VM,编译器和CPU的未来版本都可以独立进行改进和优化。 如果您指定了如此细小的特定内容,您将失去所有未来优化的好处。

您几乎可以肯定依靠字面幂乘二优化来进行换档操作。 这是编译器构build的学生将学习到的第一个优化之一。 🙂

不过,我不认为有这个保证。 你的源代码应该反映你的意图 ,而不是试图告诉优化者该做什么。 如果您要增加数量,请使用乘法。 如果您将位域从一个位置移动到另一个位置(请考虑RGB颜色操作),请使用移位操作。 无论哪种方式,你的源代码将反映你实际上在做什么。

请注意,向下移动和分割(当然,在Java中)会给出负数,奇数的不同结果。

 int a = -7; System.out.println("Shift: "+(a >> 1)); System.out.println("Div: "+(a / 2)); 

打印:

 Shift: -4 Div: -3 

由于Java没有任何未签名的数字,所以Java编译器不可能优化它。

在我testing的计算机上,整数除法比其他操作慢4到10倍

当编译器可以用2的倍数来代替分割,并且使你看不出有什么区别时,不是2的倍数的分割要慢得多。

例如,我有一个(graphics)程序,有许多分为255.事实上,我的计算是:

 r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23; 

我可以确保它比我以前的计算速度快很多:

 r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255; 

所以不,编译器不能做所有的优化技巧。

我会问:“你在做什么,这很重要?”。 首先devise你的代码的可读性和可维护性。 位移标准乘法的可能性会使性能差异极小。

这是硬件依赖。 如果我们正在谈论微控制器或i386,那么转换可能会更快,但是,如同几个答案一样,编译器通常会为您做优化。

在现代(奔腾Pro和更高版本)的硬件上,stream水线技术使得这一切完全不相干,而且从通常的path上离散,通常意味着你失去了比你所能获得的更多的优化。

微观优化不仅浪费您的时间,而且极其困难。

如果编译器(编译时常量)或JIT(运行时常量)知道除数或被乘数是2的乘方,并且正在执行整数运算,则会将其转换为您的转换。

我刚刚写了这个代码,我感到愕然,并意识到,移动一个实际上比乘以2慢!

(编辑:改变了代码停止溢出迈克尔·迈尔斯的build议后,但结果是一样的!这里有什么错?)

 import java.util.Date; public class Test { public static void main(String[] args) { Date before = new Date(); for (int j = 1; j < 50000000; j++) { int a = 1 ; for (int i = 0; i< 10; i++){ a *=2; } } Date after = new Date(); System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds"); before = new Date(); for (int j = 1; j < 50000000; j++) { int a = 1 ; for (int i = 0; i< 10; i++){ a = a << 1; } } after = new Date(); System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds"); } } 

结果是:

乘以639毫秒
转移718毫秒

根据这个微基准的结果,移位速度是分割的两倍(Oracle Java 1.7.0_72)。

大多数编译器会在适当的时候将乘法和除法转换成位移。 这是最简单的优化之一。 所以,你应该做一些更容易阅读和适合于给定的任务。

这是来自Savvas Dalkitsis的基准分析。 虽然这个testing通过比特移位来检查乘法的速度,但是使用的值是不一样的,在C#中检查下面的代码来显示值)

 for (int i = 0, j = 1, k = 1; i < 10; i++) { j = j * 2; k <<= 2; Console.WriteLine("{0} {1}", j, k); } 

在C#中显示值的Savvas Dalkitsis示例的等效代码将是

  public static void Main(String[] args) { for (int i = 0, j = 1, k = 1; i < 10; i++) { j = j * 2; k <<= 2; Console.WriteLine("{0} {1}", j, k); } Console.WriteLine("-----------------------------------------------"); DateTime before = DateTime.Now; for (int j = 1; j < 500000000; j++) { int a = 1; for (int i = 0; i < 10; i++) a *= 2; } DateTime after = DateTime.Now; Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds"); before = DateTime.Now; for (int j = 1; j < 500000000; j++) { int a = 1; for (int i = 0; i < 10; i++) a = a << 1; } after = DateTime.Now; Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds"); Console.ReadKey(); }