usar - obtener valor maximo java

Java Math.min/max performance

Question

EDIT: maaartinus dio la respuesta que estaba buscando y los datos de tmyklebu sobre el problema ayudaron mucho, ¡así que gracias a ambos! :)

He leído un poco acerca de cómo HotSpot tiene algunos "intrínsecos" que se inyectan en el código, especialmente para las librerías de matemáticas estándar de Java ( desde aquí )

Así que decidí probarlo, para ver cuánta diferencia podría hacer HotSpot en comparación con hacer la comparación directamente (especialmente desde que escuché que min / max se puede compilar en asm sin sucursales).

    public static final int max ( final int a, final int b )
{
    if ( a > b )
    {
        return a;
    }

    return b;
}

Esa es mi implementación. De otra pregunta SO que he leído que el uso del operador ternario usa un registro adicional, no he encontrado diferencias significativas entre hacer un bloque if y usar un operador ternario (es decir, return (a> b)? A: b).

Asignando una matriz int de 8Mb (es decir, 2 millones de valores), y aleatoriamente, hago la siguiente prueba:

try ( final Benchmark bench = new Benchmark( "millis to max" ) )
    {
        int max = Integer.MIN_VALUE;

        for ( int i = 0; i < array.length; ++i )
        {
            max = OpsMath.max( max, array[i] );
            // max = Math.max( max, array[i] );
        }
    }

Estoy usando un objeto Benchmark en un bloque try-with-resources. Cuando termina, llama a close () en el objeto e imprime el tiempo que tardó en completarse el bloque. Las pruebas se realizan por separado comentando dentro / fuera de las llamadas máximas en el código anterior.

''max'' se agrega a una lista fuera del bloque de referencia y se imprime más tarde, para evitar que la JVM optimice todo el bloque.

La matriz se aleatoriza cada vez que se ejecuta la prueba.

Ejecutando la prueba 6 veces, da estos resultados:

Matemáticas estándar de Java:

millis to max 9.242167 
millis to max 2.1566199999999998
millis to max 2.046396 
millis to max 2.048616  
millis to max 2.035761
millis to max 2.001044 

Así que bastante estable después de la primera ejecución, y ejecutar las pruebas nuevamente da resultados similares.

OpsMath:

millis to max 8.65418 
millis to max 1.161559  
millis to max 0.955851 
millis to max 0.946642 
millis to max 0.994543 
millis to max 0.9469069999999999 

Una vez más, resultados muy estables después de la primera ejecución.

La pregunta es: ¿por qué? Esa es una gran diferencia allí. Y no tengo idea de por qué. Incluso si implemento mi método max () exactamente como Math.max () (es decir, return (a> = b)? A: b) ¡Todavía obtengo mejores resultados! No tiene sentido.

Especificaciones:

CPU: Intel i5 2500, 3,3GHz. Versión de Java: JDK 8 (lanzamiento público del 18 de marzo), x64. Debian Jessie (versión de prueba) x64.

Todavía tengo que intentar con JVM de 32 bits.

EDITAR: prueba autónoma a lo solicitado. Se agregó una línea para forzar a la JVM a precargar las clases de Matemáticas y OpsMath. Eso elimina el costo de 18ms de la primera iteración para la prueba OpsMath.

// Constant nano to millis.
final double TO_MILLIS = 1.0d / 1000000.0d;
// 8Mb alloc.
final int[] array = new int[(8*1024*1024)/4];
// Result and time array.
final ArrayList<Integer> results = new ArrayList<>();
final ArrayList<Double> times = new ArrayList<>();
// Number of tests.
final int itcount = 6;
// Call both Math and OpsMath method so JVM initializes the classes.
System.out.println("initialize classes " + 
OpsMath.max( Math.max( 20.0f, array.length ), array.length / 2.0f ));

final Random r = new Random();
for ( int it = 0; it < itcount; ++it )
{
    int max = Integer.MIN_VALUE;

    // Randomize the array.
    for ( int i = 0; i < array.length; ++i )
    {
        array[i] = r.nextInt();
    }

    final long start = System.nanoTime();
    for ( int i = 0; i < array.length; ++i )
    {
        max = Math.max( array[i], max );
            // OpsMath.max() method implemented as described.
        // max = OpsMath.max( array[i], max );
    }
    // Calc time.
    final double end = (System.nanoTime() - start);
    // Store results.
    times.add( Double.valueOf( end ) );
    results.add( Integer.valueOf(  max ) );
}
// Print everything.
for ( int i = 0; i < itcount; ++i )
{
    System.out.println( "IT" + i + " result: " + results.get( i ) );
    System.out.println( "IT" + i + " millis: " + times.get( i ) * TO_MILLIS );
}

