Warum ist 2 * (i * i) in Java schneller als 2 * i * i?

Wenn die Multiplikation 2 * (i * i) ist, kann die JVM die Multiplikation mit 2 aus der Schleife herausrechnen, was zu diesem äquivalenten, aber effizienteren Code führt:

int n = 0;
for (int i = 0; i < 1000000000; i++) {
    n += i * i;
}
n *= 2;

wenn die Multiplikation jedoch (2 * i) * i ist, optimiert die JVM sie nicht, da die Multiplikation mit einer Konstanten nicht mehr direkt vor der Addition erfolgt.

Hier sind einige Gründe, warum ich denke, dass dies der Fall ist:

• Das Hinzufügen einer if (n == 0) n = 1 -Anweisung am Anfang der Schleife führt dazu, dass beide Versionen gleich effizient sind, da das Ausklammern der Multiplikation nicht mehr garantiert, dass das Ergebnis dasselbe ist
• Die optimierte Version (durch Ausklammern der Multiplikation mit 2) ist genau so schnell wie die Version 2 * (i * i)

Hier ist der Testcode, mit dem ich diese Schlussfolgerungen gezogen habe:

public static void main(String[] args) {
    long fastVersion = 0;
    long slowVersion = 0;
    long optimizedVersion = 0;
    long modifiedFastVersion = 0;
    long modifiedSlowVersion = 0;

    for (int i = 0; i < 10; i++) {
        fastVersion += fastVersion();
        slowVersion += slowVersion();
        optimizedVersion += optimizedVersion();
        modifiedFastVersion += modifiedFastVersion();
        modifiedSlowVersion += modifiedSlowVersion();
    }

    System.out.println("Fast version: " + (double) fastVersion / 1000000000 + " s");
    System.out.println("Slow version: " + (double) slowVersion / 1000000000 + " s");
    System.out.println("Optimized version: " + (double) optimizedVersion / 1000000000 + " s");
    System.out.println("Modified fast version: " + (double) modifiedFastVersion / 1000000000 + " s");
    System.out.println("Modified slow version: " + (double) modifiedSlowVersion / 1000000000 + " s");
}

private static long fastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long slowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

private static long optimizedVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += i * i;
    }
    n *= 2;
    return System.nanoTime() - startTime;
}

private static long modifiedFastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long modifiedSlowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

Und hier sind die Ergebnisse:

Fast version: 5.7274411 s
Slow version: 7.6190804 s
Optimized version: 5.1348007 s
Modified fast version: 7.1492705 s
Modified slow version: 7.2952668 s

Byte-Codes: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Byte-Codes Viewer: https://github.com/Konloch/Bytecode-Viewer

Auf meinem JDK (Windows 10 64 Bit, 1.8.0_65-b17) kann ich reproduzieren und erklären:

public static void main(String[] args) {
    int repeat = 10;
    long A = 0;
    long B = 0;
    for (int i = 0; i < repeat; i++) {
        A += test();
        B += testB();
    }

    System.out.println(A / repeat + " ms");
    System.out.println(B / repeat + " ms");
}


private static long test() {
    int n = 0;
    for (int i = 0; i < 1000; i++) {
        n += multi(i);
    }
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000000; i++) {
        n += multi(i);
    }
    long ms = (System.currentTimeMillis() - startTime);
    System.out.println(ms + " ms A " + n);
    return ms;
}


private static long testB() {
    int n = 0;
    for (int i = 0; i < 1000; i++) {
        n += multiB(i);
    }
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000000; i++) {
        n += multiB(i);
    }
    long ms = (System.currentTimeMillis() - startTime);
    System.out.println(ms + " ms B " + n);
    return ms;
}

private static int multiB(int i) {
    return 2 * (i * i);
}

private static int multi(int i) {
    return 2 * i * i;
}

Ausgabe:

...
405 ms A 785527736
327 ms B 785527736
404 ms A 785527736
329 ms B 785527736
404 ms A 785527736
328 ms B 785527736
404 ms A 785527736
328 ms B 785527736
410 ms
333 ms

Warum also? Der Bytecode lautet wie folgt:

 private static multiB(int arg0) { // 2 * (i * i)
     <localVar:index=0, name=i , desc=I, sig=null, start=L1, end=L2>

     L1 {
         iconst_2
         iload0
         iload0
         imul
         imul
         ireturn
     }
     L2 {
     }
 }

 private static multi(int arg0) { // 2 * i * i
     <localVar:index=0, name=i , desc=I, sig=null, start=L1, end=L2>

     L1 {
         iconst_2
         iload0
         imul
         iload0
         imul
         ireturn
     }
     L2 {
     }
 }

