Pourquoi "while (i++ < n) {}" est-il nettement plus lent que "while (++i < n) {}" ?

Question

Apparemment, sur mon ordinateur portable Windows 8 avec HotSpot JDK 1.7.0_45 (avec toutes les options de compilateur/VM définies par défaut), la boucle ci-dessous

final int n = Integer.MAX_VALUE;
int i = 0;
while (++i < n) {
}

est au moins 2 ordres de grandeur plus rapide (~10 ms vs. ~5000 ms) que :

final int n = Integer.MAX_VALUE;
int i = 0;
while (i++ < n) {
}

J'ai remarqué ce problème en écrivant une boucle pour évaluer un autre problème de performance non pertinent. Et la différence entre ++i < n y i++ < n était suffisamment importante pour influencer le résultat de manière significative.

Si nous regardons le bytecode, le corps de la boucle de la version rapide est :

iinc
iload
ldc
if_icmplt

Et pour la version plus lente :

iload
iinc
ldc
if_icmplt

Donc pour ++i < n il incrémente d'abord la variable locale i par 1 et le pousse ensuite sur la pile d'opérandes pendant que i++ < n fait ces deux étapes dans l'ordre inverse. Mais cela ne semble pas expliquer pourquoi la première est beaucoup plus rapide. Y a-t-il une copie temporaire impliquée dans le dernier cas ? Ou est-ce quelque chose d'autre que le bytecode (implémentation de la VM, matériel, etc.) qui devrait être responsable de la différence de performance ?

J'ai lu d'autres discussions concernant ++i y i++ (de manière non exhaustive), mais je n'ai pas trouvé de réponse spécifique à Java et directement liée au cas dans lequel ++i o i++ est impliqué dans une comparaison de valeurs.

Answer 1

Comme d'autres l'ont souligné, le test est imparfait à bien des égards.

Vous ne nous avez pas dit exactement comment vous avez fait ce test. Cependant, j'ai essayé de mettre en œuvre un test "naïf" (sans vouloir vous offenser) comme celui-ci :

class PrePostIncrement
{
    public static void main(String args[])
    {
        for (int j=0; j<3; j++)
        {
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runPreIncrement();
                long after = System.nanoTime();
                System.out.println("pre  : "+(after-before)/1e6);
            }
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runPostIncrement();
                long after = System.nanoTime();
                System.out.println("post : "+(after-before)/1e6);
            }
        }
    }

    private static void runPreIncrement()
    {
        final int n = Integer.MAX_VALUE;
        int i = 0;
        while (++i < n) {}
    }

    private static void runPostIncrement()
    {
        final int n = Integer.MAX_VALUE;
        int i = 0;
        while (i++ < n) {}
    }
}

Lorsqu'on l'exécute avec les paramètres par défaut, il semble y avoir une petite différence. Mais le réel Le défaut du benchmark devient évident lorsque vous l'exécutez avec l'option -server drapeau. Dans mon cas, les résultats ressemblent alors à quelque chose comme

...
pre  : 6.96E-4
pre  : 6.96E-4
pre  : 0.001044
pre  : 3.48E-4
pre  : 3.48E-4
post : 1279.734543
post : 1295.989086
post : 1284.654267
post : 1282.349093
post : 1275.204583

Évidemment, la version pré-incrémentée a été complètement optimisé . La raison en est assez simple : Le résultat n'est pas utilisé. Le fait que la boucle soit exécutée ou non n'a aucune importance, aussi le JIT le supprime simplement.

Ceci est confirmé par un regard sur le désassemblage du hotspot : La version pré-incrémentée donne ce code :

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x0000000055060500} 'runPreIncrement' '()V' in 'PrePostIncrement'
  #           [sp+0x20]  (sp of caller)
  0x000000000286fd80: sub    $0x18,%rsp
  0x000000000286fd87: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - PrePostIncrement::runPreIncrement@-1 (line 28)

  0x000000000286fd8c: add    $0x10,%rsp
  0x000000000286fd90: pop    %rbp
  0x000000000286fd91: test   %eax,-0x243fd97(%rip)        # 0x0000000000430000
                                                ;   {poll_return}
  0x000000000286fd97: retq   
  0x000000000286fd98: hlt    
  0x000000000286fd99: hlt    
  0x000000000286fd9a: hlt    
  0x000000000286fd9b: hlt    
  0x000000000286fd9c: hlt    
  0x000000000286fd9d: hlt    
  0x000000000286fd9e: hlt    
  0x000000000286fd9f: hlt    

