java - ¿Por qué el rendimiento de la adición de bytes es tan impredecible?

benchmarking

Question

Hace unas horas respondí a otra pregunta de desbordamiento de pila, y dio un resultado muy sorprendente. La respuesta se puede encontrar here . La respuesta fue / es parcialmente incorrecta, sin embargo, me siento centrado en la adición de bytes.

Estrictamente, en realidad es una adición de byte a largo.

Este es el código de referencia que he estado usando:

public class ByteAdditionBenchmark {
    private void start() {
        int[] sizes = {
            700_000,
            1_000,
            10_000,
            25_000,
            50_000,
            100_000,
            200_000,
            300_000,
            400_000,
            500_000,
            600_000,
            700_000,
        };

        for (int size : sizes) {
            List<byte[]> arrays = createByteArrays(size);
            //Warmup
            arrays.forEach(this::byteArrayCheck);
            benchmark(arrays, this::byteArrayCheck, "byteArrayCheck");
        }
    }

    private void benchmark(final List<byte[]> arrays, final Consumer<byte[]> method, final String name) {
        long start = System.nanoTime();
        arrays.forEach(method);
        long end = System.nanoTime();
        double nanosecondsPerIteration = (end - start) * 1d / arrays.size();
        System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + " ns");
    }

    private List<byte[]> createByteArrays(final int amount) {
        Random random = new Random();
        List<byte[]> resultList = new ArrayList<>();
        for (int i = 0; i < amount; i++) {
            byte[] byteArray = new byte[4096];
            byteArray[random.nextInt(4096)] = 1;
            resultList.add(byteArray);
        }
        return resultList;
    }

    private boolean byteArrayCheck(final byte[] array) {
        long sum = 0L;
        for (byte b : array) {
            sum += b;
        }
        return (sum == 0);
    }

    public static void main(String[] args) {
        new ByteAdditionBenchmark().start();
    }
}

Y estos son los resultados que he estado obteniendo:

Punto de referencia: byteArrayCheck / iterations: 700000 / time por iteration: 50.26538857142857 ns
Punto de referencia: byteArrayCheck / iterations: 1000 / time por iteration: 20.12 ns
Punto de referencia: byteArrayCheck / iterations: 10000 / time por iteration: 9.1289 ns
Punto de referencia: byteArrayCheck / iterations: 25000 / time por iteration: 10.02972 ns
Punto de referencia: byteArrayCheck / iterations: 50000 / time por iteration: 9.04478 ns
Punto de referencia: byteArrayCheck / iterations: 100000 / time por iteration: 18.44992 ns
Punto de referencia: byteArrayCheck / iterations: 200000 / time por iteration: 15.48304 ns
Punto de referencia: byteArrayCheck / iterations: 300000 / time por iteration: 15.806353333333334 ns
Punto de referencia: byteArrayCheck / iterations: 400000 / time por iteration: 16.923685 ns
Punto de referencia: byteArrayCheck / iterations: 500000 / time por iteration: 16.131066 ns
Punto de referencia: byteArrayCheck / iterations: 600000 / time por iteration: 16.435461666666665 ns
Punto de referencia: byteArrayCheck / iterations: 700000 / time por iteration: 17.107615714285714 ns

Que yo sepa, la JVM ya se ha calentado completamente después de las primeras 700000 iteraciones antes de que empiece a escupir datos de evaluación comparativa.

¿Cómo puede ser entonces que, a pesar del calentamiento, el rendimiento sigue siendo impredecible? Casi inmediatamente después de la adición de byte de calentamiento se vuelve increíblemente rápido, pero después de eso parece converger nuevamente a un nominal de 16 ns por adición nuevamente.

Las pruebas se ejecutaron en una PC con un procesador Intel i7 3770 y 16 GB de RAM, por lo que no puedo ir más allá de las 700000 iteraciones. Se está ejecutando en Windows 8.1 de 64 bits si eso importa.

Resulta que el JIT estaba optimizando todo, según la sugerencia de raphw .

Por lo tanto, reemplacé el método de referencia con lo siguiente:

