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）ループを配置し、それを何度も実行します。（これで以前と同じグラフが得られた場合...これはウォームアップ効果ではないという証拠があります。現在、何らかの経験的証拠はありません。）

---

もう1つの可能性は、ベンチマークがOSやマシン上で実行されている他のものと相互作用することによってノイズが発生することです。

• タイミングデータをバッファリングされていないストリームに書き込んでいます。これは、多くのシステムコール、および（潜在的に）多くのきめ細かいディスク書き込みを意味します。
• にたくさんの電話をかけているnanoTime()ので、ノイズが発生する可能性があります。
• マシン上で他の何かが実行されている場合（たとえば、Webブラウジングしている場合）、ベンチマークが少し遅くなり、ノイズが発生します。
• 物理メモリをめぐって競合が発生する可能性があります...RAMの量に対してマシンで実行しすぎている場合。

---

multiply最後に、これらの呼び出しのそれぞれがガベージを生成し、ガベージコレクタがそれに対処するために作業する必要があるため、ある程度のノイズは避けられません。

---

最後に、ガベージコレクターを手動で実行して（またはヒープサイズを増やして）データポイントを「平滑化」する場合、実際に行っているのは、multiply呼び出しのコストの1つを隠すことです。結果のグラフは見栄えがしますが、誤解を招く可能性があります。

• 騒々しさは、実生活で何が起こるかを反映しています。
• 実際の実際のコストにはmultiply、呼び出しによって生成されたガベージを処理するためにGCを実行するための償却コストが含まれます。

BigInteger実際の動作を反映した測定値を取得するには、テストを何度も実行し、平均時間を計算して、曲線を平均データポイントに適合させる必要があります。

ゲームの本当の目的は、科学的に有効な結果を得ることであり、滑らかな曲線ではないことを忘れないでください。

Answer 2

マイクロベンチマークを実行する場合は、最初にJVMを「ウォームアップ」して、JITにコードを最適化させてから、パフォーマンスを測定する必要があります。それ以外の場合は、JITによって実行された作業を測定しているため、実行ごとに結果が変わる可能性があります。

「ノイズ」は、CPUのキャッシュを超えて、パフォーマンスが低下し始めたことが原因である可能性があります。