Resultado de Java Math.max:

IT0 result: 2147477409
IT0 millis: 9.636998
IT1 result: 2147483098
IT1 millis: 1.901314
IT2 result: 2147482877
IT2 millis: 2.095551
IT3 result: 2147483286
IT3 millis: 1.9232859999999998
IT4 result: 2147482828
IT4 millis: 1.9455179999999999
IT5 result: 2147482475
IT5 millis: 1.882047

Resultado OpsMath.max:

IT0 result: 2147482689
IT0 millis: 9.003616
IT1 result: 2147483480
IT1 millis: 0.882421
IT2 result: 2147483186
IT2 millis: 1.079143
IT3 result: 2147478560
IT3 millis: 0.8861169999999999
IT4 result: 2147477851
IT4 millis: 0.916383
IT5 result: 2147481983
IT5 millis: 0.873984

Siguen los mismos resultados generales. He intentado aleatorizar la matriz solo una vez, y repetir las pruebas sobre la misma matriz, obtengo resultados más rápidos en general, pero la misma diferencia 2x entre Java Math.max y OpsMath.max.

Answer 1

Cuando ejecuto su código (adecuadamente modificado) utilizando Math.max en una JVM antigua (1.6.0_27), el bucle activo se parece a esto:

0x00007f4b65425c50: mov    %r11d,%edi         ;*getstatic array
                                              ; - foo146::bench@81 (line 40)
0x00007f4b65425c53: mov    0x10(%rax,%rdx,4),%r8d
0x00007f4b65425c58: mov    0x14(%rax,%rdx,4),%r10d
0x00007f4b65425c5d: mov    0x18(%rax,%rdx,4),%ecx
0x00007f4b65425c61: mov    0x2c(%rax,%rdx,4),%r11d
0x00007f4b65425c66: mov    0x28(%rax,%rdx,4),%r9d
0x00007f4b65425c6b: mov    0x24(%rax,%rdx,4),%ebx
0x00007f4b65425c6f: rex mov    0x20(%rax,%rdx,4),%esi
0x00007f4b65425c74: mov    0x1c(%rax,%rdx,4),%r14d  ;*iaload
                                              ; - foo146::bench@86 (line 40)
0x00007f4b65425c79: cmp    %edi,%r8d
0x00007f4b65425c7c: cmovl  %edi,%r8d
0x00007f4b65425c80: cmp    %r8d,%r10d
0x00007f4b65425c83: cmovl  %r8d,%r10d
0x00007f4b65425c87: cmp    %r10d,%ecx
0x00007f4b65425c8a: cmovl  %r10d,%ecx
0x00007f4b65425c8e: cmp    %ecx,%r14d
0x00007f4b65425c91: cmovl  %ecx,%r14d
0x00007f4b65425c95: cmp    %r14d,%esi
0x00007f4b65425c98: cmovl  %r14d,%esi
0x00007f4b65425c9c: cmp    %esi,%ebx
0x00007f4b65425c9e: cmovl  %esi,%ebx
0x00007f4b65425ca1: cmp    %ebx,%r9d
0x00007f4b65425ca4: cmovl  %ebx,%r9d
0x00007f4b65425ca8: cmp    %r9d,%r11d
0x00007f4b65425cab: cmovl  %r9d,%r11d         ;*invokestatic max
                                              ; - foo146::bench@88 (line 40)
0x00007f4b65425caf: add    $0x8,%edx          ;*iinc
                                              ; - foo146::bench@92 (line 39)
0x00007f4b65425cb2: cmp    $0x1ffff9,%edx
0x00007f4b65425cb8: jl     0x00007f4b65425c50

Aparte del extraño prefijo REX (no estoy seguro de qué se trata), aquí tienes un bucle que se ha desenrollado 8 veces y que hace casi todo lo que esperas: cargas, comparaciones y movimientos condicionales. Curiosamente, si cambia el orden de los argumentos al max , aquí se muestra el otro tipo de cadena de 8 cmovl profundidad. Supongo que no se sabe cómo generar un árbol de 3 cmovl de profundidad de cmovl u 8 cadenas de cmovl separadas para fusionar después de que se realiza el bucle.

