java - 为什么优化的素因子计数算法运行速度较慢

Question

嗨，我看到了一个计算数字不同质因数的在线答案，它看起来不是最佳的。所以我尝试改进它，但在一个简单的基准测试中，我的变体比原始版本慢得多。

该算法计算数字的不同质因数。最初使用 HashSet 来收集因子，然后使用 size 来获取它们的数量。我的“改进”版本使用 int 计数器，并将 while 循环分解为 if/while 以避免不必要的调用。

更新:tl/dr(有关详细信息，请参阅已接受的答案)

原始代码存在不必要地调用 Math.sqrt 的性能错误，已被编译器修复:

int n = ...;
// sqrt does not need to be recomputed if n does not change
for (int i = 3; i <= Math.sqrt(n); i += 2) {
    while (n % i == 0) {
        n /= i;
    }
}

编译器优化了 sqrt 调用，使其仅在 n 更改时发生。但是，通过使循环内容变得更加复杂(尽管没有功能更改)，编译器停止以这种方式进行优化，并且在每次迭代时都会调用 sqrt。

原始问题

public class PrimeFactors {

    // fast version, takes 10s for input 8
    static int countPrimeFactorsSet(int n) {
        Set<Integer> primeFactorSet = new HashSet<>();
        while (n % 2 == 0) {
            primeFactorSet.add(2);
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                primeFactorSet.add(i);
                n /= i;
            }
        }
        if (n > 2) {
            primeFactorSet.add(n);
        }
        return primeFactorSet.size();
    }

    // slow version, takes 19s for input 8
    static int countPrimeFactorsCounter(int n) {
        int count = 0; // using simple int
        if (n % 2 == 0) {
            count ++; // only add on first division
            n /= 2;
            while (n % 2 == 0) {
                n /= 2;
            }
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                count++; // only add on first division
                n /= i;
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 2) {
            count++;
        }
        return count;
    }

    static int findNumberWithNPrimeFactors(final int n) {
        for (int i = 3; ; i++) {
            // switch implementations
            if (countPrimeFactorsCounter(i) == n) {
            // if (countPrimeFactorsSet(i) == n) {
                return i;
            }
        }
    }

    public static void main(String[] args) {
        findNumberWithNPrimeFactors(8); // benchmark warmup
        findNumberWithNPrimeFactors(8);
        long start = System.currentTimeMillis();
        int result = findNumberWithNPrimeFactors(n);
        long duration = System.currentTimeMillis() - start;

        System.out.println("took ms " + duration + " to find " + result);
    }
}

原始版本的输出始终在 10 秒左右(在 java8 上)，而“优化”版本更接近 20 秒(两者打印相同的结果)。实际上，只需将单个 while 循环更改为包含 while 循环的 if block ，就已经将原始方法的速度减慢了一半。

使用-Xint以解释模式运行JVM，优化后的版本运行速度提高了3倍。使用 -Xcomp 使两种实现以相似的速度运行。因此，与使用简单 int 计数器的版本相比，JIT 似乎可以更优化使用单个 while 循环和 HashSet 的版本。

适当的微基准 ( How do I write a correct micro-benchmark in Java? ) 会告诉我其他信息吗？是否存在我忽略的性能优化原则(例如 Java performance tips )？

Answer 1

我将你的示例转换为 JMH benchmark为了进行公平的测量，事实上 set 变体的出现速度是 counter 的两倍:

Benchmark              Mode  Cnt     Score    Error   Units
PrimeFactors.counter  thrpt    5   717,976 ±  7,232  ops/ms
PrimeFactors.set      thrpt    5  1410,705 ± 15,894  ops/ms

为了找出原因，我使用内置 -prof xperfasm 分析器重新运行了基准测试。碰巧 counter 方法花费了超过 60% 的时间执行 vsqrtsd 指令 - 显然，这是 Math.sqrt(n) 的编译版本。

  0,02%   │  │  │     │  0x0000000002ab8f3e: vsqrtsd %xmm0,%xmm0,%xmm0    <-- Math.sqrt
 61,27%   │  │  │     │  0x0000000002ab8f42: vcvtsi2sd %r10d,%xmm1,%xmm1

同时，set方法中 HitTest 门的指令是idiv，即n % i编译的结果。

             │  │ ││  0x0000000002ecb9e7: idiv   %ebp               ;*irem
 55,81%      │  ↘ ↘│  0x0000000002ecb9e9: test   %edx,%edx

Math.sqrt 的运算速度很慢，这并不奇怪。但为什么第一种情况执行得更频繁呢？

线索是你在优化过程中所做的代码的转换。您将一个简单的 while 循环包装到一个额外的 if block 中。这使得控制流变得更加复杂，因此 JIT 无法将 Math.sqrt 计算提升到循环之外，并且必须在每次迭代时重新计算它。

我们需要稍微帮助 JIT 编译器才能恢复性能。让我们手动将 Math.sqrt 计算提升到循环之外。

    static int countPrimeFactorsSet(int n) {
        Set<Integer> primeFactorSet = new HashSet<>();
        while (n % 2 == 0) {
            primeFactorSet.add(2);
            n /= 2;
        }
        double sn = Math.sqrt(n);  // compute Math.sqrt out of the loop
        for (int i = 3; i <= sn; i += 2) {
            while (n % i == 0) {
                primeFactorSet.add(i);
                n /= i;
            }
            sn = Math.sqrt(n);     // recompute after n changes
        }
        if (n > 2) {
            primeFactorSet.add(n);
        }
        return primeFactorSet.size();
    }

    static int countPrimeFactorsCounter(int n) {
        int count = 0; // using simple int
        if (n % 2 == 0) {
            count ++; // only add on first division
            n /= 2;
            while (n % 2 == 0) {
                n /= 2;
            }
        }
        double sn = Math.sqrt(n);  // compute Math.sqrt out of the loop
        for (int i = 3; i <= sn; i += 2) {
            if (n % i == 0) {
                count++; // only add on first division
                n /= i;
                while (n % i == 0) {
                    n /= i;
                }
                sn = Math.sqrt(n);     // recompute after n changes
            }
        }
        if (n > 2) {
            count++;
        }
        return count;
    }

现在 counter 方法变得更快了!甚至比 set 快一点(这是完全可以预料的，因为它执行相同的计算量，不包括 Set 开销)。

Benchmark              Mode  Cnt     Score    Error   Units
PrimeFactors.counter  thrpt    5  1513,228 ± 13,046  ops/ms
PrimeFactors.set      thrpt    5  1411,573 ± 10,004  ops/ms

请注意，set 性能没有改变，因为 JIT 本身能够进行相同的优化，这要归功于更简单的控制流图。

结论:Java 性能是一件非常复杂的事情，尤其是在谈论微优化时。 JIT 优化很脆弱，如果没有 JMH 这样的专门工具，很难理解 JVM 的想法。和分析器。