BigInteger 中的乘法时间

2022-09-01 23:50:28

我的迷你基准测试:

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位大整数的乘法时间

结果:enter image description here

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

测试结果只有奇数位数。测试时间较短(n=1000,k=100)

enter image description here

奇数位数 (n=10000, k=10)enter image description here

如您所见,65000至70000之间有巨大的噪音。我想知道为什么...

奇数位 (n=10000, k=10),每 1000 次enter image description here迭代一次 导致噪声介于 50000-70000 之间System.gc()


答案 1

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

在整个基准测试周围放置一个(java)循环,并运行它多次。(如果这为您提供了与以前相同的图形...您将有证据表明这不是热身效果。目前,你没有任何经验证据。


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

  • 您正在将计时数据写入无缓冲流。这意味着大量的系统调用,以及(可能)大量的细粒度光盘写入。
  • 您正在对 进行大量调用,这可能会引入噪音。nanoTime()
  • 如果您的机器上正在运行其他内容(例如,您正在浏览网页),这将减慢您的基准测试速度并引入噪音。
  • 可能会有关于物理记忆的竞争...如果您的计算机上运行过多的RAM量。

最后,一定程度的噪音是不可避免的,因为每个调用都会生成垃圾,垃圾回收器将需要努力处理它。multiply


最后,如果您手动运行垃圾回收器(或增加堆大小)以“平滑”数据点,则您实际要做的是隐藏调用成本之一。生成的图形看起来不错,但它具有误导性:multiply

  • 嘈杂反映了现实生活中将要发生的事情。
  • 实际成本的实际成本包括运行GC以处理调用生成的垃圾的摊销成本。multiply

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

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


答案 2

如果做一个微模板,就必须先“预热”JVM,让JIT优化代码,然后才能衡量性能。否则,您将测量 JIT 完成的工作,这可能会更改每次运行的结果。

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


推荐