Htykuut

When the multiplication is 2 * (i * i), the JVM is able to factor out the multiplication by 2 from the loop, resulting in this equivalent but more efficient code:

int n = 0;

for (int i = 0; i < 1000000000; i++) {

    n += i * i;

}

n *= 2;

but when the multiplication is (2 * i) * i, the JVM doesn't optimize it since the multiplication by a constant is no longer right before the addition.

Here are a few reasons why I think this is the case:

• Adding an if (n == 0) n = 1 statement at the start of the loop results in both versions being as efficient, since factoring out the multiplication no longer guarantees that the result will be the same


• The optimized version (by factoring out the multiplication by 2) is exactly as fast as the 2 * (i * i) version

Here is the test code that I used to draw these conclusions:

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;

}

And here are the results:

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

ByteCodes: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html

ByteCodes Viewer: https://github.com/Konloch/bytecode-viewer

On my JDK (Win10 64 1.8.0_65-b17) I can reproduce and explain:

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;

}

Output:

...

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

So why?
The Byte code is this:

 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 {

     }

 }

The difference being:

With brackets (2 * (i * i)):

• push const stack


• push local on stack


• push local on stack


• multiply top of stack


• multiply top of stack

Without brackets (2 * i * i):

• push const stack


• push local on stack


• multiply top of stack


• push local on stack


• multiply top of stack

Loading all on stack and then working back down is faster than switching between putting on stack and operating on it.

Kasperd asked in a comment of the accepted answer:

The Java and C examples use quite different register names. Are both example using the 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

I don't have enough reputation to answer this in the comments, but these are the same ISA. It's worth pointing out that the GCC version uses 32-bit integer logic and the JVM compiled version uses 64-bit integer logic internally.

R8 to R15 are just new X86_64 registers. EAX to EDX are the lower parts of the RAX to RDX general purpose registers. The important part in the answer is that the GCC version is not unrolled. It simply executes one round of the loop per actual machine code loop. While the JVM version has 16 rounds of the loop in one physical loop (based on rustyx answer, I did not reinterpret the assembly). This is one of the reasons why there are more registers being used since the loop body is actually 16 times longer.

While not directly related to the question's environment, just for the curiosity, I did the same test on .Net Core 2.1, x64, release mode.
Here is the interesting result, confirming same phonemenia happening over the dark side of the force. 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");

        }

    }

Result:

2 * (i * i)

• result:119860736, 438ms


• result:119860736, 433ms


• result:119860736, 437ms


• result:119860736, 435ms


• result:119860736, 436ms


• result:119860736, 435ms


• result:119860736, 435ms


• result:119860736, 439ms


• result:119860736, 436ms


• result:119860736, 437ms

2 * i * i

• result:119860736, 417ms


• result:119860736, 417ms


• result:119860736, 417ms


• result:119860736, 418ms


• result:119860736, 418ms


• result:119860736, 417ms


• result:119860736, 418ms


• result:119860736, 416ms


• result:119860736, 417ms


• result:119860736, 418ms

I got similar results:

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

2 * i * i: 0.580255126 s, n=119860736

I got the SAME results if both loops were in the same program, or each was in a separate .java file/.class, executed on a separate run.

Finally, here is a javap -c -v <.java> decompile of each:

     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)

I tried a JMH using the default archetype: I also added optimized version based Runemoro' explanation .

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

  }

}

The result are here:

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

On my PC (Core i7 860, doing nothing much apart reading on my smartphone):

• 
  n += i*i then n*2 is first


• 
  2 * (i * i) is second.

The JVM is clearly not optimizing the same way than a human does (based on Runemoro answer).

Now then, reading bytecode: javap -c -v ./target/classes/org/sample/MyBenchmark.class

• Differences between 2*(i*i) (left) and 2*i*i (right) here: https://www.diffchecker.com/cvSFppWI
  


• Differences between 2*(i*i) and the optimized version here: https://www.diffchecker.com/I1XFu5dP
  

I am not expert on bytecode but we iload_2 before we imul: that's probably where you get the difference: I can suppose that the JVM optimize reading i twice (i is already here, there is no need to load it again) whilst in the 2*i*i it can't.

More of an addendum. I did repro the experiment using the latest Java 8 JVM from 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)

and this shows very similar results:

0.374653912 s

n = 119860736

0.447778698 s

n = 119860736

( second results using 2 * i * i ).

Interestingly enough, when running on the same machine, but using 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)

results are on average a bit slower:

0.414331815 s

n = 119860736

0.491430656 s

n = 119860736

Long story short: even the minor version number of HotSpot matter here, as subtle differences within the JIT implementation can have notable effects.

Interesting observation using Java 11 and switching off loop unrolling with the following VM option:

-XX:LoopUnrollLimit=0

The loop with the 2 * (i * i) expression results in a more compact native code¹:

L0001: add    eax,r11d

       inc    r8d

       mov    r11d,r8d

       imul   r11d,r8d

       shl    r11d,1h

       cmp    r8d,r10d

       jl     L0001

in comparison with the 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 results:

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)

public class LoopTest {



    @Param(value = "1000000000") private int size;



    public static void main(String args) throws RunnerException {

        new Runner(new OptionsBuilder()

             .include(LoopTest.class.getSimpleName())

             .jvmArgs("-XX:LoopUnrollLimit=0")

             .build()).run();

    }



    @Fork(1)

    @Benchmark

    public int slow() {

        int n = 0;

        for (int i = 0; i < size; i++) {

            n += 2 * i * i;

        }

        return n;

    }



    @Fork(1)

    @Benchmark

    public int fast() {

        int n = 0;

        for (int i = 0; i < size; i++) {

            n += 2 * (i * i);

        }

        return n;

    }

}

^{1 - VM options used: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0.}

If we take just two terms of summation, it can be seen that -

in former case simple mathematical fact holds true:

(3 multiplications)

, but because of operator precedence rules, we get in latter case :

(4 multiplications)