La version post-incrémentation donne ce code :

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000000550605b8} 'runPostIncrement' '()V' in 'PrePostIncrement'
  #           [sp+0x20]  (sp of caller)
  0x000000000286d0c0: sub    $0x18,%rsp
  0x000000000286d0c7: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - PrePostIncrement::runPostIncrement@-1 (line 35)

  0x000000000286d0cc: mov    $0x1,%r11d
  0x000000000286d0d2: jmp    0x000000000286d0e3
  0x000000000286d0d4: nopl   0x0(%rax,%rax,1)
  0x000000000286d0dc: data32 data32 xchg %ax,%ax
  0x000000000286d0e0: inc    %r11d              ; OopMap{off=35}
                                                ;*goto
                                                ; - PrePostIncrement::runPostIncrement@11 (line 36)

  0x000000000286d0e3: test   %eax,-0x243d0e9(%rip)        # 0x0000000000430000
                                                ;*goto
                                                ; - PrePostIncrement::runPostIncrement@11 (line 36)
                                                ;   {poll}
  0x000000000286d0e9: cmp    $0x7fffffff,%r11d
  0x000000000286d0f0: jl     0x000000000286d0e0  ;*if_icmpge
                                                ; - PrePostIncrement::runPostIncrement@8 (line 36)

  0x000000000286d0f2: add    $0x10,%rsp
  0x000000000286d0f6: pop    %rbp
  0x000000000286d0f7: test   %eax,-0x243d0fd(%rip)        # 0x0000000000430000
                                                ;   {poll_return}
  0x000000000286d0fd: retq   
  0x000000000286d0fe: hlt    
  0x000000000286d0ff: hlt    

Je ne comprends pas très bien pourquoi il semble que ce soit le cas. no supprimer la version post-incrément. (En fait, j'envisage de poser cette question séparément). Mais au moins, cela explique pourquoi vous pourriez voir des différences avec un "ordre de grandeur"...

---

EDIT : Il est intéressant de noter qu'en changeant la limite supérieure de la boucle de Integer.MAX_VALUE a Integer.MAX_VALUE-1 entonces les deux sont optimisées et ne nécessitent pas de temps. D'une manière ou d'une autre, cette limite (qui apparaît toujours comme 0x7fffffff dans l'assemblage) empêche l'optimisation. On peut supposer que cela a quelque chose à voir avec le fait que la comparaison est mise en correspondance avec un (singé !) cmp instruction, mais je ne peux pas donner une raison profonde au-delà de cela. Le JIT fonctionne de manière mystérieuse...

Answer 2

La différence entre ++i et i++ est que ++i incrémente effectivement la variable et 'renvoie' cette nouvelle valeur. i++ d'autre part crée effectivement une variable temporaire pour contenir la valeur actuelle de i, puis incrémente la variable en 'renvoyant' la valeur de la variable temporaire. C'est de là que vient la surcharge supplémentaire.

// i++ evaluates to something like this
// Imagine though that somehow i was passed by reference
int temp = i;
i = i + 1;
return temp;

// ++i evaluates to
i = i + 1;
return i;

Dans votre cas, il semble que l'incrément ne sera pas optimisé par la JVM car vous utilisez le résultat dans une expression. Par contre, la JVM peut optimiser une boucle comme celle-ci.

for( int i = 0; i < Integer.MAX_VALUE; i++ ) {}

C'est parce que le résultat de i++ n'est jamais utilisé. Dans une boucle comme celle-ci, vous devriez pouvoir utiliser à la fois ++i et i++ avec les mêmes performances que si vous utilisiez ++i.

