Warum ist "while (i ++ <n) {}" deutlich langsamer als "while (++ i <n) {}"?

74

Anscheinend ist auf meinem Windows 8-Laptop mit HotSpot JDK 1.7.0_45 (wobei alle Compiler- / VM-Optionen auf Standard gesetzt sind) die folgende Schleife

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

ist mindestens 2 Größenordnungen schneller (~ 10 ms gegenüber ~ 5000 ms) als:

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

Ich habe dieses Problem beim Schreiben einer Schleife bemerkt, um ein anderes irrelevantes Leistungsproblem zu bewerten. Und der Unterschied zwischen ++i < nund i++ < nwar groß genug, um das Ergebnis signifikant zu beeinflussen.

Wenn wir uns den Bytecode ansehen, lautet der Schleifenkörper der schnelleren Version:

iinc
iload
ldc
if_icmplt

Und für die langsamere Version:

iload
iinc
ldc
if_icmplt

Daher ++i < nerhöht es zuerst die lokale Variable ium 1 und schiebt sie dann auf den Operandenstapel, während i++ < ndiese beiden Schritte in umgekehrter Reihenfolge ausgeführt werden. Das scheint aber nicht zu erklären, warum Ersteres viel schneller ist. Gibt es im letzteren Fall eine temporäre Kopie? Oder sollte etwas jenseits des Bytecodes (VM-Implementierung, Hardware usw.) für den Leistungsunterschied verantwortlich sein?

Ich habe eine andere Diskussion las über ++iund i++(nicht erschöpfend obwohl), aber fand keine Antwort , die Java-spezifisch ist und direkt auf den Fall bezogen , wo ++ioder i++in einem Wertvergleich beteiligt ist.

java performance compiler-optimization post-increment pre-increment Sikan
quelle
23
10 ms sind kaum lang genug für einen Benchmark - geschweige denn für einen Java-Benchmark, bei dem Sie JVM-Aufwärmeffekte haben. Können Sie Ihren genauen Testcode veröffentlichen? Versuchen Sie auch, die Reihenfolge der Benchmarks umzukehren.
Mysticial
3
Wie Mysticial sagte, braucht Java Aufwärmzeit. Dies ist für den Just In Time (JIT) -Compiler vorgesehen, um seine Arbeit zu erledigen. Wenn Sie Ihren Code in eine Funktion einfügen und ihn mehrmals aufrufen, bevor Sie Ihre Messungen durchführen, erhalten Sie möglicherweise unterschiedliche Ergebnisse.
Thirler
12
@CaptainCodeman in solch einer allgemeinen Form ist diese Aussage einfach Unsinn. Leistung bietet viel mehr als (fehlerhafte) Mikro-Benchmarks. Wir sind für ein ziemlich großes Projekt von C ++ auf Java umgestiegen und haben eine Größenordnung an Leistung gewonnen. Dies hängt von dem Problem ab, das Sie lösen möchten, von den Ressourcen, die Sie haben, und vielem mehr. Wählen Sie immer die Sprache, die am besten zu Ihrem Problem passt, und das Personal, das Ihnen zur Verfügung steht (unter anderem).
Axel
4
@Axel Ich bin gespannt, für welche Art von Anwendung hat der Wechsel von C ++ zu Java zu einer Leistungssteigerung um eine Größenordnung geführt?
CaptainCodeman
7
@Axel Keine kompilierte Programmiersprache ist eine Größenordnung schneller als eine andere. Das wahrscheinlichere Szenario ist also, dass Sie schreckliche C ++ - Programmierer hatten oder eine sehr langsame Bibliothek verwendeten.
CaptainCodeman

Antworten:

119

Wie andere betont haben, ist der Test in vielerlei Hinsicht fehlerhaft.

Sie haben uns nicht genau gesagt, wie Sie diesen Test durchgeführt haben. Ich habe jedoch versucht, einen "naiven" Test (keine Beleidigung) wie folgt durchzuführen:

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) {}
    }
}

Wenn Sie dies mit Standardeinstellungen ausführen, scheint es einen kleinen Unterschied zu geben. Der wahre Fehler des Benchmarks wird jedoch offensichtlich, wenn Sie dies mit der -serverFlagge ausführen . Die Ergebnisse in meinem Fall sind dann ungefähr so

...
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

Offensichtlich wurde die Pre-Inkrement-Version komplett weg optimiert . Der Grund ist ziemlich einfach: Das Ergebnis wird nicht verwendet. Es spielt überhaupt keine Rolle, ob die Schleife ausgeführt wird oder nicht, daher entfernt die JIT sie einfach.

Dies wird durch einen Blick auf die Hotspot-Demontage bestätigt: Die Pre-Inkrement-Version führt zu folgendem Code:

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x0000000055060500} &apos;runPreIncrement&apos; &apos;()V&apos; in &apos;PrePostIncrement&apos;
  #           [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

Die Post-Inkrement-Version führt zu folgendem Code:

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000000550605b8} &apos;runPostIncrement&apos; &apos;()V&apos; in &apos;PrePostIncrement&apos;
  #           [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

