Java para pregunta de desempeño bucle

Question

teniendo en cuenta este ejemplo:

public static void main(final String[] args) { 
    final List<String> myList = Arrays.asList("A", "B", "C", "D"); 
    final long start = System.currentTimeMillis(); 
    for (int i = 1000000; i > myList.size(); i--) { 
     System.out.println("Hello"); 
    } 
    final long stop = System.currentTimeMillis(); 
    System.out.println("Finish: " + (stop - start)); 
} 

vs

public static void main(final String[] args) { 
    final List<String> myList = Arrays.asList("A", "B", "C", "D"); 
    final long start = System.currentTimeMillis(); 
    final int size = myList.size(); 
    for (int i = 1000000; i > size; i--) { 
     System.out.println("Hello"); 
    } 
    final long stop = System.currentTimeMillis(); 
    System.out.println("Finish: " + (stop - start)); 
} 

Hará esto que cualquier diffrence? En mi máquina, el segundo parece funcionar más rápido, pero no sé si es realmente preciso. ¿El compilador optimiza este código? Podría pensar que lo haría si la condición de bucle es un objeto inmutable (por ejemplo, matriz de cadenas).

Answer 1

Si quiere probar algo como esto, realmente debe optimizar su microbenchmark para medir lo que le importa.

Primero, haga que el bucle sea barato pero imposible de omitir. Calcular una suma suele ser el truco.

En segundo lugar, compare los dos tiempos.

Aquí hay algo de código que hace las dos cosas:

import java.util.*; 

public class Test { 

public static long run1() { 
    final List<String> myList = Arrays.asList("A", "B", "C", "D"); 
    final long start = System.nanoTime(); 
    int sum = 0; 
    for (int i = 1000000000; i > myList.size(); i--) sum += i; 
    final long stop = System.nanoTime(); 
    System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum); 
    return stop-start; 
} 

public static long run2() { 
    final List<String> myList = Arrays.asList("A", "B", "C", "D"); 
    final long start = System.nanoTime(); 
    int sum = 0; 
    int limit = myList.size(); 
    for (int i = 1000000000; i > limit; i--) sum += i; 
    final long stop = System.nanoTime(); 
    System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum); 
    return stop-start; 
} 

public static void main(String[] args) { 
    for (int i=0 ; i<5 ; i++) { 
    long t1 = run1(); 
    long t2 = run2(); 
    System.out.println(" Speedup = " + (t1-t2)*1e-9 + " ns/op\n"); 
    } 
} 

} 

Y si lo ejecutamos, en mi sistema obtenemos:

Finish: 0.481741256 ns/op; sum = -243309322 
Finish: 0.40228402 ns/op; sum = -243309322 
    Speedup = 0.079457236 ns/op 

Finish: 0.450627151 ns/op; sum = -243309322 
Finish: 0.43534661700000005 ns/op; sum = -243309322 
    Speedup = 0.015280534 ns/op 

Finish: 0.47738474700000005 ns/op; sum = -243309322 
Finish: 0.403698331 ns/op; sum = -243309322 
    Speedup = 0.073686416 ns/op 

Finish: 0.47729349600000004 ns/op; sum = -243309322 
Finish: 0.405540508 ns/op; sum = -243309322 
    Speedup = 0.071752988 ns/op 

Finish: 0.478979617 ns/op; sum = -243309322 
Finish: 0.36067492700000003 ns/op; sum = -243309322 
    Speedup = 0.11830469 ns/op 

lo que significa que los gastos indirectos de la llamada al método es de aproximadamente 0,1 ns . Si su ciclo hace cosas que no toman más de 1-2 ns, entonces debería preocuparse por esto. De lo contrario, no.

Answer 2

En los casos de "optimización del compilador", lo mejor que puede hacer es para cada uno de los bucles-:

for(final String x : myList) { ... } 

que permite al compilador proporcionan la ejecución más rápida.

Editar:

La diferencia entre los ejemplos de código se encuentra en el segundo argumento del bucle para. En el primer ejemplo, la VM hará una llamada a un método (más cara) y, por lo tanto, será más lenta (solo significativa cuando haya muchas iteraciones). En su segundo ejemplo, la máquina virtual hará una pila emergente (menos costosa, y las variables locales están en la pila), y por lo tanto más rápido (solo significativo cuando hay muchas iteraciones: para una sola iteración, la primera es más rápida, en términos de uso de memoria).

También: "La optimización prematura es la raíz de todo mal". La ley infame de Donald Knuth.

Answer 3

La diferencia es un método llamado menos para cada iteración, por lo que la segunda versión debe ejecutarse un poco más rápido. Aunque si usa el compilador Just-In-Time, puede optimizar eso, entendiendo que no cambia durante el ciclo. La implementación estándar de Java presenta JIT, pero no todas las implementaciones Java lo hacen.

