왜 2 * (i * i)가 Java에서 2 * i * i보다 빠릅니까?

곱셈이 2 * (i * i) 일 때 JVM은 루프에서 2로 곱셈을 배제 할 수 있습니다. 그 결과 코드는 같지만 효율적인 코드가됩니다.

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

그러나 곱셈이 (2 * i) * i 일 때, 상수에 의한 곱셈은 더하기 직전이 아니기 때문에 JVM은이를 최적화하지 않습니다.

왜 그런지 생각하는 몇 가지 이유가 있습니다.

• 루프의 시작 부분에 if (n == 0) n = 1 문을 추가하면 곱셈을 고려해야 더 이상 결과가 동일하지 않을 것이므로 효율적인 두 버전이됩니다.
• 최적화 된 버전 (곱셈을 2로 나눔으로써)은 2 * (i * i) 버전만큼 빠릅니다.

다음은 이러한 결론을 도출하는 데 사용한 테스트 코드입니다.

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

결과는 다음과 같습니다.

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

바이트 코드 : https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html 바이트 코드 뷰어 : https://github.com/Konloch/bytecode-viewer

내 JDK (Windows 10 64 비트, 1.8.0_65-b17)에서 다음을 재현하고 설명 할 수 있습니다.

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

산출:

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

차이점은 : 괄호 (2 * (i * i)) 포함 :

• 푸시 스택
• 스택에서 로컬 푸시
• 스택에서 로컬 푸시
• 스택 맨 위에 곱하기
• 스택 맨 위에 곱하기

대괄호 (2 * i * i)없이 :

• 푸시 스택
• 스택에서 로컬 푸시
• 스택 맨 위에 곱하기
• 스택에서 로컬 푸시
• 스택 맨 위에 곱하기

스택에 모든 내용을로드 한 다음 다시 작업하는 것은 스택에 놓고 조작하는 것보다 전환하는 것이 빠릅니다.

Kasperd 허용 된 대답의 의견에 물었다 :

자바와 C 예제는 상당히 다른 레지스터 이름을 사용합니다. 두 가지 모두 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

나는 코멘트에서 이것에 대답하기에 충분한 평판이 없지만, 이것들은 같은 ISA이다. GCC 버전은 32 비트 정수 논리를 사용하고 JVM 컴파일 버전은 64 비트 정수 논리를 내부적으로 사용한다는 점은 가치가 있습니다.

R8 ~ R15는 새로운 X86_64 레지스터 입니다. EAX에서 EDX는 RAX에서 RDX 범용 레지스터의 하위 부분입니다. 대답의 중요한 부분은 GCC 버전이 배포되지 않았다는 것입니다. 실제 기계 코드 루프 당 루프의 한 라운드 만 실행합니다. JVM 버전은 하나의 물리적 루프에 16 루프의 루프가 있지만 (rustyx 응답을 기반으로, 어셈블리를 재 해석하지 않았습니다). 이것은 루프 본문이 실제로 16 배 더 길기 때문에 더 많은 레지스터가 사용되는 이유 중 하나입니다.

호기심과 관련하여 질문의 환경과 직접적인 관련이 없지만 .NET Core 2.1, x64, 릴리스 모드에 대해서도 동일한 테스트를 수행했습니다.

흥미 진진한 결과가 있습니다. 힘의 어두운면에서 비슷한 음운이 나타납니다 (다른 방향으로). 암호:

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

결과:

2 * (i * i)

• 결과 : 119860736, 438 ms
• 결과 : 119860736, 433 ms
• 결과 : 119860736, 437 ms
• 결과 : 119860736, 435 ms
• 결과 : 119860736, 436 ms
• 결과 : 119860736, 435 ms
• 결과 : 119860736, 435 ms
• 결과 : 119860736, 439 ms
• 결과 : 119860736, 436 ms
• 결과 : 119860736, 437 ms

2 * i * i

