java - 为什么 Math.pow(int,int) 比我天真的实现慢？

Question

昨天看到一个问为什么Math.pow(int,int)这么慢的问题，但是这个问题措辞不当，没有研究成果，所以很快就关了。

我自己做了一些测试，发现 Math.pow 方法在处理时确实比我自己的幼稚实现(甚至不是特别有效的实现)运行得非常慢带有整数参数。下面是我运行的测试代码:

class PowerTest {

    public static double myPow(int base, int exponent) {
        if(base == 0) return 0;
        if(exponent == 0) return 1;
        int absExponent = (exponent < 0)? exponent * -1 : exponent;
        double result = base;
        for(int i = 1; i < absExponent; i++) {
            result *= base;
        }
        if(exponent < 1) result = 1 / result;
        return result;
    }

    public static void main(String args[]) {
        long startTime, endTime;

        startTime = System.nanoTime();
        for(int i = 0; i < 5000000; i++) {
            Math.pow(2,2);
        }
        endTime = System.nanoTime();
        System.out.printf("Math.pow took %d milliseconds.\n", (endTime - startTime) / 1000000);

        startTime = System.nanoTime();
        for(int i = 0; i < 5000000; i++) {
            myPow(2,2);
        }
        endTime = System.nanoTime();
        System.out.printf("myPow took %d milliseconds.\n", (endTime - startTime) / 1000000);
    }

}

在我的电脑上(linux 在 intel x86_64 cpu 上)，输出几乎总是报告 Math.pow 花费了 10ms 而 myPow 花费了 2ms。这偶尔会在这里或那里波动一毫秒，但 Math.pow 平均运行 5 倍。

我做了一些研究，根据 grepcode , Math.pow 仅提供类型签名为 (double, double) 的方法，并将其推迟到 StrictMath.pow方法是本地方法调用。

Math 库仅提供一个处理 double 的 pow 函数这一事实似乎表明了这个问题的可能答案。显然，与我的仅处理整数的算法相比，必须处理 double 类型的基数或指数的可能性的幂算法将花费更长的时间来执行。然而，最后，它归结为依赖于体系结构的 native 代码(它几乎总是比 JVM 字节码运行得更快，在我的例子中可能是 C 或汇编)。 似乎在这个层面上，会进行优化以检查数据类型并在可能的情况下运行更简单的算法。

鉴于此信息，为什么在给定整数参数时， native Math.pow 方法始终比我未经优化的原始 myPow 方法运行得慢得多？

Answer 1

正如其他人所说，您不能忽略 double 的使用，因为浮点运算几乎肯定会更慢。然而，这不是唯一的原因 - 如果您更改实现以使用它们，它仍然更快。

这是因为两件事:首先是 2^2(指数，而不是异或)是一个非常快速的计算，因此您的算法可以很好地用于此 - 尝试使用来自 Random#nextInt(或 nextDouble)的两个值，您会发现 Math#pow 实际上要快得多。

另一个原因是调用本地方法有开销，这在这里实际上是有意义的，因为 2^2 计算起来很快，而你正在调用 Math#pow 这么多次。参见 What makes JNI calls slow?有关更多信息。