Answer 4

El segundo debe ser más rápido porque no es necesario llamar al .size() cada vez que se realiza el ciclo. Es mucho más rápido decir 1 + 2 = 3 una vez que decirlo muchas veces.

Answer 5

Personalmente, no creo que pueda sacar conclusiones significativas de un ejemplo artificial como este.

Pero si realmente quieres saber, ¿por qué no utilizar javap para descompilar el código y ver qué hay diferente? ¿Por qué adivinar qué está haciendo el compilador cuando puede verlo usted mismo sin preguntar aquí?

código de bytes para el primer caso:

public class Stackoverflow extends java.lang.Object{ 
public Stackoverflow(); 
    Code: 
    0: aload_0 
    1: invokespecial #1; //Method java/lang/Object."<init>":()V 
    4: return 

public static void main(java.lang.String[]); 
    Code: 
    0: iconst_4 
    1: anewarray  #2; //class java/lang/String 
    4: dup 
    5: iconst_0 
    6: ldc  #3; //String A 
    8: aastore 
    9: dup 
    10: iconst_1 
    11: ldc  #4; //String B 
    13: aastore 
    14: dup 
    15: iconst_2 
    16: ldc  #5; //String C 
    18: aastore 
    19: dup 
    20: iconst_3 
    21: ldc  #6; //String D 
    23: aastore 
    24: invokestatic #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List 
    27: astore_1 
    28: invokestatic #8; //Method java/lang/System.currentTimeMillis:()J 
    31: lstore_2 
    32: ldc  #9; //int 1000000 
    34: istore 4 
    36: iload 4 
    38: aload_1 
    39: invokeinterface #10, 1; //InterfaceMethod java/util/List.size:()I 
    44: if_icmple  61 
    47: getstatic  #11; //Field java/lang/System.out:Ljava/io/PrintStream; 
    50: ldc  #12; //String Hello 
    52: invokevirtual #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 
    55: iinc 4, -1 
    58: goto 36 
    61: invokestatic #8; //Method java/lang/System.currentTimeMillis:()J 
    64: lstore 4 
    66: getstatic  #11; //Field java/lang/System.out:Ljava/io/PrintStream; 
    69: new  #14; //class java/lang/StringBuilder 
    72: dup 
    73: invokespecial #15; //Method java/lang/StringBuilder."<init>":()V 
    76: ldc  #16; //String Finish: 
    78: invokevirtual #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/la 
    81: lload 4 
    83: lload_2 
    84: lsub 
    85: invokevirtual #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder; 
    88: invokevirtual #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String; 
    91: invokevirtual #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 
    94: return 
} 

código de bytes para el segundo caso:

public class Stackoverflow extends java.lang.Object{ 
public Stackoverflow(); 
    Code: 
    0: aload_0 
    1: invokespecial #1; //Method java/lang/Object."<init>":()V 
    4: return 

public static void main(java.lang.String[]); 
    Code: 
    0: iconst_4 
    1: anewarray  #2; //class java/lang/String 
    4: dup 
    5: iconst_0 
    6: ldc  #3; //String A 
    8: aastore 
    9: dup 
    10: iconst_1 
    11: ldc  #4; //String B 
    13: aastore 
    14: dup 
    15: iconst_2 
    16: ldc  #5; //String C 
    18: aastore 
    19: dup 
    20: iconst_3 
    21: ldc  #6; //String D 
    23: aastore 
    24: invokestatic #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List; 
    27: astore_1 
    28: invokestatic #8; //Method java/lang/System.currentTimeMillis:()J 
    31: lstore_2 
    32: aload_1 
    33: invokeinterface #9, 1; //InterfaceMethod java/util/List.size:()I 
    38: istore 4 
    40: ldc  #10; //int 1000000 
    42: istore 5 
    44: iload 5 
    46: iload 4 
    48: if_icmple  65 
    51: getstatic  #11; //Field java/lang/System.out:Ljava/io/PrintStream; 
    54: ldc  #12; //String Hello 
    56: invokevirtual #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 
    59: iinc 5, -1 
    62: goto 44 
    65: invokestatic #8; //Method java/lang/System.currentTimeMillis:()J 
    68: lstore 5 
    70: getstatic  #11; //Field java/lang/System.out:Ljava/io/PrintStream; 
    73: new  #14; //class java/lang/StringBuilder 
    76: dup 
    77: invokespecial #15; //Method java/lang/StringBuilder."<init>":()V 
    80: ldc  #16; //String Finish: 
    82: invokevirtual #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder; 
    85: lload 5 
    87: lload_2 
    88: lsub 
    89: invokevirtual #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder; 
    92: invokevirtual #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String; 
    95: invokevirtual #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 
    98: return 
} 

hay diferencias, pero no estoy seguro de que puedo hacer una declaración definitiva sobre su efecto en el rendimiento.