• 결과 : 119860736, 417 ms
• 결과 : 119860736, 417 ms
• 결과 : 119860736, 417 ms
• 결과 : 119860736, 418ms
• 결과 : 119860736, 418ms
• 결과 : 119860736, 417 ms
• 결과 : 119860736, 418ms
• 결과 : 119860736, 416 ms
• 결과 : 119860736, 417 ms
• 결과 : 119860736, 418ms

비슷한 결과가 있습니다.

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

두 루프가 같은 프로그램에 있거나 각각의 .Java 파일/.class에 별도의 실행에서 실행되는 경우SAMEresults가 있습니다.

마지막으로, 각각의 javap -c -v <.Java> 디 컴파일이 있습니다 :

     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

참고 -

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)

나는 기본 아키 타입을 사용하여 JMH를 시도했다 : 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;
  }
}

결과는 다음과 같습니다.

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

내 PC에서 ( Core i7 860 - 내 스마트 폰에서 읽는 것과 별개로 아무것도하지 않습니다.)

• n += i*i 다음에 n*2이 첫 번째입니다.
• 2 * (i * i)는 두 번째입니다.

JVM은 분명히 인간과 같은 방법을 최적화하지 않습니다 (Runemoro의 대답을 기반으로).

이제 바이트 코드 읽기 : javap -c -v ./target/classes/org/sample/MyBenchmark.class

• 2 * (i * i) (왼쪽)과 2 * i * i (오른쪽)의 차이점은 다음과 같습니다. https://www.diffchecker.com/cvSFppWI
• 2 * (i * i)와 최적화 된 버전의 차이점은 다음과 같습니다. https://www.diffchecker.com/I1XFu5dP

저는 바이트 코드에 대한 전문가는 아니지만 iload_2 전에 우리는 imulname__을 사용합니다. 차이점을 얻었을 것입니다. JVM이 i읽기를 두 번 최적화 (iname__은 이미 여기에 있으며 다시로드 할 필요가 없음) 할 수 있다고 가정 할 수 있습니다. 2*i*i 할 수 없습니다.

부록 추가. IBM의 최신 Java 8 JVM을 사용하여 실험을 재 작성했습니다.

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)

그리고 이것은 매우 유사한 결과를 보여줍니다 :

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(2 * i * i를 사용한 두 번째 결과).

흥미롭게도 동일한 시스템에서 실행될 때 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)

결과는 평균적으로 조금 느립니다.

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

긴 이야기가 짧다 : HotSpot의 마이너 버전 번호조차도 JIT 구현 내 미묘한 차이가 눈에 띄는 영향을 미칠 수 있기 때문에.

Java 11을 (를) 사용하여 흥미로운 관찰을하고 다음 VM 옵션을 사용하여 루프 언 롤링을 해제하십시오.

-XX:LoopUnrollLimit=0

2 * (i * i) 표현식을 사용하는 루프로 인해보다 간단한 네이티브 코드가 생성됩니다.¹:

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

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

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)

벤치 마크 결과 :

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

벤치 마크 소스 코드 :

@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 옵션 사용 : -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0}

추가하는 두 가지 방법은 약간 다른 바이트 코드를 생성합니다.

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

2 * (i * i) vs :

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

2 * i * i의 경우.

그리고 JMH 벤치 마크를 사용하면 다음과 같습니다.

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

}

차이점은 분명합니다.

# 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

관찰 한 것은 벤치마킹 스타일의 이상이 아니라 정확합니다 (예 : 웜업 없음 Java로 올바른 마이크로 벤치 마크를 작성하는 방법은 무엇입니까? ).

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

Graal은 전반적인 성능이 향상되고 현대적인 컴파일러이기 때문에 결과가 훨씬 더 가깝다는 것을 알 수 있습니다.

따라서 이것은 JIT 컴파일러가 특정 코드 조각을 얼마나 잘 최적화 할 수 있는지에 달려 있으며 반드시 논리적 이유가있는 것은 아닙니다.