tiempo de multiplicación en BigInteger

Question

mi mini punto de referencia:

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

Mide el tiempo de multiplicación de n dígitos BigInteger

Resultado:

Se puede ver fácilmente la tendencia, pero por qué hay gran ruido por encima de 50000 dígitos? ¿Es por el recolector de basura o hay algo más que afecte mis resultados? Al realizar la prueba, no se ejecutaban otras aplicaciones.

Resultado de la prueba con solo dígitos impares. La prueba fue más corto (n = 1000, K = 100)

dígitos impares (n = 10.000, k = 10)

Como se puede ver que hay una gran ruido entre 65.000 y 70000. me pregunto por qué ...

dígitos impar (n = 10 000, K = 10), System.gc() cada 1000 iteraciones resultados en ruido entre 50000-70000

Answer 1

También sospecho que este es un efecto de calentamiento de JVM. No calentamiento que implica la carga de clases o el compilador JIT, pero el calentamiento del montón.

Coloque un bucle (java) alrededor de la referencia completa y ejecútelo varias veces. (Si esto le da los mismos gráficos como antes ... usted tendrá pruebas que esto no es un efecto de calentamiento. En la actualidad no tiene ninguna evidencia empírica de un modo u otro.)

---

Otra posibilidad es que el ruido sea causado por las interacciones de su punto de referencia con el SO y/u otras cosas que se ejecutan en la máquina.

• Está escribiendo sus datos de sincronización en una secuencia sin búfer. Eso significa MUCHAS llamadas de sys, y (potencialmente) muchas grabaciones de discos de grano fino.
• Usted está haciendo MUCHOS llamadas a nanoTime(), y podría introducir ruido.
• Si algo más está ejecutándose en su máquina (por ejemplo, si está navegando por la web) que ralentizará su punto de referencia por un momento e introducirá ruido.
• Puede haber competencia sobre la memoria física ... si tiene demasiada ejecución en su máquina por la cantidad de RAM.

---

Por último, una cierta cantidad de ruido es inevitable, porque cada una de esas llamadas multiply genera la basura, y el recolector de basura va a tener que trabajar para tratar con él.

---

Finalmente, por último, si se ejecuta manualmente el recolector de basura (o aumentar el tamaño de la pila) para "suavizar" los puntos de datos, lo que realmente está haciendo es ocultar uno de los costos de las llamadas multiply. Los gráficos resultantes se ven bien, pero es engañoso:

• El ruido refleja lo que sucederá en la vida real.
• El costo real del multiply en realidad incluye el costo amortizado de ejecutar el GC para hacer frente a la basura generada por la llamada.

para obtener un mediciones que reflejan la forma en que se comporta BigInteger en la vida real, lo que necesita para ejecutar la prueba de un gran número de veces, calcular los tiempos promedio y ajustar una curva a los puntos de datos promedio.

Recuerde, el objetivo real del juego es obtener resultados científicamente válidos ... no una curva suave.

Answer 2

Si hace un microbenchmark, primero debe "calentar" la JVM para que el JIT optimice el código, y luego puede medir el rendimiento. De lo contrario, está midiendo el trabajo realizado por el JIT y eso puede cambiar el resultado en cada ejecución.

El "ruido" ocurre probablemente porque se excede la memoria caché de la CPU y el rendimiento comienza a degradarse.