java - Tiempo de multiplicación en BigInteger

benchmarking

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 BigInteger de n dígitos

Resultado:

Puede ver fácilmente la tendencia, pero ¿por qué hay un ruido tan grande por encima de los 50000 dígitos? ¿Es debido al recolector de basura o hay algo más que afecta mis resultados? Al realizar la prueba, no había otras aplicaciones en ejecución.

Resultado de la prueba con sólo dígitos impares. La prueba fue más corta (n = 1000, k = 100)

Dígitos impares (n = 10000, k = 10)

Como puede ver, hay un gran ruido entre 65000 y 70000. Me pregunto por qué ...

Dígitos impares (n = 10000, k = 10), System.gc() cada 1000 iteraciones Resultados en ruido entre 50000-70000.

Answer 1

Si hace una marca microbiológica, primero debe "calentar" la JVM para permitir 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 el caché de la CPU y el rendimiento comienza a degradarse.

Answer 2

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

Coloque un bucle (java) alrededor de todo el índice de referencia y ejecútelo varias veces. (Si esto te da los mismos gráficos que antes ... tendrás evidencia de que esto no es un efecto de calentamiento. Actualmente no tienes 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 sistema operativo y / u otras cosas que se ejecutan en la máquina.

• Estás escribiendo tus datos de tiempo en un flujo no almacenado en búfer. Eso significa MUCHAS SISTEMAS, y (potencialmente) muchas escrituras de disco de grano fino.
• Usted está haciendo nanoTime() llamadas a nanoTime() , y eso podría nanoTime() ruido.
• Si se está ejecutando algo más en su máquina (por ejemplo, está navegando por la web) que ralentizará un poco su índice de referencia e introducirá ruido.
• Podría haber competencia sobre la memoria física ... si tiene demasiada ejecución en su máquina por la cantidad de RAM.

Finalmente, una cierta cantidad de ruido es inevitable, porque cada una de esas multiply llamadas genera basura, y el recolector de basura tendrá que trabajar para lidiar con eso.

Finalmente, si ejecuta manualmente el recolector de basura (o aumenta el tamaño del montón) para "suavizar" los puntos de datos, lo que realmente está haciendo es ocultar uno de los costos de multiply llamadas. Los gráficos resultantes se ven bien, pero son engañosos:

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

Para obtener mediciones que reflejen la forma en que BigInteger comporta en la vida real, debe ejecutar la prueba una gran cantidad de veces, calcular 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.