Mir ist nicht ganz klar, warum die Post-Inkrement-Version anscheinend nicht entfernt wird. (Tatsächlich betrachte ich dies als separate Frage). Aber zumindest erklärt dies, warum Sie möglicherweise Unterschiede mit einer "Größenordnung" sehen ...

EDIT: Interessant ist , wenn die obere Grenze der Schleife ändert , Integer.MAX_VALUEum Integer.MAX_VALUE-1dann beide sind Versionen wegoptimiert und erfordern „Null“ der Zeit. Irgendwie verhindert diese Grenze (die immer noch wie 0x7fffffffin der Baugruppe erscheint) die Optimierung. Vermutlich hat dies etwas damit zu tun, dass der Vergleich einer (versengten!) cmpAnweisung zugeordnet wird, aber darüber hinaus kann ich keinen tiefgreifenden Grund nennen. Die JIT arbeitet auf mysteriöse Weise ...

Marco13
quelle
2
Ich bin kein Java-Typ, aber ich interessiere mich vorübergehend für die Mechanik von Compilern. Wenn Sie (oder jemand anderes) Ihre Folgefrage in einem separaten Beitrag stellen, veröffentlichen Sie bitte einen Link. Vielen Dank!
RLH
26
Eigentlich war das das erste, was mir in den Sinn kam: Beim while (i++ < Integer.MAX_VALUE)Verlassen der Schleife ist bereits ein Überlauf passiert i. Der Nachweis der Richtigkeit einer Codetransformation ist viel schwieriger, wenn ein Überlauf auftreten kann, und schließlich sind Schleifen mit Überläufen nicht der übliche Fall. Warum sollte sich der Hotspot also die Mühe machen, sie zu optimieren
Holger,
5
@ RLH Ich schrieb eine Folgefrage auf stackoverflow.com/questions/25326377/…
Marco13
@Holger: Ja, das klingt nach einer Möglichkeit, Probleme mit den Optimierungen zu vermeiden, die gegen Sicherheitsbeschränkungen verstoßen. Es kommt nicht häufig vor, daher lohnt es sich nicht, nach allen möglichen Fehlern zu suchen (z. B. Pufferüberläufe).
Luaan
@Holger aber wie erklären Sie, dass, wenn das Limit von Integer.MAX_VALUE auf Integer.MAX_VALUE-1 reduziert wird, beide optimiert sind, so dass bei i ++ immer noch ein Fallüberlauf auftritt, aber gleichzeitig optimiert wird !!!
Sumit Kumar Saha
19

Der Unterschied zwischen ++ i und i ++ besteht darin, dass ++ i die Variable effektiv inkrementiert und diesen neuen Wert "zurückgibt". i ++ hingegen erstellt effektiv eine temporäre Variable, die den aktuellen Wert in i enthält, und erhöht dann die Variable, die den Wert der temporären Variablen zurückgibt. Hier kommt der zusätzliche Overhead her.

// 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;

In Ihrem Fall scheint das Inkrement von der JVM nicht optimiert zu werden, da Sie das Ergebnis in einem Ausdruck verwenden. Die JVM kann andererseits eine solche Schleife optimieren.

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

Dies liegt daran, dass das Ergebnis von i ++ niemals verwendet wird. In einer solchen Schleife sollten Sie in der Lage sein, sowohl ++ i als auch i ++ mit der gleichen Leistung zu verwenden, als ob Sie ++ i verwendet hätten.

Smith_61
quelle
Es könnte etwas klarer sein, wenn der Hotspot-Compiler explizit erwähnt wird.
Joop Eggen
10
Wie im OP erwähnt, führen beide Versionen zu der gleichen Anzahl von Bytecode-Anweisungen. Wo ist der Overhead, über den Sie dort sprechen? Und über welche JVM-Optimierungen, über die Sie sprechen, sind für die ++iVersion möglich, für die andere nicht?
Arne.b
Fragen Sie sich, wie iload funktioniert ... Kopiert es tatsächlich die Variable aus der lokalen Variablentabelle in den Operandenstapel? Wenn ja, wird i für i ++ zuerst in den Operandenstapel verschoben (kopiert) und iinc erhöht das ursprüngliche i in der lokalen Variablentabelle. ++ Ich mache genau das gleiche in umgekehrter Reihenfolge. In beiden Fällen gibt es keine zusätzliche temporäre Variable. Aber ich könnte völlig falsch liegen :)
Sikan
Wenn Sie sich Eugenes Antwort mit seinen hinzugefügten Benchmarks ansehen, sehen Sie, dass der Unterschied minimal ist, wenn überhaupt keiner. Die JVM kann meistens ein i ++ zu einem ++ i optimieren. Dadurch wird die temporäre Variable entfernt und nur ein Inkrement für die Variable ausgeführt. Ich vermute nur, dass die JVM bei Verwendung von i ++ im Vergleich beim Kompilieren des Bytecodes zu Maschinencode ein zusätzliches Register zur Verwendung mit der Schleife zuweist.
Smith_61
18