Answer 3

EDIT 2

Vous devriez vraiment regarder ici :

http://hg.openjdk.java.net/code-tools/jmh/file/f90aef7f1d2c/jmh-samples/src/main/java/org/openjdk/jmh/samples/JMHSample_11_Loops.java

EDITAR Plus j'y pense, plus je me rends compte que ce test est en quelque sorte erroné, la boucle sera sérieusement optimisée par la JVM.

Je pense que vous devriez juste laisser tomber le @Param et laissez n=2 .

De cette façon, vous testerez les performances de l while lui-même. Les résultats que j'obtiens dans ce cas :

o.m.t.WhileTest.testFirst      avgt         5        0.787        0.086    ns/op
o.m.t.WhileTest.testSecond     avgt         5        0.782        0.087    ns/op

Il n'y a presque aucune différence

La toute première question que vous devez vous poser est la suivante comment vous testez et mesurez cela . C'est du micro-benchmarking et en Java c'est un art, et presque toujours un simple utilisateur (comme moi) se trompera dans les résultats. Vous devez vous fier à un test de référence et à un très bon outil pour cela. J'ai utilisé JMH pour tester ceci :

    @Measurement(iterations=5, time=1, timeUnit=TimeUnit.MILLISECONDS)
@Fork(1)
@Warmup(iterations=5, time=1, timeUnit=TimeUnit.SECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
public class WhileTest {
    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
            .include(".*" + WhileTest.class.getSimpleName() + ".*")
            .threads(1)
            .build();

        new Runner(opt).run();
    }

    @Param({"100", "10000", "100000", "1000000"})
    private int n;

    /*
    @State(Scope.Benchmark)
    public static class HOLDER_I {
        int x;
    }
    */

    @Benchmark
    public int testFirst(){
        int i = 0;
        while (++i < n) {
        }
        return i;
    }

    @Benchmark
    public int testSecond(){
        int i = 0;
        while (i++ < n) {
        }
        return i;
    }
}

Quelqu'un de beaucoup plus expérimenté dans le domaine de l'HJM pourrait corriger ces résultats (je l'espère vraiment, car je ne suis pas encore très polyvalent dans le domaine de l'HJM), mais les résultats montrent que la différence est très faible :

Benchmark                        (n)   Mode   Samples        Score  Score error    Units
o.m.t.WhileTest.testFirst        100   avgt         5        1.271        0.096    ns/op
o.m.t.WhileTest.testFirst      10000   avgt         5        1.319        0.125    ns/op
o.m.t.WhileTest.testFirst     100000   avgt         5        1.327        0.241    ns/op
o.m.t.WhileTest.testFirst    1000000   avgt         5        1.311        0.136    ns/op
o.m.t.WhileTest.testSecond       100   avgt         5        1.450        0.525    ns/op
o.m.t.WhileTest.testSecond     10000   avgt         5        1.563        0.479    ns/op
o.m.t.WhileTest.testSecond    100000   avgt         5        1.418        0.428    ns/op
o.m.t.WhileTest.testSecond   1000000   avgt         5        1.344        0.120    ns/op

Le champ Score est celui qui vous intéresse.

Answer 4

Ce test n'est probablement pas suffisant pour tirer des conclusions mais je dirais que si c'est le cas, la JVM peut optimiser cette expression en changeant i++ en ++i puisque la valeur stockée de i++ (pré-valeur) n'est jamais utilisée dans cette boucle.

Answer 5

Je suggère que vous devriez (dans la mesure du possible) toujours utiliser ++c plutôt que c++ comme le premier jamais sera plus lent puisque, conceptuellement, une copie profonde de c doit être prise dans ce dernier cas afin de retourner la valeur précédente.

En effet, de nombreux optimiseurs supprimeront une copie profonde inutile, mais ils ne peuvent pas facilement le faire si vous utilisez la valeur de l'expression. Et c'est exactement ce que vous faites dans votre cas.

Beaucoup de gens ne sont pas d'accord : ils considèrent qu'il s'agit d'une micro-optimisation.