Ciekawa wydajność Java Loop Performance

Question

Mam duży problem podczas oceniania mojego kodu Java. Aby uprościć problem, napisałem poniższy kod, który wywołuje to samo dziwne zachowanie. Ważna jest metoda run() i podana podwójna wartość rate. Dla mojego testu wykonawczego (w metodzie głównej) ustawiłem stawkę na 0,5 jeden raz i 1,0 na drugi czas. Przy wartości 1.0 instrukcja if będzie wykonywana w każdej iteracji pętli, a przy wartości 0,5 instrukcja if będzie wykonywana o połowę mniej. Z tego powodu spodziewałem się dłuższego czasu pracy w pierwszym przypadku, ale jest odwrotnie. Czy ktoś może mi wyjaśnić to zjawisko?

Wynik główny:

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. 

Kodeks

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

Oddział misprediction zabija wydajność w pierwszym przypadku. Chociaż drugi przypadek wykonuje pewną pracę, jest nieco prosty, więc procesor może z łatwością przewidzieć następny krok. Więcej informacji można znaleźć w tej wersji: Wikipedia page.

Spróbuj przetestować za pomocą 0.7. Jeśli mam rację, wydajność będzie wynosić od 0,5 do 1,0.

Answer 2

Bardzo podobne do Why is processing a sorted array faster than an unsorted array? I są te same powody za kulisami.

Answer 3

Aby potwierdzić, że widzisz skutki nieprawidłowego oddziału, as indicated in my comment, przeprowadziłem kilka testów. Tabela pokazuje stawkę (dane wejściowe do metody uruchamiania), liczbę wykonanych if i czas uruchomienia.

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 

Im bliżej jesteś 0,5, tym więcej błędnych przewidywań rozgałęzień (mniej więcej po jednym każdym przebiegu). Im bardziej zbliżasz się do 0 lub 1, tym dokładniejsze prognozy rozgałęzień otrzymujesz (brak błędów, gdy kurs wynosi 0 lub 1).

A ponieważ obraz jest wart tysiąca słów: