Due operazioni in un ciclo contro due cicli che eseguono le stesse operazioni una per ciclo

Question

Questa domanda è identica a questa Two loop bodies or one (result identical) ma nel mio caso, io uso Java.

Ho due cicli che funzionano un miliardo di volte.

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;  
} 

Il tempo necessario per eseguire questi due cicli nella mia macchina è di circa 4 secondi. Quando unisco questi due loop in un unico loop e eseguo tutte le operazioni in quel loop singolo, viene eseguito in 2 secondi. Come puoi vedere operazioni banali compongono il contenuto del loop, richiedendo quindi un tempo costante.

La mia domanda è dove sto ottenendo questo miglioramento delle prestazioni?

sto indovinando che l'unico luogo possibile dove la prestazione viene colpito nei due cicli separati è che incrementa i e controlla se i < 1000000000 2 miliardi di volte contro solo 1 miliardo di volte se mi si fondono insieme i loop. C'è qualcos'altro che succede lì dentro?

Grazie!

Answer 1

Se non lo fai Esegui una fase di riscaldamento, è possibile che il primo ciclo venga ottimizzato e compilato ma non il secondo, mentre quando li unisci viene compilato l'intero ciclo unito. Inoltre, usando l'opzione server e il tuo codice, la maggior parte viene ottimizzata perché non usi i risultati.

Ho eseguito il test di seguito, inserendo ogni loop e il ciclo unito nel proprio metodo e aggiornando la JVM per assicurarsi che tutto venga compilato.

Risultati (opzioni JVM: -server -XX:+PrintCompilation):

• Loop 1 = 500 ms
• ciclo 2 = 900 ms
• fuse loop = 1.300 ms

Così il ciclo fusione è leggermente più veloce, ma non così 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

mi sembra che, nel caso di un unico anello JIT può scegliere di fare svolgimento del ciclo e di conseguenza le prestazioni sono leggermente migliori

Answer 3

Hai usato -server? Se no, dovresti: il JIT del cliente non è prevedibile, né buono. Se sei veramente interessato a cosa sta succedendo, puoi utilizzare UnlockDiagnostic + LogCompilation per verificare quali ottimizzazioni vengono applicate in entrambi i casi (fino all'assemblaggio generato).

Inoltre, dal codice fornito non riesco a vedere se si esegue il riscaldamento, sia che si esegua il test una o più volte per la stessa JVM, sia che sia stato eseguito un paio di esecuzioni (diverse JVM). Se stai prendendo in considerazione il migliore, il tempo medio o mediano, butti fuori valori anomali?

Ecco un buon collegamento sul tema della scrittura Java micro-benchmark: http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

Edit: Un altro microbenchmarking punta, guardatevi on-the-stack di sostituzione: http://www.azulsystems.com/blog/cliff/2011-11-22-what-the-heck-is-osr-and-why-is-it-bad-or-good

Answer 4

In breve, la CPU può eseguire le istruzioni nel ciclo unito in parallelo, raddoppiando le prestazioni.

È anche possibile che il secondo ciclo non sia ottimizzato in modo efficiente. Questo perché il primo ciclo attiverà l'intero metodo da compilare e il secondo ciclo verrà compilato senza alcuna metrica che possa sconvolgere i tempi del secondo ciclo. Metterei ciascun ciclo in un metodo separato per assicurarmi che non fosse così.

La CPU può eseguire un numero elevato di operazioni indipendenti in parallelo (depth 10 on Pentium III and 20 in the Xeon). Un'operazione che tenta di fare in parallelo è un ramo, usando la previsione del ramo, ma se non prende lo stesso ramo quasi ogni volta.

ho il sospetto con il ciclo srotolare il ciclo appare più come segue (forse più loop di srotolamento in questo 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;  
}