Con el OpsMath.max explícito, se convierte en una serie de ramas condicionales e incondicionales que se desenrollan 8 veces. No voy a publicar el bucle; no es lindo. Básicamente, cada mov/cmp/cmovl anterior se divide en una carga, una comparación y un salto condicional hacia donde suceden un mov y un jmp . Curiosamente, si cambia el orden de los argumentos al max , aquí se cmovle cadena de 8 cmovle profundidad en cmovle lugar. EDITAR : Como @maaartinus señala, dichas ratas son en realidad más rápidas en algunas máquinas porque el predictor de ramificaciones hace su magia en ellas y son ramificaciones bien predichas.

No dudaría en sacar conclusiones de este punto de referencia. Usted tiene problemas de construcción de referencia; Tienes que ejecutarlo muchas más veces que tú y debes factorizar tu código de manera diferente si deseas cronometrar el código más rápido de Hotspot. Más allá del código del envoltorio, no está midiendo qué tan rápido es su max , o qué tan bien entiende Hotspot lo que está tratando de hacer, o cualquier otra cosa de valor aquí. Ambas implementaciones de max resultarán en un código que es completamente demasiado rápido para que cualquier tipo de medición directa sea significativa dentro del contexto de un programa más grande.

Answer 2

Es difícil decir por qué Math.max es más lento que un Ops.max , pero es fácil decir por qué este punto de referencia favorece en gran medida la bifurcación a movimientos condicionales: en la n -ésima iteración, la probabilidad de

Math.max( array[i], max );

no ser igual a max es la probabilidad de que la array[n-1] sea ​​más grande que todos los elementos anteriores. Obviamente, esta probabilidad se vuelve más y más baja con el crecimiento n y dado

final int[] array = new int[(8*1024*1024)/4];

Es bastante despreciable la mayor parte del tiempo. La instrucción de movimiento condicional es insensible a la probabilidad de bifurcación, siempre lleva la misma cantidad de tiempo para ejecutarse. La instrucción de movimiento condicional es más rápida que la predicción de rama si la rama es muy difícil de predecir. Por otro lado, la predicción de rama es más rápida si la rama se puede predecir bien con alta probabilidad. Actualmente, no estoy seguro de la velocidad del movimiento condicional en comparación con el mejor y el peor caso de ramificación. ¹

En su caso, casi todas las primeras ramas son bastante predecibles. Desde aproximadamente n == 10 adelante, no tiene sentido usar movimientos condicionales, ya que se garantiza que la bifurcación se predice correctamente y puede ejecutarse en paralelo con otras instrucciones (supongo que necesita exactamente un ciclo por iteración).

Esto parece ocurrir para los algoritmos que calculan el mínimo / máximo o que realizan una clasificación ineficiente (una buena capacidad de predicción de ramificación significa una baja entropía por paso).

¹ Tanto el movimiento condicional como la rama predicha toman un ciclo. El problema con el primero es que necesita sus dos operandos y esto requiere instrucciones adicionales. Al final, la ruta crítica puede alargarse y / o las ALU saturarse mientras la unidad de bifurcación está inactiva. A menudo, pero no siempre, las ramas se pueden predecir bien en aplicaciones prácticas; Es por eso que la predicción de rama se inventó en primer lugar.

En cuanto a los detalles sangrientos de cronometrar el movimiento condicional frente a la predicción de rama, el mejor y el peor de los casos, consulte la discusión a continuación en los comentarios. Mi propio punto de referencia muestra que el movimiento condicional es significativamente más rápido que la predicción de rama cuando la predicción de rama encuentra su peor caso, pero no puedo ignorar los resultados contradictorios . Necesitamos una explicación de qué es exactamente lo que hace la diferencia. Algunos más puntos de referencia y / o análisis podrían ayudar.

Answer 3

Utilizando JDK 8:

java version "1.8.0"
Java(TM) SE Runtime Environment (build 1.8.0-b132)
Java HotSpot(TM) 64-Bit Server VM (build 25.0-b70, mixed mode)

En Ubuntu 13.10

Corrí lo siguiente:

import java.util.Random;
import java.util.function.BiFunction;

public class MaxPerformance {
  private final BiFunction<Integer, Integer, Integer> max;
  private final int[] array;

  public MaxPerformance(BiFunction<Integer, Integer, Integer> max, int[] array) {
    this.max = max;
    this.array = array;
  }

  public double time() {
    long start = System.nanoTime();

    int m = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; ++i) m = max.apply(m, array[i]);