BEARBEITEN 2

Sie sollten hier wirklich schauen:

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

BEARBEITEN Je mehr ich darüber nachdenke, desto mehr wird mir klar, dass dieser Test irgendwie falsch ist. Die Schleife wird von der JVM ernsthaft optimiert.

Ich denke, dass Sie das einfach fallen @Paramlassen und lassen sollten n=2.

Auf diese Weise testen Sie die Leistung des whileselbst. Die Ergebnisse bekomme ich in diesem Fall:

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

Das ist fast kein Unterschied

Die allererste Frage, die Sie sich stellen sollten, ist, wie Sie dies testen und messen . Dies ist Mikro-Benchmarking und in Java ist dies eine Kunst, und fast immer wird ein einfacher Benutzer (wie ich) die Ergebnisse falsch verstehen. Sie sollten sich auf einen Benchmark-Test und ein sehr gutes Werkzeug verlassen. Ich habe JMH verwendet, um dies zu testen:

    @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;
    }
}

Jemand, der viel mehr Erfahrung mit JMH hat, könnte diese Ergebnisse korrigieren (ich hoffe es wirklich!, Da ich in JMH noch nicht so vielseitig bin), aber die Ergebnisse zeigen, dass der Unterschied verdammt gering ist:

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

Das Feld Score ist das Feld, an dem Sie interessiert sind.

Eugene
quelle
Nach allem, was ich sagen und korrigieren kann, wenn ich falsch liege, scheint die JVM das i ++ nicht in ++ i zu optimieren, wenn das Ergebnis verwendet wird. Oder liegt es nur daran, dass i ++ eine zusätzliche Zeit schleift?
Smith_61
0

Wahrscheinlich reicht dieser Test nicht aus, um Schlussfolgerungen zu ziehen, aber ich würde sagen, wenn dies der Fall ist, kann die JVM diesen Ausdruck optimieren, indem sie i ++ in ++ i ändert, da der gespeicherte Wert von i ++ (Vorwert) in dieser Schleife niemals verwendet wird.

danibuiza
quelle
-3

Ich schlage vor, Sie sollten (wann immer möglich) immer verwenden, ++canstatt, c++da erstere niemals langsamer werden, da cim letzteren Fall konzeptionell eine tiefe Kopie von erstellt werden muss, um den vorherigen Wert zurückzugeben.

In der Tat optimieren viele Optimierer eine unnötige tiefe Kopie, aber sie können dies nicht einfach tun, wenn Sie den Ausdruckswert verwenden. Und genau das tun Sie in Ihrem Fall.

Viele Leute sind sich jedoch nicht einig: Sie sehen darin eine Mikrooptimierung.

Bathseba
quelle
6
Dies mag in der Welt der nicht trivialen C ++ - Iteratoren zutreffen, aber nicht für primitive Typen ...
Mysticial
3
@Bathsheba Ich stimme zu, dass Sie Ihren Compiler verstehen sollten und welche Art von Optimierungen er für Sie tun wird. In begrenzten Fällen müssen Sie diese Art von Optimierungen selbst vornehmen. Wenn Sie einen Compiler verwenden, der dies nicht für Sie erledigt, wissen Sie es wahrscheinlich. Da die meisten dieser Compiler für eingebettete Systeme sind oder eine geringere Anzahl von Benutzern haben.
Smith_61
4
Ich bin auf der Seite von @Bathsheba. Ich weiß, dass es in 99% der Fälle (insbesondere in Java) keinen Unterschied macht, ++ i und i ++ zu schreiben. Ich würde es mir jedoch zur Gewohnheit machen, ++ i zu schreiben, da es nicht triviale Fälle gibt, in denen dies einen Unterschied macht (insbesondere in C ++ usw.). Angesichts der Tatsache, dass ++ i nicht schwerer zu lesen ist als i ++, warum nicht ein potenziell sichereres Formular schreiben? Genau wie wir Dinge schreiben wie if (CONSTANT == var)undif (CONSTANT.equals(var))
Adrian Shum
5
Downvote für Fehlinformationen. Es ist nicht möglich, irgendetwas "tief zu kopieren", auf das die "++" - Operatoren in Java angewendet werden können, und die Aussage, dass Optimierer den Vorgang nicht optimieren können, wenn er in einem Vergleich verwendet wird, ist ebenfalls eine Fehlinformation.
Score_Under
4
In der Situation, in der das Ergebnis eines inkrementierenden Operators verwendet wird, sollte der Operator verwendet werden, der besser zur Semantik seiner Tätigkeit passt , da Leistungsunterschiede durch Codeänderungen ausgeglichen werden können, die sich aus der Auswahl ergeben. Wenn das Ergebnis des Operators nicht verwendet wird, bevorzuge ich Postoperatoren, da es mit dem an anderer Stelle verwendeten Nomen-Verb-Muster konsistenter ist.
Supercat