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%。

原文：

我的测试使用了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倍的性能差异听起来很诡异，没有看到完整的代码就无法解释。

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%2被替换为y&1，因为HotSpot不会自动执行此优化。
5. 最小化了主基准循环中不相关操作的影响。

手工编写微基准是一项困难的任务。这就是为什么强烈建议使用像JMH这样的适当的基准测试框架的原因。