Java curioso Loop Performance

Question

Tengo un gran problema al evaluar mi código de Java. Para simplificar el problema, escribí el siguiente código que produce el mismo comportamiento curioso. Importante es el método run() y la tasa de valor doble dada. Para mi prueba de tiempo de ejecución (en el método principal) configuré la tasa a 0.5 una vez y 1.0 la otra vez. Con el valor 1.0, la sentencia if se ejecutará en cada iteración de ciclo y con el valor 0.5 la instrucción if se ejecutará la mitad. Por esta razón, esperaba un tiempo de ejecución más prolongado para el primer caso, pero lo contrario es cierto. ¿Alguien puede explicarme este fenómeno?

El resultado de principal:

Test mit rate = 0.5 
Length: 50000000, IF executions: 25000856 
Execution time was 4329 ms. 
Length: 50000000, IF executions: 24999141 
Execution time was 4307 ms. 
Length: 50000000, IF executions: 25001582 
Execution time was 4223 ms. 
Length: 50000000, IF executions: 25000694 
Execution time was 4328 ms. 
Length: 50000000, IF executions: 25004766 
Execution time was 4346 ms. 
================================= 
Test mit rate = 1.0 
Length: 50000000, IF executions: 50000000 
Execution time was 3482 ms. 
Length: 50000000, IF executions: 50000000 
Execution time was 3572 ms. 
Length: 50000000, IF executions: 50000000 
Execution time was 3529 ms. 
Length: 50000000, IF executions: 50000000 
Execution time was 3479 ms. 
Length: 50000000, IF executions: 50000000 
Execution time was 3473 ms. 

El Código

public ArrayList<Byte> list = new ArrayList<Byte>(); 
public final int LENGTH = 50000000; 

public PerformanceTest(){ 
    byte[]arr = new byte[LENGTH]; 
    Random random = new Random(); 
    random.nextBytes(arr); 
    for(byte b : arr) 
     list.add(b); 
} 

public void run(double rate){ 

    byte b = 0; 
    int count = 0; 

    for (int i = 0; i < LENGTH; i++) { 

     if(getRate(rate)){ 
      list.set(i, b); 
      count++; 
     } 
    } 
    System.out.println("Length: " + LENGTH + ", IF executions: " + count); 
} 

public boolean getRate(double rate){ 
    return Math.random() < rate; 
} 

public static void main(String[] args) throws InterruptedException { 
    PerformanceTest test = new PerformanceTest(); 

    long start, end; 
    System.out.println("Test mit rate = 0.5"); 
    for (int i = 0; i < 5; i++) { 
     start=System.currentTimeMillis(); 
     test.run(0.5); 
     end = System.currentTimeMillis(); 
     System.out.println("Execution time was "+(end-start)+" ms."); 

     Thread.sleep(500); 
    }  
    System.out.println("================================="); 
    System.out.println("Test mit rate = 1.0");  
    for (int i = 0; i < 5; i++) { 
     start=System.currentTimeMillis(); 
     test.run(1.0); 
     end = System.currentTimeMillis(); 
     System.out.println("Execution time was "+(end-start)+" ms."); 
     Thread.sleep(500); 
    } 
} 

Answer 1

Branch predicción errónea mata el rendimiento en el primer caso. Aunque el segundo caso hace algo de trabajo, es un poco directo, por lo que el procesador puede predecir fácilmente el siguiente paso. Consulte esto Wikipedia page para obtener más información.

Pruebe con 0.7. Si estoy en lo correcto, el rendimiento estará entre 0.5 y 1.0.

Answer 2

Muy similar a Why is processing a sorted array faster than an unsorted array? Y existen las mismas razones detrás de las escenas.

Answer 3

Para confirmar que está viendo los efectos de una omisión de bifurcación as indicated in my comment, he realizado algunas pruebas. La tabla muestra la tasa (entrada a su método de ejecución), el número de if ejecutado y el tiempo de ejecución.

0.0 0    1162 
0.1 5,000,892  1204.25 
0.2 10,002,410 1236.8 
0.3 14,998,226 1264 
0.4 19,996,983 1278 
0.5 24,998,455 1305.5 
0.6 29,998,879 1263.25 
0.7 34,999,821 1232.25 
0.8 39,999,414 1203.5 
0.9 44,998,674 1202 
1.0 50,000,000 1176.75 

Cuanto más se acerca a 0.5, más errores de ramificación se obtienen (aproximadamente uno por cada ejecución). Cuanto más cerca esté de 0 o 1, más precisas predicciones de bifurcación obtendrás (sin errores de predicción cuando la tasa sea 0 o 1).

Y como una imagen vale más que mil palabras: