Dlaczego 2 *(i * i) jest szybsze niż 2 * i * I w Javie?

(Uwaga redaktora: ta odpowiedź jest zaprzeczana przez dowody z patrzenia na asm, jak pokazuje inna odpowiedź. To było przypuszczenie poparte kilkoma eksperymentami, ale okazało się nie być poprawne.)

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

Ale gdy mnożenie jest (2 * i) * i, JVM nie optymalizuje go, ponieważ mnożenie przez stała nie jest już tuż przed dodaniem n +=.

Oto kilka powodów, dla których myślę, że tak jest:

• dodanie if (n == 0) n = 1 na początku pętli powoduje, że obie wersje są równie wydajne, ponieważ faktorowanie mnożenia nie gwarantuje już, że wynik będzie taki sam
• wersja zoptymalizowana (obliczając mnożenie przez 2) jest dokładnie tak szybka jak wersja 2 * (i * i)

Oto kod testowy, który użyłem do wyciągnij te wnioski:

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

A oto wyniki:

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

Kody bajtowe: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Przeglądarka kodów bajtowych: https://github.com/Konloch/bytecode-viewer

Na moim JDK (Windows 10 64 bit, 1.8.0_65-b17) mogę odtworzyć i wyjaśnić:

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

Wyjście:

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

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

Różnica jest: Ze wspornikami (2 * (i * i)):

• push const stack
• push local on stack
• push local on stack
• mnożenie wierzchołka stosu
• mnożenie wierzchołka stosu

Bez nawiasów (2 * i * i):

• push const stack
• push local on stack
• mnożenie wierzchołka stosu
• push local on stack
• mnożenie wierzchołka stosu

Ładowanie wszystkich na stosie, a następnie praca z powrotem w dół jest szybsza niż przełączanie między zakładaniem stosu a operowaniem na nim.

Kasperd zapytany w komentarzu zaakceptowanej odpowiedzi:

Przykłady Javy i C używają zupełnie innych nazw rejestrów. Czy oba przykłady używają 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

Nie mam wystarczającej reputacji, aby odpowiedzieć na to w komentarzach, ale to są te same ISA. Warto podkreślić, że wersja GCC wykorzystuje 32-bitową logikę całkowitą, a wersja skompilowana JVM wykorzystuje wewnętrznie 64-bitową logikę całkowitą.

R8 do R15 to tylko nowe X86_64 rejestry . EAX do EDX są dolnymi częściami rejestrów ogólnego przeznaczenia RAX do RDX. Ważną częścią odpowiedzi jest to, że wersja GCC nie jest rozwijana. Po prostu wykonuje jedną rundę pętli na rzeczywistą pętlę kodu maszynowego. Podczas gdy wersja JVM ma 16 rund pętli w jednej fizycznej pętli (na podstawie odpowiedzi rustyxa, nie reinterpretowałem montażu). Jest to jeden z powodów, dla których jest więcej rejestrów używanych, ponieważ ciało pętli jest w rzeczywistości 16 razy dłuższe.

Chociaż nie jest to bezpośrednio związane ze środowiskiem, tak dla ciekawości, zrobiłem ten sam test na. Net Core 2.1, x64, release mode.

Oto interesujący wynik, potwierdzający podobną fonomenę (na odwrót) zachodzącą po ciemnej stronie mocy. Kod:

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");
    }
}

Wynik:

2 * (i * i)

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

2 * i * i

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

Mam podobne wyniki:

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

Otrzymałem te same wyniki, jeśli obie pętle były w tym samym programie, lub każda była w osobnym programie .plik java/.Klasa, wykonywana w osobnym biegu.

Wreszcie, oto javap -c -v <.java> dekompilacja każdego:

     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

FYI -

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)

Ciekawa obserwacja przy użyciu Java 11 i wyłączaniu rozwijania pętli za pomocą następującej opcji VM:

-XX:LoopUnrollLimit=0

Pętla z wyrażeniem 2 * (i * i) powoduje powstanie bardziej zwartego kodu natywnego¹:

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

W porównaniu z wersją 2 * i * i:

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

Wersja Java:

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)

Wyniki porównawcze:

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 source code:

@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 - używane opcje maszyny wirtualnej: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0}

Próbowałem JMH używając domyślnego archetypu: dodałem również zoptymalizowaną wersję opartą na wyjaśnieniu Runemoro.

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

Wyniki są tutaj:

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

Na moim PC (Core i7 860-nie robi nic poza czytaniem na moim smartfonie):

• n += i*i then n*2 is first
• 2 * (i * i) jest drugi.

JVM wyraźnie nie optymalizuje się tak, jak człowiek (na podstawie odpowiedzi Runemoro).

Teraz następnie odczyt kodu bajtowego: javap -c -v ./target/classes/org/sample/MyBenchmark.class

• różnice między 2*(I*i) (po lewej) i 2*i*i (po prawej) tutaj: https://www.diffchecker.com/cvSFppWI
• różnice między 2*(i*i) A wersją zoptymalizowaną tutaj: https://www.diffchecker.com/I1XFu5dP

Nie jestem ekspertem od bajtowego kodu, ale my iload_2 przed imul: to prawdopodobnie miejsce, gdzie masz różnicę: mogę przypuszczać, że JVM optymalizuje odczyt i dwa razy (i jest już tutaj, a jest nie ma potrzeby ładowania go ponownie) podczas gdy w 2*i*i nie może.

Bardziej jako dodatek. Zrobiłem repro eksperymentu przy użyciu najnowszej Java 8 JVM od IBM:

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)

A to pokazuje bardzo podobne wyniki:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(Drugie wyniki z użyciem 2 * i * i).

Co ciekawe, gdy działa na tym samym komputerze, ale używając Oracle Java:

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)

Wyniki są średnio nieco wolniejsze:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

W skrócie: nawet mniejszy numer wersji HotSpot ma tutaj znaczenie, ponieważ subtelne różnice w implementacji JIT mogą mieć znaczące efekty.

Dwie metody dodawania generują nieco inny kod bajtowy:

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

Dla 2 * (i * i) vs:

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

Dla 2 * i * i.

I przy użyciu JMH benchmark taki jak ten:

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

}

Różnica jest jasna:

# 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

To, co obserwujesz, jest poprawne, a nie tylko anomalią Twojego stylu benchmarkingu (np. brak rozgrzewki, zobacz Jak napisać poprawny mikro-benchmark w Javie?)

Running again with 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

Widzisz, że wyniki są znacznie bliższe, co ma sens, ponieważ Graal jest ogólnie lepiej działającym, bardziej nowoczesnym kompilatorem.

Więc to zależy tylko od tego, jak dobrze kompilator JIT jest w stanie zoptymalizować konkretny fragment kodu i niekoniecznie ma do tego logiczny powód.