Der Unterschied ist: Mit Klammern (2 * (i * i)):

• Drücken Sie den const-Stack
• Lokal auf Stapel schieben
• Lokal auf Stapel schieben
• multiplizieren Sie die Oberseite des Stapels
• multiplizieren Sie die Oberseite des Stapels

Ohne Klammern (2 * i * i):

• Drücken Sie den const-Stack
• Lokal auf Stapel schieben
• multiplizieren Sie die Oberseite des Stapels
• Lokal auf Stapel schieben
• multiplizieren Sie die Oberseite des Stapels

Das Laden aller Teile des Stapels und das anschließende Zurückarbeiten sind schneller als das Umschalten zwischen dem Aufsetzen des Stapels und dem Bedienen.

Kasperd fragte in einem Kommentar der akzeptierten Antwort:

In den Beispielen Java und C werden sehr unterschiedliche Registernamen verwendet. Verwenden beide Beispiele den AMD64 ISA?

xor edx, edx
xor eax, eax
.L2:
mov ecx, edx
imul ecx, edx
add edx, 1
lea eax, [rax+rcx*2]
cmp edx, 1000000000
jne .L2

Ich habe nicht genug Reputation, um dies in den Kommentaren zu beantworten, aber dies sind die gleichen ISA. Es sei darauf hingewiesen, dass die GCC-Version eine 32-Bit-Ganzzahllogik verwendet und die kompilierte JVM-Version intern eine 64-Bit-Ganzzahllogik verwendet.

R8 bis R15 sind nur neue X86_64 Register . EAX bis EDX sind die unteren Teile der Allzweckregister RAX bis RDX. Der wichtige Teil der Antwort ist, dass die GCC-Version nicht abgerollt ist. Es wird einfach eine Runde der Schleife pro tatsächlicher Maschinencodeschleife ausgeführt. Während die JVM-Version 16 Runden der Schleife in einer physischen Schleife enthält (basierend auf der Rustyx-Antwort, habe ich die Assembly nicht neu interpretiert). Dies ist einer der Gründe, warum mehr Register verwendet werden, da der Schleifenkörper tatsächlich 16-mal länger ist.

Obwohl dies nicht direkt mit der Umgebung der Frage zusammenhängt, habe ich aus Neugier den gleichen Test für .NET Core 2.1, x64, Release-Modus durchgeführt.

Hier ist das interessante Ergebnis, das bestätigt, dass ähnliche Phänomene (anders herum) auf der dunklen Seite der Streitmacht auftreten. Code:

static void Main(string[] args)
{
    Stopwatch watch = new Stopwatch();

    Console.WriteLine("2 * (i * i)");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * (i * i);
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds} ms");
    }

    Console.WriteLine();
    Console.WriteLine("2 * i * i");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * i * i;
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds}ms");
    }
}

Ergebnis:

2 * (i * i)

• ergebnis: 119860736, 438 ms
• ergebnis: 119860736, 433 ms
• ergebnis: 119860736, 437 ms
• ergebnis: 119860736, 435 ms
• ergebnis: 119860736, 436 ms
• ergebnis: 119860736, 435 ms
• ergebnis: 119860736, 435 ms
• ergebnis: 119860736, 439 ms
• ergebnis: 119860736, 436 ms
• ergebnis: 119860736, 437 ms

2 * i * i

• ergebnis: 119860736, 417 ms
• ergebnis: 119860736, 417 ms
• ergebnis: 119860736, 417 ms
• ergebnis: 119860736, 418 ms
• ergebnis: 119860736, 418 ms
• ergebnis: 119860736, 417 ms
• ergebnis: 119860736, 418 ms
• ergebnis: 119860736, 416 ms
• ergebnis: 119860736, 417 ms
• ergebnis: 119860736, 418 ms

Ich habe ähnliche Ergebnisse erhalten:

2 * (i * i): 0.458765943 s, n=119860736
2 * i * i: 0.580255126 s, n=119860736

Ich habe die SAME Ergebnisse erhalten, wenn sich beide Schleifen im selben Programm befanden oder sich in einer separaten .Java-Datei/.class befanden, die in einem separaten Lauf ausgeführt wurde.

