tempo Moltiplicazione in BigInteger

Question

mio mini punto di riferimento:

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(); 
    } 
} 

Misura tempo moltiplicazione di n cifre BigInteger

Risultato:

Si può facilmente vedere il trend, ma perché c'è così grande rumore superiore a 50000 cifre? È a causa del garbage collector o c'è qualcos'altro che influenza i miei risultati? Durante l'esecuzione del test, non c'erano altre applicazioni in esecuzione.

Risultato dal test con solo cifre dispari. Il test è stato più breve (n = 1000, k = 100)

cifre dispari (n = 10000, k = 10)

Come potete vedere c'è un enorme rumore tra 65000 e 70000. mi chiedo perché ...

cifre dispari (n = 10000, k = 10), System.gc() ogni 1000 iterazioni Risultati in rumore tra 50000-70000

Answer 1

Ho anche il sospetto che si tratti di un effetto di riscaldamento JVM. Non riscaldamento che coinvolge il caricamento di classi o il compilatore JIT, ma il riscaldamento dell'heap.

Mettere un ciclo (java) attorno all'intero benchmark ed eseguirlo un numero di volte. (Se questo ti dà gli stessi grafici come prima ... si avrà la prova che questo non è un effetto di riscaldamento. Al momento non si dispone di alcuna prova empirica in un modo o nell'altro.)

---

Un'altra possibilità è che il rumore è causato dalle interazioni del tuo benchmark con il sistema operativo e/o altre cose in esecuzione sulla macchina.

• Si stanno scrivendo i dati di temporizzazione su un flusso non bufferizzato. Ciò significa MOLTE SERIE di syscalls e (potenzialmente) molte scritture di dischi a grana fine.
• Si stanno effettuando MOLTE chiamate a nanoTime() e che potrebbe introdurre rumore.
• Se qualcos'altro è in esecuzione sulla macchina (ad esempio, la navigazione sul Web) rallenterà il benchmark per un po 'e introdurrà rumore.
• Potrebbe esserci competizione sulla memoria fisica ... se hai troppo lavoro sulla tua macchina per la quantità di RAM.

---

Infine, una certa quantità di rumore è inevitabile, perché ciascuno di tali multiply chiamate genera rifiuti, e il collettore garbage avrà bisogno di lavorare a trattare con esso.

---

Infine, infine, se si esegue manualmente il garbage collector (o aumentare la dimensione heap) per "appianare" i punti di dati, quello che si sta effettivamente facendo è nascondere uno dei costi di multiply chiamate. I grafici risultanti sembra bello, ma è fuorviante:

• La rumorosità rispecchia ciò che accadrà nella vita reale.
• Il costo reale di multiply include effettivamente il costo ammortizzato di esecuzione del GC per gestire la spazzatura generata dalla chiamata.

per ottenere una misurazione che riflettono il modo in cui si comporta BigInteger nella vita reale, è necessario eseguire il test di un gran numero di volte, calcolare i tempi medi e montare una curva ai punti di dati medi.

Ricorda, il vero obiettivo del gioco è ottenere risultati scientificamente validi ... non una curva uniforme.

Answer 2

Se si esegue un microbenchmark, è necessario "riscaldare" prima JVM per consentire al JIT di ottimizzare il codice e quindi misurare le prestazioni. Altrimenti si sta misurando il lavoro svolto dalla JIT e questo può cambiare il risultato ad ogni sessione.

Il "disturbo" si verifica probabilmente perché la cache della CPU viene superata e le prestazioni iniziano a peggiorare.