private void benchmark(final List<byte[]> arrays, final Predicate<byte[]> method, final String name) {
    long start = System.nanoTime();
    boolean someUnrelatedResult = false;
    for (byte[] array : arrays) {
        someUnrelatedResult |= method.test(array);
    }
    long end = System.nanoTime();
    double nanosecondsPerIteration = (end - start) * 1d / arrays.size();
    System.out.println("Result: " + someUnrelatedResult);
    System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + "ns");
}

Esto garantizará que no se pueda optimizar y que los resultados de las pruebas también lo muestren (se omite la impresión del resultado para mayor claridad):

Punto de referencia: byteArrayCheck / iterations: 700000 / time por iteration: 1658.2627914285715 ns
Punto de referencia: byteArrayCheck / iterations: 1000 / time por iteration: 1241.706 ns
Punto de referencia: byteArrayCheck / iterations: 10000 / time por iteration: 1215.941 ns
Punto de referencia: byteArrayCheck / iterations: 25000 / time por iteration: 1332.94656 ns
Punto de referencia: byteArrayCheck / iterations: 50000 / time por iteration: 1456.0361 ns
Punto de referencia: byteArrayCheck / iterations: 100000 / time por iteration: 1753.26777 ns
Punto de referencia: byteArrayCheck / iterations: 200000 / time por iteration: 1756.93283 ns
Punto de referencia: byteArrayCheck / iterations: 300000 / time por iteration: 1762.9992266666666 ns
Punto de referencia: byteArrayCheck / iterations: 400000 / time por iteration: 1806.854815 ns
Punto de referencia: byteArrayCheck / iterations: 500000 / time por iteration: 1784.09091 ns
Punto de referencia: byteArrayCheck / iterations: 600000 / time por iteration: 1804.6096366666666 ns
Punto de referencia: byteArrayCheck / iterations: 700000 / time por iteration: 1811.0597585714286 ns

Yo diría que estos resultados parecen mucho más convincentes con respecto al tiempo de cálculo. Sin embargo, mi pregunta sigue en pie. Con las pruebas repetidas en tiempos aleatorios, el mismo patrón sigue siendo que los puntos de referencia con un número bajo de iteraciones son más rápidos que aquellos con más iteraciones, aunque parecen estabilizarse a 100,000 iteraciones o en algún lugar más bajo.

¿Cuál es la explicación?

Answer 1

Como muchas cosas en informática, depende. Trabajar con un sistema operativo Windows 7 como señaló Dawnkeeper puede ser parte del problema.

La realidad es que todos los procesos en una computadora comparten la CPU (incluso las CPU de varios núcleos). Por lo tanto, su proceso es solo uno de docenas, quizás cientos de procesos que todos necesitan tiempo en la CPU. Su proceso probablemente tenga una prioridad más alta, por lo que pasará más tiempo en la CPU que, por ejemplo, el proceso que limpia los archivos en segundo plano (nuevamente, señalado por Dawnkeeper).

Algo que a veces complica la compartición de la CPU son los procesos que se involucran en la E / S. Cada vez que algo necesita imprimir en la pantalla o obtener algo del disco, es LENTO. Cada vez que se inicia un proceso, la CPU hace una de dos cosas. Si se trata de un proceso "agradable", se guardará donde está, se apagará todo y se apagará. Si el proceso está involucrado en la E / S, esto llevará algún tiempo. La otra opción es que el proceso es ''importante'' y continuará en su tarea hasta que alcance un buen punto para detenerse. Esto no es diferente cuando alguien dice "Oye, necesito hablar contigo" y tú respondes "Este video de YouTube terminará en 20 segundos, espera".

Espero que eso ayude. La JVM es solo otro proceso en los ojos de las computadoras.

EDITAR: preguntas de aclaración: ¿cómo maneja esas declaraciones impresas? ¿Están siendo impresos en la pantalla? Escrito en un archivo? ¿Se almacena en la memoria hasta que se completa la ejecución y luego se escribe en un archivo?

EDIT 2: this puede ayudarte a cambiar la prioridad.

Answer 2

Esto podría ser muchas cosas. Entre ellos: ventanas y relojes.