Schließlich ist hier eine javap -c -v <.Java> Dekompilierung von jedem:

     3: ldc           #3                  // String 2 * (i * i):
     5: invokevirtual #4                  // Method Java/io/PrintStream.print:(Ljava/lang/String;)V
     8: invokestatic  #5                  // Method Java/lang/System.nanoTime:()J
     8: invokestatic  #5                  // Method Java/lang/System.nanoTime:()J
    11: lstore_1
    12: iconst_0
    13: istore_3
    14: iconst_0
    15: istore        4
    17: iload         4
    19: ldc           #6                  // int 1000000000
    21: if_icmpge     40
    24: iload_3
    25: iconst_2
    26: iload         4
    28: iload         4
    30: imul
    31: imul
    32: iadd
    33: istore_3
    34: iinc          4, 1
    37: goto          17

vs.

     3: ldc           #3                  // String 2 * i * i:
     5: invokevirtual #4                  // Method Java/io/PrintStream.print:(Ljava/lang/String;)V
     8: invokestatic  #5                  // Method Java/lang/System.nanoTime:()J
    11: lstore_1
    12: iconst_0
    13: istore_3
    14: iconst_0
    15: istore        4
    17: iload         4
    19: ldc           #6                  // int 1000000000
    21: if_icmpge     40
    24: iload_3
    25: iconst_2
    26: iload         4
    28: imul
    29: iload         4
    31: imul
    32: iadd
    33: istore_3
    34: iinc          4, 1
    37: goto          17

Zu Ihrer Information -

Java -version
Java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)

Ich habe versucht, eine JMH mit dem Standard-Archetyp zu erstellen: Ich habe auch eine optimierte Version hinzugefügt, die auf Runemoros Erklärung basiert.

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
//@BenchmarkMode({ Mode.All })
@BenchmarkMode(Mode.AverageTime)
public class MyBenchmark {
  @Param({ "100", "1000", "1000000000" })
  private int size;

  @Benchmark
  public int two_square_i() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += 2 * (i * i);
    }
    return n;
  }

  @Benchmark
  public int square_i_two() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += i * i;
    }
    return 2*n;
  }

  @Benchmark
  public int two_i_() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += 2 * i * i;
    }
    return n;
  }
}

Das Ergebnis sind hier:

Benchmark                           (size)  Mode  Samples          Score   Score error  Units
o.s.MyBenchmark.square_i_two           100  avgt       10         58,062         1,410  ns/op
o.s.MyBenchmark.square_i_two          1000  avgt       10        547,393        12,851  ns/op
o.s.MyBenchmark.square_i_two    1000000000  avgt       10  540343681,267  16795210,324  ns/op
o.s.MyBenchmark.two_i_                 100  avgt       10         87,491         2,004  ns/op
o.s.MyBenchmark.two_i_                1000  avgt       10       1015,388        30,313  ns/op
o.s.MyBenchmark.two_i_          1000000000  avgt       10  967100076,600  24929570,556  ns/op
o.s.MyBenchmark.two_square_i           100  avgt       10         70,715         2,107  ns/op
o.s.MyBenchmark.two_square_i          1000  avgt       10        686,977        24,613  ns/op
o.s.MyBenchmark.two_square_i    1000000000  avgt       10  652736811,450  27015580,488  ns/op

Auf meinem PC ( Core i7 860 - es macht nichts anderes als auf meinem Smartphone zu lesen):

• n += i*i dann n*2 ist zuerst
• 2 * (i * i) ist an zweiter Stelle.

Die JVM optimiert eindeutig nicht auf die gleiche Weise wie ein Mensch (basierend auf Runemoros Antwort).

Lesen Sie nun den Bytecode: javap -c -v ./target/classes/org/sample/MyBenchmark.class

• Unterschiede zwischen 2 * (i * i) (links) und 2 * i * i (rechts) hier: https://www.diffchecker.com/cvSFppWI
• Unterschiede zwischen 2 * (i * i) und der optimierten Version hier: https://www.diffchecker.com/I1XFu5dP

