为什么整数的 java 除法比黑客的快乐实现更快

我正在测试黑客喜悦书中的divs10 函数吞吐量，在我的 JDK 1.7 64 位版本 21 和 i7 英特尔盒子上用 java 编码处理器： 7vendor_id ：正版英特尔中央处理器系列： 6型号： 26型号名称：英特尔(R( 酷睿(TM( i7 处理器 920 @ 2.67GHz

我想知道为什么默认的java运算符/比黑客喜悦书中的divs10函数更快，结果显示divs10比"/"运算符慢3倍，令我惊讶。

任何人都可以告诉我是否有任何花哨的内在JVM可以使用？

源代码如下。

 public class div10 {
            public static final int divs10(int n) {
                   int q, r;
                   n = n + (n >> 31 & 9);
                   q = (n >> 1) + (n >> 2);
                   q += q >> 4;
                   q += q >> 8;
                   q += q >> 16;
                   q = q >> 3;
                   r = n - ((q << 3) + (q << 1));
                   return q + ((r + 6) >> 4);
            }
            public static void main(String[] args) {
                /*
                long count = 0;
                for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
                    if ( (i/10) != divs10(i) ) {
                        System.err.println("error dividing :" + i );
                    }
                    if ((i & 0xFFFFFFF ) == 0 ) {
                        System.out.println("Finished:" + Long.toHexString(count) + ":" + count + ":" + i);
                    }
                    count++;
                }
                System.out.println("Success:" + count);
                */
                long start = System.nanoTime();
                long count = 0L;
                int iter = 100_000;
                for (int j = 0; j < 10; j++) 
                    for (int i = -iter; i < iter; i++) {
                        count += (i/10);
                    }
                for (int j = 0; j < 10; j++) 
                    for (int i = -iter; i < iter; i++) {
                        count += divs10(i);
                    }
                System.out.println(count + " warm up done ") ;

                start = System.nanoTime();
                count = 0L;
                for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
                    count += i/10;
                }
                System.out.println(count + ", took:" + (System.nanoTime() - start) / 1000_000L + " ms, " + (System.nanoTime() - start) / ((long)Integer.MAX_VALUE - (long)Integer.MIN_VALUE) + " ns per ops" ) ;
                start = System.nanoTime();
                count = 0L;
                for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
                    count += divs10(i);
                }
                System.out.println(count + ", took:" + (System.nanoTime() - start) / 1000_000L + " ms, " + (System.nanoTime() - start) / ((long)Integer.MAX_VALUE - (long)Integer.MIN_VALUE) + " ns per ops" ) ;
           }
    }

更新：在查看较新的常春藤桥表(第 174 页(时，我看到所有延迟为 1.这意味着我之前的解释是不正确的。

对在 divs10 方法中执行的指令进行计数的尝试是 27 条(没有函数调用开销(指令。您正在执行的操作需要先完成前一个操作，然后才能启动下一个操作。因此，这意味着您应该考虑指令的延迟。根据常春藤桥指令表，所有涉及的指令都有 1 个时钟周期的延迟。这为您提供了总共 27 个时钟周期。

这与单个IDIV(8位(指令相比。在表中，我发现这需要大约 20 个时钟周期延迟。

原始估计会给出：27 个周期/20 个周期 = 慢 1.35 倍。这与你得到的结果不一致。我不是这方面的专家，但我认为这是因为使用 IDIV 指令的部门可以并行运行，因为它们是独立的。IDIV 指令的吞吐量为 8 个时钟周期。这允许 CPU 以这种方式优化指令，使其每 4 个周期可以运行大约 52 个格(这是一个估计值(。

因此，要使用位移算法执行 4 个除法，您需要 108 个周期，而 IDIV 大约需要 64 个时钟周期。这给出了：108/52 = 慢 2.1 倍。

这接近您测量的比率。我猜剩下的额外时间用于函数调用的开销。也许 CPU 的优化比我的估计要大。

当你写：

count += (i/10);

Java JIT 能够使用一些不错的技巧来优化每个常量的除法，例如">倒数乘法" - 请参阅本文以获取数学参考 - 或本文。

因此，它也许可以通过单个乘法+移位来代替此除法，这在所有情况下都比规避的divs10()函数快得多，后者对于最旧的 CPU 来说可能很快，但对于现代 CPU，整数乘法需要 1 或 1.5 个周期！"黑客的喜悦"技巧确实在普通的 386 上玩得很好，但不适用于现代 CPus。

此外，JIT 可能能够展开循环，以获得更快的过程，因为计算count += ...很容易并行。

结论：当您使用高级语言(如 Java(并在具有 JIT 的 VM 上运行时，不要期望知道代码将如何编译。即使是任何现代的C编译器也能够通过使用">倒数乘法"技巧来优化count += i/10，或者展开循环(甚至使其成为多线程(。

让您的 (JIT( 编译器完成其工作，如果性能对您来说不够，请优化您的数据结构和算法，而不是尝试"调整"编译器。如果您需要一些 CPU 级别的低级性能技巧的文档和源代码，请查看此参考资料。但请注意，您将无法在Java中使用它们(添加asm需要C/C++或Delphi编译器(。最后但并非最不重要的一点是，请记住，过早优化是万恶之源(Knuth(。

相关内容

最新更新

热门标签：