java - "Fast"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% 左右。

原文:

I was very surprised to find that the naive approach was 4x faster than the "fast" version, which was itself about 3x faster than the Math.pow() version.

我的测试使用了 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

注意:整数乘法是相当快的运算，sometimes even faster than an extra comparison .不要期望适合 long 的值会带来巨大的性能改进。在指数较大的 BigInteger 上，快速幂算法的优势将很明显。

更新

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

改进后的版本有哪些关键变化？

1. 应在不同的 JVM 实例中分别测试不同的算法，以防止配置文件污染。
2. 必须多次调用基准以允许正确编译/重新编译，直到达到稳定状态。
3. 一个基准试验应该放在一个单独的方法中，以避免堆栈替换问题。
4. y % 2 替换为 y & 1 因为 HotSpot 不会自动执行此优化。
5. 最大限度地减少了主基准循环中不相关操作的影响。

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