Codificaría el segundo, porque significaría (a primera vista) un método de llamada en lugar de uno por iteración del ciclo. No sé si el compilador puede optimizarlo, pero estoy seguro de que puedo hacerlo con bastante facilidad. Entonces lo hago, independientemente de su efecto en el tiempo de pared.

Answer 6

Tenga en cuenta que el compilador javac no tiene nada que ver con la optimización. El compilador "importante" es el compilador JIT que vive dentro de la JVM.

En su ejemplo, en el caso más genérico, el myList.size() es un envío de método simple, que devuelve el contenido de un campo en la instancia List. Este es un trabajo insignificante en comparación con lo que está implicado por System.out.println("Hello") (al menos una llamada al sistema, por lo tanto cientos de ciclos de reloj, en comparación con no más de una docena para el envío método). Dudo mucho que su código pueda exhibir una diferencia significativa en la velocidad.

En un plano más general, el compilador JIT debe reconocer esta llamada a size() como una llamada a un caso conocido, de modo que pueda realizar el método de despacho con una llamada a una función directa (que es más rápido), o incluso inline la size() llamada de método, reduciendo la llamada a un acceso de campo de instancia simple.

Answer 7

No se puede optimizar, porque mylist.size() podría cambiar durante la ejecución del bucle. Incluso si es final, esto sólo significa que la referencia es final (lo que significa que no se puede reasignar miLista a algún otro objeto), pero los métodos de miLista, como remove() y añadir() están todavía disponibles. Final no hace que el objeto sea inmutable.

Answer 8

Como siempre con estas cosas, tendrá que ejecutarlas para ver cuál es más rápido dada la implementación que está utilizando. Sin embargo, el primero tiene el potencial de reducción del rendimiento de tener que llamar size() cada iteración, y una llamada a la función es más caro que simplemente comprobando la variable directamente. Sin embargo, es posible que dicha llamada de función podría ser optimizado de distancia en función de su código y lo que hace el compilador, por lo que tendría que realizar pruebas para ver.

Sin embargo, como señaló Pindatjuh, es mejor usar un bucle foreach cuando va a iterar sobre toda la colección de esa manera. Debería permitir al compilador optimizar las cosas mejor y es menos propenso a errores.

Answer 9

Tiene sentido que la segunda implementación sea más rápida, ya que almacena una única copia final local de la variable. El compilador tendría que darse cuenta de que el tamaño no puede cambiar dentro del ciclo para que el rendimiento sea más o menos equivalente.

Una pregunta es - qué este tipo de micro-optimización realmente importa? Si lo hace, vaya con lo que se ejecuta más rápido en sus pruebas y no confíe en una optimización del compilador.

Answer 10

compilador Java hubiera optimizado que es así, pero no lo hizo al ver la condición divertido. Si lo escribió así, no habría problema.

for (int i = myList.size(); i < 1000000; i--) { 
    System.out.println("Hello"); 
} 

Answer 11

Una vez trabajé en un proyecto en mi primera tarea fue la de localizar a algún código increíblemente lento (estaba en una marca nueva máquina 486 y tardó unos 20 minutos para ejecutar):

for(size_t i = 0; i < strlen(data); i++) 
{ 
    // do something with data[i] 
} 

la solución era (lo tiene a algo así como dos minutos o menos):

size_t length = strlen(data); 

for(int i = 0; i < length; i++) 
{ 
    // do something with data[i] 
} 

la cuestión es que los "datos" era más de 1 millón de caracteres, y strlen tiene que contar cada uno todo el tiempo.

En el caso de Java, el método "size()" probablemente devuelve una variable y, como tal, la VM lo alineará. En una máquina virtual como la de Android, probablemente no. Entonces la respuesta es "depende".

Mi preferencia personal es nunca llamar a un método más de una vez si se supone que debe devolver el mismo resultado cada vez.De esta forma, si el método implica un cálculo, se realiza solo una vez y luego nunca es un problema.

Answer 12

Con el último ejemplo, no necesitará resolver el tamaño actual de la matriz, por lo que será un poco más rápido que el primer ejemplo.

Solo recuerda que esto solo es útil si no cambias el número de valores en tu matriz.

En Android se recomienda utilizar el ejemplo más reciente en el ejemplo, Designing for Performance. http://developer.android.com/guide/practices/design/performance.html#foreach

Answer 13

Casi con seguridad lo que está viendo aquí es una diferencia en HotSpot en línea. Con un bucle más simple, es más probable que se alinee y, por lo tanto, elimine toda la basura redundante. Podría hacer lo mismo en línea, pero hágalo más temprano o con menos esfuerzo. En general, con microbenchmarks de Java debe ejecutar el código varias veces, a partir del cual puede calcular tiempos de inicio, tiempos promedio y desviaciones.