    m = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; ++i) m = max.apply(array[i], m);

    // total time over number of calls to max
    return ((double) (System.nanoTime() - start)) / (double) array.length / 2.0;
  }

  public double averageTime(int repeats) {
    double cumulativeTime = 0;
    for (int i = 0; i < repeats; i++)
      cumulativeTime += time();
    return (double) cumulativeTime / (double) repeats;
  }

  public static void main(String[] args) {
    int size = 1000000;
    Random random = new Random(123123123L);
    int[] array = new int[size];
    for (int i = 0; i < size; i++) array[i] = random.nextInt();

    double tMath = new MaxPerformance(Math::max, array).averageTime(100);
    double tAlt1 = new MaxPerformance(MaxPerformance::max1, array).averageTime(100);
    double tAlt2 = new MaxPerformance(MaxPerformance::max2, array).averageTime(100);

    System.out.println("Java Math: " + tMath);
    System.out.println("Alt 1:     " + tAlt1);
    System.out.println("Alt 2:     " + tAlt2);
  }

  public static int max1(final int a, final int b) {
    if (a >= b) return a;
    return b;
  }

  public static int max2(final int a, final int b) {
    return (a >= b) ? a : b; // same as JDK implementation
  }
}

Y obtuve los siguientes resultados (promedio de nanosegundos tomados para cada llamada al máximo):

Java Math: 15.443555810000003
Alt 1:     14.968298919999997
Alt 2:     16.442204045

Entonces, a largo plazo, parece que la segunda implementación es la más rápida, aunque por un margen relativamente pequeño.

Para tener una prueba un poco más científica, tiene sentido calcular el máximo de pares de elementos donde cada llamada es independiente de la anterior. Esto se puede hacer utilizando dos matrices aleatorias en lugar de una como en este punto de referencia:

import java.util.Random;
import java.util.function.BiFunction;
public class MaxPerformance2 {
  private final BiFunction<Integer, Integer, Integer> max;
  private final int[] array1, array2;

  public MaxPerformance2(BiFunction<Integer, Integer, Integer> max, int[] array1, int[] array2) {
    this.max = max;
    this.array1 = array1;
    this.array2 = array2;
    if (array1.length != array2.length) throw new IllegalArgumentException();
  }

  public double time() {
    long start = System.nanoTime();

    int m = Integer.MIN_VALUE;
    for (int i = 0; i < array1.length; ++i) m = max.apply(array1[i], array2[i]);
    m += m; // to avoid optimizations!

    return ((double) (System.nanoTime() - start)) / (double) array1.length;
  }

  public double averageTime(int repeats) {
    // warm up rounds:
    double tmp = 0;
    for (int i = 0; i < 10; i++) tmp += time();
    tmp *= 2.0;

    double cumulativeTime = 0;
    for (int i = 0; i < repeats; i++)
        cumulativeTime += time();
    return cumulativeTime / (double) repeats;
  }

  public static void main(String[] args) {
    int size = 1000000;
    Random random = new Random(123123123L);
    int[] array1 = new int[size];
    int[] array2 = new int[size];
    for (int i = 0; i < size; i++) {
        array1[i] = random.nextInt();
        array2[i] = random.nextInt();
    }

    double tMath = new MaxPerformance2(Math::max, array1, array2).averageTime(100);
    double tAlt1 = new MaxPerformance2(MaxPerformance2::max1, array1, array2).averageTime(100);
    double tAlt2 = new MaxPerformance2(MaxPerformance2::max2, array1, array2).averageTime(100);

    System.out.println("Java Math: " + tMath);
    System.out.println("Alt 1:     " + tAlt1);
    System.out.println("Alt 2:     " + tAlt2);
  }

  public static int max1(final int a, final int b) {
    if (a >= b) return a;
    return b;
  }

  public static int max2(final int a, final int b) {
    return (a >= b) ? a : b; // same as JDK implementation
  }
}

Lo que me dio:

Java Math: 15.346468170000005
Alt 1:     16.378737519999998
Alt 2:     20.506475350000006

La forma en que se configura su prueba hace una gran diferencia en los resultados. La versión JDK parece ser la más rápida en este escenario. Esta vez por un margen relativamente grande en comparación con el caso anterior.

Alguien mencionó Caliper. Bueno, si lees code.google.com/p/caliper/wiki/JavaMicrobenchmarks , una de las primeras cosas que dicen acerca de la micro-evaluación comparativa es no hacerlo: esto es porque es difícil obtener resultados precisos en general. Creo que este es un claro ejemplo de eso.