Lọ sao 2 * (i * i) Lọ 2 * i * i trong Java?

Khi phép nhân là 2 * (i * i), JVM có thể nhân hệ số nhân với 2 từ vòng lặp, dẫn đến mã tương đương nhưng hiệu quả hơn này:

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

nhưng khi phép nhân là (2 * i) * i, JVM không tối ưu hóa nó vì phép nhân với hằng số không còn đúng trước khi bổ sung.

Dưới đây là một vài lý do tại sao tôi nghĩ rằng đây là trường hợp:

• Việc thêm một câu lệnh if (n == 0) n = 1 khi bắt đầu vòng lặp dẫn đến cả hai phiên bản đều hiệu quả, vì việc bao thanh toán nhân không còn đảm bảo rằng kết quả sẽ giống nhau
• Phiên bản được tối ưu hóa (bằng cách bao gồm phép nhân với 2) chính xác nhanh như phiên bản 2 * (i * i)

Đây là mã kiểm tra mà tôi đã sử dụng để rút ra những kết luận sau:

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

Và đây là kết quả:

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

Mã byte: https://cs.nyu.edu/cifts/fall00/V22.0201-001/jvm2.html Mã byte Trình xem: https://github.com/Konloch/bytecode-viewer

Trên JDK của tôi (Windows 10 64 bit, 1.8.0_65-b17) tôi có thể sao chép và giải thích:

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

Đầu ra:

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

Vậy tại sao? Mã byte là đây:

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

Sự khác biệt là: Với dấu ngoặc (2 * (i * i)):

• Đẩy const stack
• Đẩy cục bộ lên ngăn xếp
• Đẩy cục bộ lên ngăn xếp
• nhân lên trên cùng của ngăn xếp
• nhân lên trên cùng của ngăn xếp

Không có dấu ngoặc (2 * i * i):

• Đẩy const stack
• Đẩy cục bộ lên ngăn xếp
• nhân lên trên cùng của ngăn xếp
• Đẩy cục bộ lên ngăn xếp
• nhân lên trên cùng của ngăn xếp

Tải tất cả vào ngăn xếp và sau đó làm việc trở lại nhanh hơn so với chuyển đổi giữa việc đặt lên ngăn xếp và vận hành trên nó.

Kasperd hỏi trong một bình luận về câu trả lời được chấp nhận:

Các ví dụ Java và C sử dụng các tên đăng ký khá khác nhau. Cả hai ví dụ đều sử dụng AMD AMD64?

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

Tôi không có đủ danh tiếng để trả lời điều này trong các bình luận, nhưng đây là cùng một ISA. Thật đáng để chỉ ra rằng phiên bản GCC sử dụng logic số nguyên 32 bit và phiên bản được biên dịch JVM sử dụng logic số nguyên 64 bit bên trong.

R8 đến R15 chỉ là các thanh ghi X86_64 mới . EAX đến EDX là các phần thấp hơn của các thanh ghi mục đích chung RAX đến RDX. Phần quan trọng trong câu trả lời là phiên bản GCC không được kiểm soát. Nó chỉ đơn giản thực hiện một vòng lặp trên mỗi vòng lặp mã máy thực tế. Mặc dù phiên bản JVM có 16 vòng lặp trong một vòng lặp vật lý (dựa trên câu trả lời rustyx, tôi đã không diễn giải lại hội). Đây là một trong những lý do tại sao có nhiều thanh ghi được sử dụng vì thân vòng lặp thực sự dài hơn 16 lần.

Mặc dù không liên quan trực tiếp đến môi trường của câu hỏi, chỉ vì tò mò, tôi đã thực hiện thử nghiệm tương tự trên .NET Core 2.1, x64, chế độ phát hành.

Đây là kết quả thú vị, xác nhận âm vị tương tự (cách khác xung quanh) xảy ra trên mặt tối của lực lượng. Mã số:

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

Kết quả:

2 * (i * i)

• kết quả: 119860736, 438 ms
• kết quả: 119860736, 433 ms
• kết quả: 119860736, 437 ms
• kết quả: 119860736, 435 ms
• kết quả: 119860736, 436 ms
• kết quả: 119860736, 435 ms
• kết quả: 119860736, 435 ms
• kết quả: 119860736, 439 ms
• kết quả: 119860736, 436 ms
• kết quả: 119860736, 437 ms

