Why is “2 * (i * i)” faster than “2 * i * i”?

  • A+
Category:Languages

The following Java program takes on average between 0.50s and 0.55s to run:

public static void main(String[] args) {     long startTime = System.nanoTime();     int n = 0;     for (int i = 0; i < 1000000000; i++) {         n += 2 * (i * i);     }     System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");     System.out.println("n = " + n); } 

If I replace 2 * (i * i) with 2 * i * i, it takes between 0.60 and 0.65s to run. How come?

Edit: I ran each version of the program 15 times, alternating between the two. Here are the results:

2 * (i * i): 0.5183738, 0.5298337, 0.5308647, 0.5133458, 0.5003011, 0.5366181, 0.515149, 0.5237389, 0.5249942, 0.5641624, 0.538412, 0.5466744, 0.531159, 0.5048032, 0.5232789

2 * i * i: 0.6246434, 0.6049722, 0.6603363, 0.6243328, 0.6541802, 0.6312638, 0.6241105, 0.627815, 0.6114252, 0.6781033, 0.6393969, 0.6608845, 0.6201077, 0.6511559, 0.6544526

The fastest run of 2 * i * i took longer than the slowest run of 2 * (i * i). If they were both as efficient, the probability of this happening would be less than 1/2^15 = 0.00305%.

 


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 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: