为什么Math.pow(int,int)比我的朴素实现慢？

昨天我看到一个问题,问为什么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花了10毫秒,而myPow花了2毫秒.这偶尔会在这里或那里波动一毫秒,但平均下降Math.pow约5倍.

我做了一些研究,根据grepcode,Math.pow只提供了一个类型签名为的方法(double, double),并且它将该StrictMath.pow方法推迟到本机方法调用.

Math图书馆只提供pow处理双打的功能这一事实似乎表明了这个问题的可能答案.显然,必须处理double类型的基数或指数的可能性的幂算法将比我的仅处理整数的算法花费更长的时间来执行.但是,最后,它归结为依赖于体系结构的本机代码(它几乎总是比JVM字节代码运行得更快,在我的情况下可能是C或汇编).似乎在这个级别上,将进行优化以检查数据类型并尽可能运行更简单的算法.

鉴于此信息,为什么在给定整数参数时,本机Math.pow方法始终比我未优化和天真的myPow方法运行得慢得多？

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

这是因为有两件事:首先是2^2(指数,而不是xor)是一个非常快速的计算,所以你的算法可以很好地使用它 - 尝试使用Random#nextInt(或nextDouble)中的两个值,你会看到它Math#pow是实际上要快得多.

另一个原因是调用本机方法有开销,这在这里实际上是有意义的,因为2^2计算速度很快,并且您调用了Math#pow很多次.请参阅是什么让JNI呼叫变慢？了解更多.