Perché l'inversione del ciclo lo rende più lento?

Question

Ho il seguente codice che esegue uno spostamento circolare dei bit della matrice:

private static void method1(byte[] bytes) { 
    byte previousByte = bytes[0]; 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7)); 
    for (int i = 1; i < bytes.length; i++) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7)); 
     previousByte = tmp; 
    } 
} 

Poi ho pensato è più facile e più leggibile per andare all'indietro come questo:

private static void method2(byte[] bytes) { 
    byte lastByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7)); 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7)); 
} 

Ma notato che il secondo (metodo 2) è più lento del primo (metodo 1)! Ho notato la differenza perché sto chiamando il metodo migliaia di volte. Così ho fatto un test per assicurarsi ed ecco il risultato medio da 20 test di chiamare ogni metodo 3000 volte (e il numero di byte è di 1 milione):

method1 average : 4s 572ms 
method2 average : 5s 630ms 

Quindi la mia domanda è: perché è il primo uno più veloce del secondo?

Ecco il codice di prova per assicurarsi che non sto facendo qualcosa di sbagliato con il mio test:

import java.math.BigInteger; 

public class BitShiftTests { 

public static void main(String[] args) { 

    int numOfTests = 20; 
    int numberOfShifts = 3000; 
    byte[] numbers = new byte[1000000]; 
    for (int i = 0; i < numbers.length; i++) { 
     numbers[i] = (byte) (i % 255); 
    } 

    System.out.println("Testing method1..."); 
    BigInteger method1Sum = new BigInteger("00000000", 2); 
    for (int i = 1; i <= numOfTests; i++) { 
     long total = 0L; 
     for (int j = 0; j < numberOfShifts; j++) { 
      long startTime = System.nanoTime(); 
      method1(numbers); 
      long endTime = System.nanoTime(); 
      total = total + (endTime - startTime); 
     } 
     method1Sum = method1Sum.add(new BigInteger(Long.toString(total), 10)); 
     System.out.println(String.format("%-2d: %s", i, getTime(total))); 
    } 

    System.out.println("Testing method2..."); 
    BigInteger method2Sum = new BigInteger("00000000", 2); 
    for (int i = 1; i <= numOfTests; i++) { 
     long total = 0L; 
     for (int j = 0; j < numberOfShifts; j++) { 
      long startTime = System.nanoTime(); 
      method2(numbers); 
      long endTime = System.nanoTime(); 
      total = total + (endTime - startTime); 
     } 
     method2Sum = method2Sum.add(new BigInteger(Long.toString(total), 10)); 
     System.out.println(String.format("%-2d: %s", i, getTime(total))); 
    } 

    System.out.println("method1 average : " + getTime(method1Sum.longValue()/numOfTests)); 
    System.out.println("method2 average : " + getTime(method2Sum.longValue()/numOfTests)); 
} 

private static void method1(byte[] bytes) { 
    byte previousByte = bytes[0]; 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7)); 
    for (int i = 1; i < bytes.length; i++) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7)); 
     previousByte = tmp; 
    } 
} 

private static void method2(byte[] bytes) { 
    byte lastByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7)); 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7)); 
} 

private static String getTime(long nanoSecs) { 

    int minutes = (int) (nanoSecs/60000000000.0); 
    int seconds = (int) (nanoSecs/1000000000.0) - (minutes * 60); 
    int millisecs = (int) (((nanoSecs/1000000000.0) - (seconds + minutes * 60)) * 1000); 
    int nanosecs = (int) nanoSecs - (millisecs * 1000000000); 

    if (minutes == 0 && seconds == 0 && millisecs == 0) { 
    return nanosecs + "ns"; 
    } 

    if (minutes == 0 && seconds == 0) { 
    return millisecs + "ms"; 
    } 

    if (minutes == 0 && millisecs == 0) { 
    return seconds + "s"; 
    } 

    if (seconds == 0 && millisecs == 0) { 
    return minutes + "min"; 
    } 

    if (minutes == 0) { 
    return seconds + "s " + millisecs + "ms"; 
    } 

    if (seconds == 0) { 
    return minutes + "min " + millisecs + "ms"; 
    } 

    if (millisecs == 0) { 
    return minutes + "min " + seconds + "s"; 
    } 

    return minutes + "min " + seconds + "s " + millisecs + "ms"; 
} 
} 

Aggiornamento:

Sembra che il motivo è che sto accedendo a 2 indici differenti in ogni ciclo nel secondo metodo, mentre stavo accedendo solo a 1 indice nel primo metodo. Quindi non ha nulla a che fare con l'inversione del ciclo.

Grazie a @ rm5248 e @ Ben, sceglierei entrambe le risposte se potessi, ma ho scelto quello precedente.

Answer 1

Ho fatto un test rapido su questo, e sembra che il motivo per cui il secondo metodo sia più lento è perché l'algoritmo è cambiato un po '. Nel primo, mantieni un valore in una variabile locale, mentre non sei nel secondo. Per questo motivo, Java deve passare due volte alla matrice per ottenere la variabile. In teoria, questo non dovrebbe essere diverso, ma penso che abbia a che fare con il modo in cui gli array sono implementati in Java (ho il sospetto che se lo avessi provato in C i tempi sarebbero stati molto più vicini).

Per riferimento, ecco la mia applicazione (credo che fa la stessa cosa, ma non può):

private static void method2(byte[] bytes) { 
    byte prevByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((prevByte & 0xff) << 7)); 
     prevByte = tmp; 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length-1] & 0xff) << 7)); 
} 

Qui erano i tempi medi che ho ottenuto:

method1 average : 6s 555ms 
method2 average : 6s 726ms 

Answer 2

Potrebbe essere il comportamento della cache, ma la spiegazione più probabile è ciò che Peter ha detto nei suoi commenti: il JIT è meglio ottimizzato per il primo codice.

In particolare, è probabile che il JIT riconosca che il primo ciclo non indicherà mai oltre i limiti dell'array, evitando così il controllo associato. Il secondo ciclo è più complicato e probabilmente include controlli dei limiti su ogni accesso.

Oltre a ciò, il primo ciclo legge solo un valore dall'array e l'altro da una variabile locale temporanea che verrà registrata. La seconda versione legge due diversi elementi dall'array.

Per verificare con certezza, è necessario esaminare lo smontaggio del codice macchina prodotto dal JIT per entrambi i casi.