Quel idiome pour itérer un tableau est le plus efficace?

Question

Java 5 nous a donné les boucles for-each, qui devraient être utilisées là où c'est possible.

Mais quel est l'idiome le plus efficace si vous avez besoin d'utiliser l'index du tableau dans le bloc?

// Option (1) 
for (int i = array.length - 1; i >= 0; i--) { 
    // Code. 
} 

// Option (2) 
for (int i = 0; i < array.length; i++) { 
    // Code. 
} 

// Option (3) 
for (int i = 0, n = array.length; i < n; i++) { 
    // Code. 
} 

(De toute évidence, cela ne fera pas une grande différence de performance dans la plupart des programmes, mais l'humour moi.) :-)

1. boucles en arrière et est hideux. Peut-être même cache hostile? Ou le transformateur moderne peut-il détecter la marche arrière dans la mémoire?

2. est plus courte et je peux voir comment le compilateur JIT peut comprendre que array ne change jamais et donc length est constante, de sorte qu'il peut essentiellement le remplacer par (3). Mais fait-il cela? (Supposons que la machine virtuelle Java est Hotspot/Java Oracle 7.)

3. est suggérée par Joshua Bloch au point 45 Effective Java comme l'option la plus rapide si elle est une Collection.size() qui est la limite supérieure. Mais s'applique-t-il également aux tableaux? Du bytecode (voir ci-dessous) je peux voir celui-là enregistrer une instruction arraylength par cycle (pré-optimisé).

This question au sujet des boucles dans la machine virtuelle Dalvik, listes (1) - (3) le plus rapide au plus lent. Cependant, l'information date de 2008 et Dalvik est beaucoup plus mature aujourd'hui, donc je ne pense pas que ce soit toujours le cas.

En regardant le bytecode généré à partir des exemples ci-dessus, il existe des différences évidentes:

Compiled from "ForLoops.java" 
public class ForLoops extends java.lang.Object{ 
static int[] array; 

public ForLoops(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."<init>":()V 
    4: return 

public static void forLoop1(); 
    Code: 
    0: getstatic #17; //Field array:[I 
    3: arraylength 
    4: iconst_1 
    5: isub 
    6: istore_0 
    7: goto 13 
    10: iinc 0, -1 
    13: iload_0 
    14: ifge 10 
    17: return 

public static void forLoop2(); 
    Code: 
    0: iconst_0 
    1: istore_0 
    2: goto 8 
    5: iinc 0, 1 
    8: iload_0 
    9: getstatic #17; //Field array:[I 
    12: arraylength 
    13: if_icmplt 5 
    16: return 

public static void forLoop3(); 
    Code: 
    0: iconst_0 
    1: istore_0 
    2: getstatic #17; //Field array:[I 
    5: arraylength 
    6: istore_1 
    7: goto 13 
    10: iinc 0, 1 
    13: iload_0 
    14: iload_1 
    15: if_icmplt 10 
    18: return 

} 

Answer 1

Vous pouvez facilement tester par vous-même; Si vous le faites, vous devriez probablement jeter un oeil à these tips about performance testing des créateurs HotSpot eux-mêmes. This answer peut être utile aussi. Si vous décidez de tester ces implémentations, faites-nous savoir ce que vous trouvez!

Cependant, dans l'ensemble, vous ne devriez pas trop vous inquiéter de ces choses. Au lieu de cela, se concentrer sur l'écriture de code lisible et faire avancer les choses. La plupart du temps, vous constaterez que votre code s'exécute assez vite sans "trucs". Le matériel moderne est très rapide, et le JIT est plutôt bon.

Si vous constatez que votre code est trop lent, commencez par profile, puis optimisez. Tout le reste est prématuré. Et rappelez-vous, d'un homme qui est plus intelligent que nous tous:

« L'optimisation prématurée est la racine de tout le mal. » - Donald Knuth

EDIT: Puisque vous semblez curieux à ce sujet moins en termes de « comment devrais-je écrire mon code? » et plus en termes d'une expérience de pensée, je attendre toutes ces options pour fonctionner à des vitesses plus ou moins identiques.

Aucune de ces boucles n'est susceptible de modifier le prédicteur de branche (pour des ensembles de taille raisonnable, de toute façon). Je m'attendrais à ce que le JIT sous-jacent transforme toute référence de longueur de tableau récurrente de style (2) en style (3).Toutes choses étant égales par ailleurs, les performances du cache (1) ne sont pas plus mauvaises que celles de (2) ou (3) simplement parce qu'il fonctionne en arrière; pour un tableau donné, les mêmes lignes de cache seront chargées et frappées (ou pas) tout aussi souvent.

Bien sûr, mes attentes ne sont pas pertinentes. La seule façon de savoir est de tester! Lors des tests, cependant, rappelez-vous que writing good microbenchmarks is hard.