Ich bin kein Experte für Bytecode, aber wir iload_2, bevor wir imul: Hier haben Sie wahrscheinlich den Unterschied: Ich kann davon ausgehen, dass die JVM das Lesen i zweimal optimiert (i ist bereits hier und muss nicht erneut geladen werden, während dies im 2*i*i nicht möglich ist.

Interessante Beobachtung mit Java 11 und Abschalten der Schleife mit der folgenden Option VM:

-XX:LoopUnrollLimit=0

Die Schleife mit dem Ausdruck 2 * (i * i) führt zu einem kompakteren systemeigenen Code¹:

L0001: add    eax,r11d
       inc    r8d
       mov    r11d,r8d
       imul   r11d,r8d
       shl    r11d,1h
       cmp    r8d,r10d
       jl     L0001

im Vergleich zur 2 * i * i Version:

L0001: add    eax,r11d
       mov    r11d,r8d
       shl    r11d,1h
       add    r11d,2h
       inc    r8d
       imul   r11d,r8d
       cmp    r8d,r10d
       jl     L0001

Java-Version:

Java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

Benchmark-Ergebnisse:

Benchmark          (size)  Mode  Cnt    Score     Error  Units
LoopTest.fast  1000000000  avgt    5  694,868 ±  36,470  ms/op
LoopTest.slow  1000000000  avgt    5  769,840 ± 135,006  ms/op

Benchmark-Quellcode:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class LoopTest {

    @Param("1000000000") private int size;

    public static void main(String[] args) throws RunnerException {
        Options opt =
            new OptionsBuilder().include(LoopTest.class.getSimpleName())
                                .jvmArgs("-XX:LoopUnrollLimit=0")
                                .build();
        new Runner(opt).run();
    }

    @Benchmark
    public int slow() {
        int n = 0;
        for (int i = 0; i < size; i++) {
            n += 2 * i * i;
        }
        return n;
    }

    @Benchmark
    public int fast() {
        int n = 0;
        for (int i = 0; i < size; i++) {
            n += 2 * (i * i);
        }
        return n;
    }
}

^{1 - VM Verwendete Optionen: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0}

Eher ein Nachtrag. Ich habe das Experiment mit der neuesten Java 8 JVM von IBM wiederholt:

Java version "1.8.0_191"
Java(TM) 2 Runtime Environment, Standard Edition (IBM build 1.8.0_191-b12 26_Oct_2018_18_45 Mac OS X x64(SR5 FP25))
Java HotSpot(TM) 64-Bit Server VM (build 25.191-b12, mixed mode)

Und das zeigt sehr ähnliche Ergebnisse:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(zweite Ergebnisse mit 2 * i * i).

Interessanterweise, wenn Sie auf demselben Computer ausgeführt werden, aber Oracle Java verwenden:

Java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)

ergebnisse sind im Durchschnitt etwas langsamer:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

Kurz gesagt: Auch die Nebenversionsnummer von HotSpot spielt hier eine Rolle, da geringfügige Unterschiede innerhalb der JIT-Implementierung erhebliche Auswirkungen haben können.

Die beiden Methoden zum Hinzufügen generieren geringfügig unterschiedlichen Bytecode:

  17: iconst_2
  18: iload         4
  20: iload         4
  22: imul
  23: imul
  24: iadd

Für 2 * (i * i) vs:

  17: iconst_2
  18: iload         4
  20: imul
  21: iload         4
  23: imul
  24: iadd

Für 2 * i * i.

Und wenn Sie einen JMH Benchmark wie diesen verwenden:

@Warmup(iterations = 5, batchSize = 1)
@Measurement(iterations = 5, batchSize = 1)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
public class MyBenchmark {

    @Benchmark
    public int noBrackets() {
        int n = 0;
        for (int i = 0; i < 1000000000; i++) {
            n += 2 * i * i;
        }
        return n;
    }

    @Benchmark
    public int brackets() {
        int n = 0;
        for (int i = 0; i < 1000000000; i++) {
            n += 2 * (i * i);
        }
        return n;
    }

}

Der Unterschied ist klar:

# JMH version: 1.21
# VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28
# VM options: <none>

Benchmark                      (n)  Mode  Cnt    Score    Error  Units
MyBenchmark.brackets    1000000000  avgt    5  380.889 ± 58.011  ms/op
MyBenchmark.noBrackets  1000000000  avgt    5  512.464 ± 11.098  ms/op

Was Sie beobachten, ist korrekt und nicht nur eine Anomalie Ihres Benchmarking-Stils (d. H. Kein Aufwärmen, siehe Wie schreibe ich einen korrekten Micro-Benchmark in Java? )

Laufen wieder mit Graal:

# JMH version: 1.21
# VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28
# VM options: -XX:+UnlockExperimentalVMOptions -XX:+EnableJVMCI -XX:+UseJVMCICompiler

Benchmark                      (n)  Mode  Cnt    Score    Error  Units
MyBenchmark.brackets    1000000000  avgt    5  335.100 ± 23.085  ms/op
MyBenchmark.noBrackets  1000000000  avgt    5  331.163 ± 50.670  ms/op

Sie sehen, dass die Ergebnisse viel näher liegen, was Sinn macht, da Graal insgesamt ein leistungsfähigerer, modernerer Compiler ist.

Das hängt also davon ab, wie gut der JIT-Compiler in der Lage ist, einen bestimmten Code zu optimieren, und hat nicht unbedingt einen logischen Grund dafür.