java - BigInteger 中的乘法时间

Question

我的迷你基准：

import java.math.*;
import java.util.*;
import java.io.*;
public class c
{
    static Random rnd = new Random();
    public static String addDigits(String a, int n)
    {
        if(a==null) return null;
        if(n<=0) return a;
        for(int i=0; i<n; i++)
            a+=rnd.nextInt(10);
        return a;
    }
    public static void main(String[] args) throws IOException
    {
        int n = 10000; \\number of iterations
        int k = 10;    \\number of digits added at each iteration

        BigInteger a;
        BigInteger b;

        String as = "";
        String bs = "";
        as += rnd.nextInt(9)+1;
        bs += rnd.nextInt(9)+1;
        a = new BigInteger(as);
        b = new BigInteger(bs);
        FileWriter fw = new FileWriter("c.txt");
        long t1 = System.nanoTime();
        a.multiply(b);
        long t2 = System.nanoTime();
        //fw.write("1,"+(t2-t1)+"\n");
        if(k>0) {
            as = addDigits(as, k-1);
            bs = addDigits(as, k-1);
        }
        for(int i=0; i<n; i++)
        {
            a = new BigInteger(as);
            b = new BigInteger(bs);
            t1 = System.nanoTime();
            a.multiply(b);
            t2 = System.nanoTime();
            fw.write(((i+1)*k)+","+(t2-t1)+"\n");
            if(i < n-1)
            {
                as = addDigits(as, k);
                bs = addDigits(as, k);
            }
            System.out.println((i+1)*k);
        }       

        fw.close();
    }
}

它测量 n 位 BigInteger 的乘法时间

结果：

你可以很容易地看到趋势，但为什么在 50000 位以上会有这么大的噪音？这是因为垃圾收集器还是有其他影响我的结果的东西？执行测试时，没有其他应用程序在运行。

测试结果只有奇数。测试更短（n=1000，k=100）

奇数位 (n=10000, k=10)

如您所见，在 65000 和 70000 之间有很大的噪音。我想知道为什么...

奇数位 (n=10000, k=10)，System.gc()每 1000 次迭代 导致 50000-70000 之间的噪声

Answer 1

我也怀疑这是 JVM 预热效应。不是涉及类加载或 JIT 编译器的预热，而是堆的预热。

在整个基准测试中放置一个（java）循环，并运行多次。（如果这为您提供与以前相同的图表......您将有证据表明这不是热身效应。目前您没有任何经验证据。）

---

另一种可能性是噪音是由您的基准测试与操作系统和/或机器上运行的其他东西的交互引起的。

• 您正在将计时数据写入无缓冲流。这意味着大量的系统调用，以及（可能）大量细粒度的磁盘写入。
• 您正在对 进行大量调用nanoTime()，这可能会引入噪音。
• 如果您的机器上正在运行其他东西（例如，您正在浏览网页），这会降低您的基准测试速度并引入噪音。
• 物理内存可能存在竞争……如果您的机器上运行的内存过多，则无法获得内存。

---

最后，一定量的噪音是不可避免的，因为这些multiply调用中的每一个都会产生垃圾，而垃圾收集器将需要工作来处理它。

---

最后，如果您手动运行垃圾收集器（或增加堆大小）以“平滑”数据点，那么您实际上所做的是隐藏multiply调用成本之一。生成的图表看起来不错，但它具有误导性：

• 噪音反映了现实生活中会发生什么。
• 真正的成本multiply实际上包括运行 GC 以处理调用产生的垃圾的摊销成本。

要获得反映BigInteger现实生活中行为方式的测量结果，您需要多次运行测试，计算平均时间并将曲线拟合到平均数据点。

请记住，游戏的真正目的是获得科学有效的结果……而不是平滑的曲线。

Answer 2

如果做微基准，必须先“预热”JVM，让JIT优化代码，然后才能衡量性能。否则，您正在衡量 JIT 完成的工作，这可能会改变每次运行的结果。

“噪音”的发生可能是因为超出了 CPU 的缓存并且性能开始下降。