Java中的"快速"整数权力

Question

[简答:糟糕的基准测试方法.你觉得我现在已经想到了.]

问题表现为"找到一种快速计算x ^ y的方法,其中x和y是正整数".典型的"快速"算法如下所示:

public long fastPower(int x, int y) {
  // Replaced my code with the "better" version described below,
  // but this version isn't measurably faster than what I had before
  long base = x; // otherwise, we may overflow at x *= x.
  long result = y % 2 == 1 ? x : 1;
  while (y > 1) {
    base *= base;
    y >>= 1;
    if (y % 2 == 1) result *= base;
  }

  return result;
}

我想看看这比说的快多少,调用Math.pow(),或者使用像x这样自己乘以y的简单方法,如下所示:

public long naivePower(int x, int y) {
  long result = 1;
  for (int i = 0; i < y; i++) {
    result *= x;
  }
  return result;
}

编辑:好的,我(正确地)指出我的基准测试代码没有消耗结果,这完全抛弃了一切.一旦我开始使用结果,我仍然看到天真的方法比"快速"方法快25%.

原文:

我很惊讶地发现天真的方法比"快速"版本快4倍,"快速"版本本身比Math.pow()版本快3倍.

我的测试是使用10,000,000次试验(然后是1亿次,只是为了确保JIT有时间预热),每次都使用随机值(以防止调用被优化掉)2 <= x <= 3,并且25 < = y <= 29.我选择了一个窄范围的值,这些值不会产生大于2 ^ 63的结果,但是偏向于使用更大的指数来尝试给"快速"版本带来优势.我正在预先生成10,000个伪随机数,以便从时间中消除代码的那部分.

据我所知,对于小型指数,天真的版本可能会更快."快速"版本有两个分支而不是一个,并且通常会执行两倍于天真的算术/存储操作 - 但我希望对于大型指数,这仍然会导致快速方法节省一半的操作最好的情况,在最坏的情况下差不多.

任何人都知道为什么天真的方法会比"快速"版本快得多,即使数据偏向于"快速"版本(即更大的指数)？该代码中的额外分支是否在运行时占据了很大的差异？

基准测试代码(是的,我知道我应该使用一些框架用于"官方"基准测试,但这是一个玩具问题) - 更新为预热,并消耗结果:

PowerIf[] powers = new PowerIf[] {
  new EasyPower(), // just calls Math.pow() and cast to int
  new NaivePower(),
  new FastPower()
};

Random rand = new Random(0); // same seed for each run
int randCount = 10000;
int[] bases = new int[randCount];
int[] exponents = new int[randCount];
for (int i = 0; i < randCount; i++) {
  bases[i] = 2 + rand.nextInt(2);
  exponents[i] = 25 + rand.nextInt(5);
}

int count = 1000000000;

for (int trial = 0; trial < powers.length; trial++) {
  long total = 0;
  for (int i = 0; i < count; i++) { // warm up
    final int x = bases[i % randCount];
    final int y = exponents[i % randCount];
    total += powers[trial].power(x, y);
  }
  long start = System.currentTimeMillis();
  for (int i = 0; i < count; i++) {
    final int x = bases[i % randCount];
    final int y = exponents[i % randCount];
    total += powers[trial].power(x, y);
  }
  long end = System.currentTimeMillis();
  System.out.printf("%25s: %d ms%n", powers[trial].toString(), (end - start)); 
  System.out.println(total);
}

产生输出:

                EasyPower: 7908 ms
-407261252961037760
               NaivePower: 1993 ms
-407261252961037760
                FastPower: 2394 ms
-407261252961037760

使用随机数和试验的参数确实改变了输出特性,但测试之间的比率始终与所示的相同.

Answer 1

你有两个问题fastPower:

1. 这是更好地更换y % 2 == 0与(y & 1) == 0; 按位运算更快.
2. 您的代码总是递减y并执行额外的乘法,包括y偶数时的情况.将这部分放入else条款中会更好.

无论如何,我猜你的基准测试方法并不完美.4倍的性能差异听起来很奇怪,如果没有看到完整的代码就无法解释.

在应用了上述改进之后,我已经使用JMH基准测试验证了fastPower确实比naivePower使用1.3倍到2倍的因素更快.

package bench;

import org.openjdk.jmh.annotations.*;

@State(Scope.Benchmark)
public class FastPow {
    @Param("3")
    int x;
    @Param({"25", "28", "31", "32"})
    int y;

    @Benchmark
    public long fast() {
        return fastPower(x, y);
    }

    @Benchmark
    public long naive() {
        return naivePower(x, y);
    }

    public static long fastPower(long x, int y) {
        long result = 1;
        while (y > 0) {
            if ((y & 1) == 0) {
                x *= x;
                y >>>= 1;
            } else {
                result *= x;
                y--;
            }
        }
        return result;
    }

    public static long naivePower(long x, int y) {
        long result = 1;
        for (int i = 0; i < y; i++) {
            result *= x;
        }
        return result;
    }
}

结果:

Benchmark      (x)  (y)   Mode  Cnt    Score   Error   Units
FastPow.fast     3   25  thrpt   10  103,406 ± 0,664  ops/us
FastPow.fast     3   28  thrpt   10  103,520 ± 0,351  ops/us
FastPow.fast     3   31  thrpt   10   85,390 ± 0,286  ops/us
FastPow.fast     3   32  thrpt   10  115,868 ± 0,294  ops/us
FastPow.naive    3   25  thrpt   10   76,331 ± 0,660  ops/us
FastPow.naive    3   28  thrpt   10   69,527 ± 0,464  ops/us
FastPow.naive    3   31  thrpt   10   54,407 ± 0,231  ops/us
FastPow.naive    3   32  thrpt   10   56,127 ± 0,207  ops/us

注意:整数乘法运算非常快,有时甚至比额外比较更快.不要期望通过适合的值来实现巨大的性能提升long.快速功率算法的优势将在BigInteger较大的指数上显而易见.

更新

由于作者发布了基准测试,我必须承认,令人惊讶的性能结果来自常见的基准测试陷阱.我在保留原始方法的同时改进了基准,现在它表明FastPower确实比这更快NaivePower,见到这里.

改进版本的主要变化是什么？

1. 应在不同的JVM实例中单独测试不同的算法,以防止轮廓污染.
2. 必须多次调用基准测试才能进行正确的编译/重新编译,直到达到稳定状态.
3. 一个基准测试应该放在一个单独的方法中,以避免堆栈上的替换问题.
4. y % 2y & 1由于HotSpot不会自动执行此优化,因此将替换为.
5. 最大限度地减少主要基准测试循环中不相关操作的影响.

手动编写微基准是一项艰巨的任务.这就是为什么强烈建议使用适当的基准测试框架,如JMH.