Bdtyktl

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.

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.

I can't reproduce your claim. This java fiddle mostly gets the "opposite" result:

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)