Dos operaciones en un bucle frente a dos bucles realizando las mismas operaciones una por bucle

Question

Esta pregunta es idéntica a esta Two loop bodies or one (result identical) pero en mi caso, uso Java.

Tengo dos circuitos que se ejecutan mil millones de veces.

int a = 188, b = 144, aMax = 0, bMax = 0; 

for (int i = 0; i < 1000000000; i++) { 
    int t = a^i; 
    if (t > aMax) 
    aMax = t;  
} 

for (int i = 0; i < 1000000000; i++) { 
    int t = b^i; 
    if (t > bMax) 
    bMax = t;  
} 

El tiempo que lleva ejecutar estos dos bucles en mi máquina es de aproximadamente 4 segundos. Cuando fusiono estos dos bucles en un solo bucle y realizo todas las operaciones en ese solo bucle, se ejecuta en 2 segundos. Como puede ver, las operaciones triviales conforman el contenido del ciclo, lo que requiere un tiempo constante.

Mi pregunta es dónde obtengo esta mejora en el rendimiento?

Supongo que el único lugar posible donde el rendimiento se ve afectado en los dos bucles separados es que aumenta i y comprueba si i < 1000000000 2 mil millones frente a solo mil millones de veces si fusiono los bucles. ¿Está sucediendo algo más allí?

Gracias!

Answer 1

Si no lo hace ejecutar una fase de calentamiento, es posible que el primer bucle se optimice y se compile, pero no el segundo, mientras que cuando se combinan se compila todo el bucle combinado. Además, utilizando la opción server y su código, la mayoría se optimiza ya que no utiliza los resultados.

He realizado la prueba a continuación, poniendo cada bucle así como el bucle combinado en su propio método y caliento la JVM para asegurarme de que todo se compila.

resultados (opciones de JVM: -server -XX:+PrintCompilation):

• bucle 1 = 500 ms
• bucle 2 = 900 ms
• fusionadas loop = 1.300 ms

Así que el bucle resultante de la fusión es ligeramente más rápido, pero no tanto.

public static void main(String[] args) throws InterruptedException { 

    for (int i = 0; i < 3; i++) { 
     loop1(); 
     loop2(); 
     loopBoth(); 
    } 

    long start = System.nanoTime(); 

    loop1(); 

    long end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 

    start = System.nanoTime(); 
    loop2(); 
    end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 

    start = System.nanoTime(); 
    loopBoth(); 
    end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 
} 

public static void loop1() { 
    int a = 188, aMax = 0; 
    for (int i = 0; i < 1000000000; i++) { 
     int t = a^i; 
     if (t > aMax) { 
      aMax = t; 
     } 
    } 
    System.out.println(aMax); 
} 

public static void loop2() { 
    int b = 144, bMax = 0; 
    for (int i = 0; i < 1000000000; i++) { 
     int t = b^i; 
     if (t > bMax) { 
      bMax = t; 
     } 
    } 
    System.out.println(bMax); 
} 

public static void loopBoth() { 
    int a = 188, b = 144, aMax = 0, bMax = 0; 

    for (int i = 0; i < 1000000000; i++) { 
     int t = a^i; 
     if (t > aMax) { 
      aMax = t; 
     } 
     int u = b^i; 
     if (u > bMax) { 
      bMax = u; 
     } 
    } 
    System.out.println(aMax); 
    System.out.println(bMax); 
} 

Answer 2

Me parece que en el caso de un solo bucle de la no aplicación JIT puede hacer desenrollado bucle y como resultado, el rendimiento es ligeramente mejor

Answer 3

¿Utilizó -server? Si no, deberías - el cliente JIT no es tan predecible, ni tan bueno. Si realmente está interesado en saber qué está sucediendo exactamente, puede usar UnlockDiagnostic + LogCompilation para verificar qué optimizaciones se están aplicando en ambos casos (hasta el ensamblaje generado).

Además, desde el código que proporcionó no puedo ver si realiza el calentamiento, si ejecuta la prueba una o varias veces para la misma JVM, si lo hizo un par de ejecuciones (JVM diferentes). Ya sea que esté teniendo en cuenta lo mejor, el promedio o la mediana del tiempo, ¿arroja valores atípicos?

Aquí es un buen enlace sobre el tema de la escritura de Java micro-puntos de referencia: http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

Editar: Una más punta microbenchmarking, cuidado de la sustitución de la pila de folios: http://www.azulsystems.com/blog/cliff/2011-11-22-what-the-heck-is-osr-and-why-is-it-bad-or-good

Answer 4

En resumen, la CPU puede ejecutar las instrucciones en el bucle combinado en paralelo, doblando el rendimiento.

También es posible que el segundo bucle no se optimice de manera eficiente. Esto se debe a que el primer bucle activará la compilación del método completo y el segundo bucle se compilará sin ninguna métrica que pueda alterar el tiempo del segundo bucle. Colocaría cada ciclo en un método diferente para asegurarme de que este no sea el caso.

La CPU puede realizar una gran cantidad de operaciones independientes en paralelo (depth 10 on Pentium III and 20 in the Xeon). Una operación que intenta hacer en paralelo es una rama, utilizando la predicción de bifurcación, pero si no toma la misma bifurcación casi siempre.

sospecho con el lazo de desenrollar el bucle se parece más a continuación (posiblemente más desenrollado del bucle, en este caso)

for (int i = 0; i < 1000000000; i += 2) { 
    // this first block is run almost in parallel 
    int t1 = a^i; 
    int t2 = b^i; 
    int t3 = a^(i+1); 
    int t4 = b^(i+1); 
    // this block run in parallel 
    if (t1 > aMax) aMax = t1;  
    if (t2 > bMax) bMax = t2;  
    if (t3 > aMax) aMax = t3;  
    if (t4 > bMax) bMax = t4;  
}