Windows : incluso si no está ejecutando nada más, el sistema puede decidir que necesita el núcleo en el que se ejecuta su código para pulir algunos gráficos o desempolvar algunos archivos olvidados.

Relojes : se llama System.nanoTime() , pero esto no significa que los valores cambien tan rápido. Hace un tiempo hice una prueba en ''System.currentTimeMillis ()'' y el valor solo cambiaba cada 10 ms.

Answer 3

La razón de su resultado es que realmente no sabe lo que está midiendo. El compilador justo a tiempo de Java es sin duda echando un vistazo a su código y puede suceder que no esté midiendo nada.

El compilador es lo suficientemente inteligente como para darse cuenta de que su List<byte[]> no se usa para nada. Por lo tanto, eventualmente eliminará todo el código relacionado de su aplicación en ejecución. Por lo tanto, es muy probable que su punto de referencia mida una aplicación cada vez más vacía.

La respuesta a todas estas preguntas es siempre: no vale la pena tener una discusión antes de que veamos un punto de referencia válido. Los arneses de evaluación comparativa como el JMH (que puedo recomendar) conocen un concepto llamado agujero negro . Los agujeros negros están destinados a confundir al compilador justo a tiempo para pensar que un valor computado realmente se usa para algo, aunque no lo sea. Con tales agujeros negros, de lo contrario el código que se borra como no-op permanecerá.

Otro problema típico de los puntos de referencia de cosecha propia son los bucles optimizados. De nuevo, el compilador justo a tiempo notará que el bucle da como resultado el mismo cálculo para cualquier iteración y, por lo tanto, eliminará el bucle por completo. Con un arnés de evaluación comparativa (de calidad), solo sugerirá una serie de bucles para ejecutar en lugar de codificarlos de forma rígida. De esta manera, el arnés puede hacerse cargo de engañar al compilador.

Escriba un punto de referencia con JMH, verá que sus tiempos medidos serán bastante diferentes.

En cuanto a su actualización : sólo puedo repetir. Nunca confíe en un punto de referencia no compartido! Una forma fácil de averiguar qué hace JVM con su código es ejecutar JITwatch. La principal preocupación con su índice de referencia es que ignora los perfiles de JVM. Un perfil es un intento de la JVM para recordar las propiedades de su código en las que luego basa su optimización. Para su punto de referencia, mezcle los perfiles de diferentes carreras juntos. La JVM luego tiene que renovar su perfil actual y volver a compilar el código de byte sobre la marcha, lo que cuesta tiempo.

Para evitar este problema, un arnés como JMH le permite generar un nuevo proceso JVM para cada punto de referencia. Esto es lo que estoy midiendo con un punto de referencia aprovechado:

Benchmark                    Mode   Samples         Mean   Mean error    Units
o.s.MyBenchmark.test100k     avgt        20     1922.671       29.155    ns/op
o.s.MyBenchmark.test10k      avgt        20     1911.152       13.217    ns/op
o.s.MyBenchmark.test1k       avgt        20     1857.205        3.086    ns/op
o.s.MyBenchmark.test200k     avgt        20     1905.360       18.102    ns/op
o.s.MyBenchmark.test25k      avgt        20     1832.663      102.562    ns/op
o.s.MyBenchmark.test50k      avgt        20     1907.488       18.043    ns/op

Y aquí está el código fuente del banco de pruebas basado en el JMH mencionado:

@State(Scope.Benchmark)
public class MyBenchmark {

    private List<byte[]> input1k, input10k, input25k, input50k, input100k, input200k;

    @Setup
    public void setUp() {
        input1k = createByteArray(1_000);
        input10k = createByteArray(10_000);
        input25k = createByteArray(25_000);
        input50k = createByteArray(50_000);
        input100k = createByteArray(100_000);
        input200k = createByteArray(200_000);
    }

