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

Question

我正在测试 hacker's delight book 中的 divs10 函数吞吐量，在我的 jdk 1.7 64 位版本 21 和 i7 intel box 上用 java 编码处理器:7vendor_id :正版英特尔CPU系列:6型号:26型号名称:Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz

我想知道为什么默认的 java 运算符/比 hacker's delight book 中的 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" ) ;

           }
    }

Answer 1

更新:查看较新的Ivy Bridge table时(第 174 页)，我看到所有的延迟都是 1。这意味着我之前的解释是不正确的。

尝试计算在 divs10 方法中执行的指令是 27(没有函数调用的开销)指令。您正在执行的操作要求在下一个操作开始之前完成前一个操作。所以这意味着你应该考虑指令的延迟。根据 Ivy Bridge 指令表，所有涉及的指令都有 1 个时钟周期的延迟。这为您提供了总共 27 个时钟周期。

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

粗略估计:27 个周期/20 个周期 = 慢 1.35 倍。这与您的结果不一致。我不是这方面的专家，但我认为这是因为使用 IDIV 指令的除法可以并行运行，因为它们是独立的。 IDIV 指令的吞吐量为 8 个时钟周期。这允许 CPU 以每 52 个周期可以运行大约 4 个除法的方式优化指令(这是一个估计值)。

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

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