2 * i * i

• kết quả: 119860736, 417 ms
• kết quả: 119860736, 417 ms
• kết quả: 119860736, 417 ms
• kết quả: 119860736, 418 ms
• kết quả: 119860736, 418 ms
• kết quả: 119860736, 417 ms
• kết quả: 119860736, 418 ms
• kết quả: 119860736, 416 ms
• kết quả: 119860736, 417 ms
• kết quả: 119860736, 418 ms

Tôi đã nhận được kết quả tương tự:

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

Tôi đã nhận được kết quảGIỐNGnếu cả hai vòng lặp trong cùng một chương trình hoặc mỗi vòng lặp nằm trong một tệp .Java /. Class riêng biệt, được thực hiện trên một lần chạy riêng.

Cuối cùng, đây là một dịch ngược javap -c -v <.Java> của mỗi:

     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)

Tôi đã thử một JMH bằng cách sử dụng nguyên mẫu mặc định: Tôi cũng đã thêm một phiên bản được tối ưu hóa dựa trên lời giải thích của 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;
  }
}

Kết quả là đây:

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

Trên PC của tôi ( Core i7 860 - nó không làm gì khác ngoài việc đọc trên điện thoại thông minh của tôi):

• n += i*i sau đó n*2 là đầu tiên
• 2 * (i * i) là thứ hai.

JVM rõ ràng là không tối ưu hóa theo cách tương tự như con người (dựa trên câu trả lời của Runemoro).

Bây giờ sau đó, đọc mã byte: javap -c -v ./target/classes/org/sample/MyBenchmark.class

• Sự khác nhau giữa 2 * (i * i) (trái) và 2 * i * i (phải) tại đây: https://www.diffchecker.com/cvSFppWI
• Sự khác biệt giữa 2 * (i * i) và phiên bản được tối ưu hóa tại đây: https://www.diffchecker.com/I1XFu5dP

Tôi không phải là chuyên gia về mã byte, nhưng chúng tôi iload_2 trước khi chúng tôi imul: đó có thể là nơi bạn nhận được sự khác biệt: Tôi có thể giả sử rằng JVM tối ưu hóa việc đọc i hai lần (i đã ở đây và không cần tải lại 2*i*i không thể.

Thêm một phụ lục. Tôi đã repro thử nghiệm bằng cách sử dụng JVM Java 8 mới nhất từ ​​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)

Và điều này cho thấy kết quả rất giống nhau:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(kết quả thứ hai sử dụng 2 * i * i).

Thật thú vị, khi chạy trên cùng một máy, nhưng sử dụng 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)

kết quả trung bình chậm hơn một chút:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

Câu chuyện dài: ngay cả số phiên bản nhỏ của vấn đề HotSpot ở đây, vì sự khác biệt tinh tế trong triển khai JIT có thể có tác dụng đáng chú ý.

Quan sát thú vị bằng cách sử dụng Java 11 và tắt tắt vòng lặp với việc tùy chọn VM sau:

-XX:LoopUnrollLimit=0

Vòng lặp với biểu thức 2 * (i * i) dẫn đến mã gốc nhỏ gọn hơn¹:

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

so với phiên bản 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

Phiên bản 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)

Kết quả điểm chuẩn:

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

Mã nguồn điểm chuẩn:

@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 tùy chọn được sử dụng: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0}

Hai phương thức thêm làm tạo mã byte hơi khác nhau:

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

Dành cho 2 * (i * i) so với:

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

Dành cho 2 * i * i.

Và khi sử dụng a JMH điểm chuẩn như thế này:

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

}

Sự khác biệt là rõ ràng:

# 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

Những gì bạn quan sát là chính xác và không chỉ là sự bất thường trong phong cách đo điểm chuẩn của bạn (tức là không khởi động, xem Làm cách nào để tôi viết một điểm chuẩn vi mô chính xác trong Java? )

Chạy lại với 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

Bạn thấy rằng các kết quả gần hơn nhiều, điều này có ý nghĩa, vì Graal là một trình biên dịch tổng thể hoạt động tốt hơn, hiện đại hơn.

Vì vậy, điều này thực sự phụ thuộc vào mức độ mà trình biên dịch JIT có thể tối ưu hóa một đoạn mã cụ thể và không nhất thiết phải có lý do hợp lý với nó.