    private static List<byte[]> createByteArray(int length) {
        Random random = new Random();
        List<byte[]> resultList = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            byte[] byteArray = new byte[4096];
            byteArray[random.nextInt(4096)] = 1;
            resultList.add(byteArray);
        }
        return resultList;
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(1_000)
    public boolean test1k() {
        return runBenchmark(input1k, this::byteArrayCheck);
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(10_000)
    public boolean test10k() {
        return runBenchmark(input10k, this::byteArrayCheck);
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(25_000)
    public boolean test25k() {
        return runBenchmark(input25k, this::byteArrayCheck);
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(50_000)
    public boolean test50k() {
        return runBenchmark(input50k, this::byteArrayCheck);
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(100_000)
    public boolean test100k() {
        return runBenchmark(input100k, this::byteArrayCheck);
    }

    @GenerateMicroBenchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @OperationsPerInvocation(200_000)
    public boolean test200k() {
        return runBenchmark(input200k, this::byteArrayCheck);
    }

    private static boolean runBenchmark(List<byte[]> arrays, Predicate<byte[]> method) {
        boolean someUnrelatedResult = false;
        for (byte[] array : arrays) {
            someUnrelatedResult |= method.test(array);
        }
        return someUnrelatedResult;
    }

    private boolean byteArrayCheck(final byte[] array) {
        long sum = 0L;
        for (byte b : array) {
            sum += b;
        }
        return (sum == 0);
    }

    public static void main(String[] args) throws RunnerException {
        new Runner(new OptionsBuilder()
                .include(".*" + MyBenchmark.class.getSimpleName() + ".*")
                .forks(1)
                .build()).run();
    }
}

Answer 4

Para 1000 iteraciones, solo está midiendo la sobrecarga de la llamada de método, el tiempo de medición, etc., que supera el tiempo para realizar el trabajo real. Más de 50,000 iteraciones, su procesador se queda sin caché L1 y se ralentiza. Dependiendo del tamaño de la memoria caché de su procesador, es probable que tenga otra ralentización en unos pocos millones de iteraciones cuando los datos ya no entren en la memoria caché L2.

Su procesador tiene una memoria caché de 8 MB, por lo que con esa cantidad de iteraciones debería obtener la próxima ralentización. Puede cambiar la prueba agregando, digamos solo cada cuarto byte, y verá que su tiempo no mejora, porque no son las operaciones sino el ancho de banda de la memoria lo que cuesta el tiempo.

Answer 5

Un simple cambio en su método de referencia hace una gran diferencia:

private void benchmark(final List<byte[]> arrays, final Predicate<byte[]> method, final String name) {
    long start = System.nanoTime();
    arrays.forEach(a -> { if(method.test(a)) System.out.println(); });
    long end = System.nanoTime();
    double nanosecondsPerIteration = (end - start) * 1d / arrays.size();
    System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + "ns");
}

Aquí, el resultado se utiliza realmente desde el punto de vista de la JVM. Mientras obtenía aproximadamente los mismos valores para su código original en mi máquina, después del cambio obtuve:

Benchmark: byteArrayCheck / iterations: 300000 / time per iteration: 1447.9460033333332ns
Benchmark: byteArrayCheck / iterations: 1000 / time per iteration: 3801.986ns
Benchmark: byteArrayCheck / iterations: 10000 / time per iteration: 3319.9504ns
Benchmark: byteArrayCheck / iterations: 25000 / time per iteration: 1929.62352ns
Benchmark: byteArrayCheck / iterations: 50000 / time per iteration: 1943.07152ns
Benchmark: byteArrayCheck / iterations: 100000 / time per iteration: 1928.07745ns
Benchmark: byteArrayCheck / iterations: 200000 / time per iteration: 1915.344575ns
Benchmark: byteArrayCheck / iterations: 300000 / time per iteration: 1918.1994833333333ns
Benchmark: byteArrayCheck / iterations: 400000 / time per iteration: 1913.248085ns

(Salté los números más altos debido a la insuficiente memoria RAM)

Muestra que hay una sobrecarga fija que se vuelve insignificante con números más grandes, pero también que las fluctuaciones en el rango de 10 a 20 nanosegundos son irrelevantes.

Quiero enfatizar que esto todavía no es un punto de referencia confiable (si alguna vez puede haber uno). Pero es lo suficientemente bueno como para indicar que la respuesta de raphw tiene un punto válido.