BigDecimal toPlainString 生成字符串需要很长时间

Question

我在 Java 中编写了一个程序来计算像 100 万这样的极端阶乘。它所做的本质上是从 1 到 n 开始一个循环，每次迭代，将 BigDecimal 乘以循环中计数器变量的值。循环完成后，它调用 BigDecimal#toPlainString() 其中 returns 作为字符串生成的数字。但是，调用此方法需要很长时间才能执行。例如，在下面的代码中：

public static void main(String[] args) {
        BigDecimal number = new BigDecimal(1);
        long startTime = System.currentTimeMillis();
        for (int i = 1; i < 500000; i++) {
            number = number.multiply(new BigDecimal(i));
        }
        System.out.println("Generating took: " + (System.currentTimeMillis() - startTime) + "ms. Creating String.");
        startTime = System.currentTimeMillis();
        String result = number.toPlainString();
        System.out.println("String generation took: " + (System.currentTimeMillis() - startTime) + "ms");
        FileUtils.writeStringToFile(new File("Path/To/File"), result);
    }

控制台的输出是：

Generating took: 181324ms. Creating String.
String generation took: 710498ms

这表明方法 toPlainString() 花费了多长时间。

我知道我们正在处理巨大的数字（在上面的例子中大约是一百万位数）但我想知道是否有任何方法可以加快这种方法，我应该如何去做？

谢谢！

编辑#1: post中添加毫秒时间计算的唯一原因是带来'long' 进行预测，并可能演示代码的行为，以防所有读者都无法重现问题。我想做的是确定为什么我的情况需要这么长时间，最重要的是如何加快转换为字符串的过程。

Answer 1

首先，您的基准测试不可重现。在您的情况下，阶乘部分花费了 181324 毫秒，字符串生成花费了 710498 毫秒，因此字符串生成是 slow 作为阶乘部分的 710498 / 181324 = 3.9 倍。

当我运行像你写的那样写了一遍，它给出了这些结果。

Generating took: 90664ms. Creating String.
String generation took: 3465ms

因此字符串生成速度为 90644 / 3465 = 阶乘部分的 26 倍。

当你运行一个基准时，你需要运行多次取平均值。特别是当你像你一样做一个 long-running 微基准测试时，因为你的计算机上可能同时发生了很多其他事情 - 也许你的病毒检查程序启动了，或者你的 Java 进程被换出了磁盘由于内存不足，或者 Java 决定进行完整的垃圾回收。

其次，您没有预热 VM，因此不清楚您在对什么进行基准测试。您是在对 HotSpot 编译引擎的本机编译器还是您的实际代码进行基准测试？这就是为什么您总是需要在像您这样的运行ning 微基准测试之前预热 VM。

最好的方法是使用适当的微基准测试框架。另一种方法是运行你的代码更多次（使用 for-loop），当它稳定在不再减少的时间上时，你有一个很好的迹象表明预热已经完成，你可以采取接下来运行秒的平均值得出一个数字。

运行它在我的 MacBookPro 上，这导致阶乘部分的平均时间为 80144 毫秒，字符串生成的平均时间为 2839 毫秒（请注意，我还没有为此调查内存使用情况）。

因此字符串生成速度是 80144 / 2839 = 阶乘部分的 28 倍。

如果您可以在您的机器上多次重现相同的结果，而当您运行您的程序根本没有触及它，并且您的机器有足够的内存时，那么就会发生一些有趣的事情.但问题不在 BigDecimal 中的 toPlainString() 方法中 - 该方法比代码的阶乘部分快得多。

Answer 2

为什么BigDecimal#PlainString用Java7生成字符串的时间很长的原因是：在Java7中实现的效率很低。幸运的是在 Java 8 中更快。

在这里，可能需要注意的是 在这种特殊情况下，它实际上并不是 BigDecimal 中的字符串创建，而是 BigInteger 中的字符串创建].在给定示例中计算的值是一个大阶乘，因此实际上是一个整数值。 BigDecimal 的内部 scale 字段将是 0，查看 toPlainString 方法表明，在这种情况下，内部 intVal 字段将被返回：

public String toPlainString() {
    if(scale==0) {
        if(intCompact!=INFLATED) {
            return Long.toString(intCompact);
        } else {
            return intVal.toString();
        }
    }
    ...
}

这个 intVal 字段是一个 BigInteger，这才是真正的罪魁祸首。

下面的程序不是作为一个合适的"microbenchmark"，但只应该给出性能的估计：它创建了几个阶乘，并生成了字符串这些的表示：

import java.math.BigDecimal;

public class BigDecimalToPlainStringPerformance
{
    public static void main(String[] args)
    {
        for (int n = 10000; n <= 50000; n += 5000)
        {
            BigDecimal number = factorial(n);
            long before = System.nanoTime();
            String result = number.toPlainString();
            long after = System.nanoTime();

            double ms = (after - before) / 1e6;
            System.out.println(n + "! took " + ms +
                " ms, length " + result.length());
        }
    }

    private static BigDecimal factorial(int n)
    {
        BigDecimal number = new BigDecimal(1);
        for (int i = 1; i < n; i++)
        {
            number = number.multiply(new BigDecimal(i));
        }
        return number;
    }

}

使用 Java 7 (u07)，在我的（旧）PC 上，输出是

10000! took 514.98249 ms, length 35656
15000! took 1232.86507 ms, length 56126
20000! took 2364.799995 ms, length 77333
25000! took 3877.565724 ms, length 99090
30000! took 5814.925361 ms, length 121283
35000! took 8231.13608 ms, length 143841
40000! took 11088.823021 ms, length 166709
45000! took 14344.778177 ms, length 189850
50000! took 18155.089823 ms, length 213232

幸运的是，此性能问题已在 Java 8 中修复。使用 Java 8 (u45)，输出为

10000! took 77.20227 ms, length 35656
15000! took 113.811951 ms, length 56126
20000! took 188.293764 ms, length 77333
25000! took 261.328745 ms, length 99090
30000! took 355.001264 ms, length 121283
35000! took 481.912925 ms, length 143841
40000! took 610.812827 ms, length 166709
45000! took 698.80725 ms, length 189850
50000! took 840.87391 ms, length 213232

表明性能得到了显着改善。

通过快速浏览 OpenJDK 中的提交日志，有一个提交可能与此处最相关：

Accelerate conversion to string by means of Schoenhage recursive base conversion

（我没有验证这个，但它似乎是唯一一个致力于提高toString性能的）

BigDecimal toPlainString 生成字符串需要很长时间

BigDecimal toPlainString takes very long to generate String

java

performance

factorial

bigdecimal