Mengapa 2 * (i * i) lebih cepat dari 2 * i * i di Jawa?

Ketika perkalian adalah 2 * (i * i), JVM dapat memperhitungkan faktor perkalian dengan 2 dari loop, menghasilkan kode yang setara namun lebih efisien ini:

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

tetapi ketika multiplikasi adalah (2 * i) * i, JVM tidak mengoptimalkannya karena perkalian dengan konstanta tidak lagi tepat sebelum penambahan.

Berikut adalah beberapa alasan mengapa saya pikir inilah masalahnya:

• Menambahkan pernyataan if (n == 0) n = 1 pada awal loop menghasilkan kedua versi sama efisiennya, karena mengabaikan multiplikasi tidak lagi menjamin bahwa hasilnya akan sama.
• Versi yang dioptimalkan (dengan memperhitungkan keluar perkalian 2) sama persis dengan versi 2 * (i * i)

Berikut ini adalah kode tes yang saya gunakan untuk menarik kesimpulan ini:

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

Dan inilah hasilnya:

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

Kode byte: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Byte codes Viewer: https://github.com/Konloch/bytecode-viewer

Di JDK saya (Windows 10 64 bit, 1.8.0_65-b17) saya dapat mereproduksi dan menjelaskan:

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

Keluaran:

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

Jadi kenapa? Kode byte adalah ini:

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

Perbedaannya adalah: Dengan kurung (2 * (i * i)):

• Dorong tumpukan const
• Dorong tumpukan lokal
• Dorong tumpukan lokal
• gandakan bagian atas tumpukan
• gandakan bagian atas tumpukan

Tanpa tanda kurung (2 * i * i):

• Dorong tumpukan const
• Dorong tumpukan lokal
• gandakan bagian atas tumpukan
• Dorong tumpukan lokal
• gandakan bagian atas tumpukan

Memuat semua pada tumpukan dan kemudian bekerja kembali lebih cepat daripada beralih antara meletakkan di atas tumpukan dan mengoperasikannya.

Kasperd bertanya dalam komentar dari jawaban yang diterima:

Contoh Java dan C menggunakan nama register yang sangat berbeda. Apakah kedua contoh menggunakan 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

Saya tidak memiliki reputasi yang cukup untuk menjawab ini di komentar, tetapi ini adalah ISA yang sama. Perlu ditunjukkan bahwa versi GCC menggunakan logika integer 32-bit dan versi kompilasi JVM menggunakan logika integer 64-bit secara internal.

R8 ke R15 hanyalah X86_64 baru register . EAX ke EDX adalah bagian bawah register tujuan umum RAX ke RDX. Bagian penting dalam jawabannya adalah bahwa versi GCC tidak terbuka. Ini hanya menjalankan satu putaran loop per loop kode mesin yang sebenarnya. Sementara versi JVM memiliki 16 putaran loop dalam satu loop fisik (berdasarkan jawaban rustyx, saya tidak menafsirkan ulang Majelis). Ini adalah salah satu alasan mengapa ada lebih banyak register yang digunakan karena loop body sebenarnya 16 kali lebih lama.

Meskipun tidak terkait langsung dengan lingkungan pertanyaan, hanya untuk rasa ingin tahu, saya melakukan tes yang sama pada. NET Core 2.1, x64, mode rilis.

Ini adalah hasil yang menarik, mengkonfirmasikan phonomena yang serupa (sebaliknya) terjadi di sisi gelap gaya. Kode:

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

Hasil:

2 * (i * i)

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

2 * i * i

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

Saya mendapat hasil yang serupa:

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

Saya mendapatSAMAhasil jika kedua loop berada di program yang sama, atau masing-masing dalam file .Java/.class terpisah, dieksekusi pada menjalankan yang terpisah.

Akhirnya, inilah dekompilasi javap -c -v <.Java> masing-masing:

     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)

Saya mencoba JMH menggunakan pola dasar default: Saya juga menambahkan versi yang dioptimalkan berdasarkan Penjelasan 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;
  }
}

Hasilnya ada di sini:

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

Di PC saya ( Core i7 860 - tidak ada artinya selain membaca di smartphone saya):

• n += i*i maka n*2 adalah yang pertama
• 2 * (i * i) adalah yang kedua.

JVM jelas tidak mengoptimalkan dengan cara yang sama dengan manusia (berdasarkan jawaban Runemoro).

Nah, membaca bytecode: javap -c -v ./target/classes/org/sample/MyBenchmark.class

• Perbedaan antara 2 * (i * i) (kiri) dan 2 * i * i (kanan) di sini: https://www.diffchecker.com/cvSFppWI
• Perbedaan antara 2 * (i * i) dan versi yang dioptimalkan di sini: https://www.diffchecker.com/I1XFu5dP

Saya bukan ahli bytecode, tapi kami iload_2 sebelum kami imul: di situlah Anda mendapatkan perbedaan: Saya dapat menduga bahwa JVM mengoptimalkan pembacaan i dua kali (i sudah ada di sini, dan tidak perlu memuat lagi) sementara 2*i*i tidak bisa.

Lebih dari sebuah tambahan. Saya melakukan repro percobaan menggunakan Java 8 JVM terbaru dari 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)

Dan ini menunjukkan hasil yang sangat mirip:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(hasil kedua menggunakan 2 * i * i).

Cukup menarik, ketika berjalan di mesin yang sama, tetapi menggunakan 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)

hasilnya rata-rata sedikit lebih lambat:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

Singkat cerita: bahkan nomor versi kecil masalah HotSpot di sini, karena perbedaan halus dalam implementasi JIT dapat memiliki efek penting.

Pengamatan menarik menggunakan Java 11 dan mematikan loop terbuka dengan opsi VM berikut:

-XX:LoopUnrollLimit=0

Pengulangan dengan ekspresi 2 * (i * i) menghasilkan kode asli yang lebih ringkas¹:

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

dibandingkan dengan versi 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

Versi 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)

Hasil patok banding:

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

Kode sumber patokan:

@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 opsi yang digunakan: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0}

Dua metode penambahan memang menghasilkan kode byte yang sedikit berbeda:

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

Untuk 2 * (i * i) vs:

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

Untuk 2 * i * i.

Dan ketika menggunakan JMH benchmark seperti ini:

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

}

Perbedaannya jelas:

# 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

Apa yang Anda amati benar, dan bukan hanya anomali dari gaya pembandingan Anda (mis. Tidak ada pemanasan, lihat Bagaimana cara saya menulis pembandingan mikro di Jawa? )

Berlari lagi dengan 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

Anda melihat bahwa hasilnya jauh lebih dekat, yang masuk akal, karena Graal adalah kompiler yang berkinerja lebih baik, lebih modern, secara keseluruhan.

Jadi ini benar-benar hanya sampai seberapa baik kompiler JIT mampu mengoptimalkan potongan kode tertentu, dan tidak selalu memiliki alasan logis untuk itu.