Java loop efficiency
I compared the efficiency of nested for, while and do while loops in Java, and I encountered some strange results that I needed help understanding
public class Loops {
public static void main(String[] args) {
int L = 100000; // number of iterations per loop
// for loop
double start = System.currentTimeMillis();
long s1 = 0;
for (int i=0; i < L; i++) {
for (int j = 0; j < L; j++) {
s1 += 1;
}
}
double end = System.currentTimeMillis();
String result1 = String.format("for loop: %.5f",(end-start) / 1000);
System.out.println(s1);
System.out.println(result1);
// do-while loop
double start1 = System.currentTimeMillis();
int i = 0;
long s2 = 0;
do {
i++;
int j = 0;
do {
s2 += 1;
j++;
} while (j < L);
} while (i < L);
double end1 = System.currentTimeMillis();
String result2 = String.format("do-while: %.5f",(end1-start1) / 1000);
System.out.println(s2);
System.out.println(result2);
// while loop
double start2 = System.currentTimeMillis();
i = 0;
long s3 = 0;
while (i < L) {
i++;
int j = 0;
while (j < L) {
s3 += 1;
j++;
}
}
double end2 = System.currentTimeMillis();
String result3 = String.format("while: %.5f",(end2-start2) / 1000);
System.out.println(s3);
System.out.println(result3);
}
}
The respective counters of all cycles reach 10 billion; The result puzzled me:
For loop: 6.48300
do-while：0.41200
And: 9.71500
Why is the do while loop much faster? This performance gap extends in parallel with any change in L I run these loops independently and do the same
Solution
I've run the code you provided, and I'm surprised to find these performance differences Guided by curiosity, I began to investigate and found that although these cycles seem to do the same thing, there are some important differences between them
The result of running these cycles for the first time is:
for loop: 1.43100 do-while: 0.51300 while: 1.54500
However, when I run these three loops at least 10 times, the performance of these loops is almost the same
for loop: 0.43200 do-while: 0.46100 while: 0.42900
JIT can optimize these loops over time, but there must be some differences, resulting in different initial performance of these loops There are actually two differences:
>The do while loop executes fewer times than the for loop and the while loop
For simplicity, assume L = 1
long s1 = 0;
for (int i=0; i < L; i++) {
for (int j = 0; j < L; j++) {
s1 += 1;
Outer ring: 0 < 1 inner loop: 0 < 1 inner ring: 1 < 1 outer ring: 1 < 1 4 Comparisons
int i = 0;
long s2 = 0;
do {
i++;
int j = 0;
do {
s2 += 1;
j++;
} while (j < L);
} while (i < L);
Inner ring: 1 < 1 outer ring: 1 < 1 2 Comparisons > different generated bytecodes
For further investigation, I have changed your class slightly, which will not affect the work of the class
public class Loops {
final static int L = 100000; // number of iterations per loop
public static void main(String[] args) {
int round = 10;
while (round-- > 0) {
forLoop();
doWhileLoop();
whileLoop();
}
}
private static long whileLoop() {
int i = 0;
long s3 = 0;
while (i++ < L) {
int j = 0;
while (j++ < L) {
s3 += 1;
}
}
return s3;
}
private static long doWhileLoop() {
int i = 0;
long s2 = 0;
do {
int j = 0;
do {
s2 += 1;
} while (++j < L);
} while (++i < L);
return s2;
}
private static long forLoop() {
long s1 = 0;
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
s1 += 1;
}
}
return s1;
}
}
Then compile it and call javap - C - S - Private - L loop to get the bytecode
The first is the bytecode of dowileloop
0: iconst_0 // push the int value 0 onto the stack 1: istore_1 // store int value into variable 1 (i) 2: lconst_0 // push the long 0 onto the stack 3: lstore_2 // store a long value in a local variable 2 (s2) 4: iconst_0 // push the int value 0 onto the stack 5: istore 4 // store int value into variable 4 (j) 7: lload_2 // load a long value from a local variable 2 (i) 8: lconst_1 // push the long 1 onto the stack 9: ladd // add two longs 10: lstore_2 // store a long value in a local variable 2 (i) 11: iinc 4,1 // increment local variable 4 (j) by signed byte 1 14: iload 4 // load an int value from a local variable 4 (j) 16: iload_0 // load an int value from a local variable 0 (L) 17: if_icmplt 7 // if value1 is less than value2,branch to instruction at 7 20: iinc 1,1 // increment local variable 1 (i) by signed byte 1 23: iload_1 // load an int value from a local variable 1 (i) 24: iload_0 // load an int value from a local variable 0 (L) 25: if_icmplt 4 // if value1 is less than value2,branch to instruction at 4 28: lload_2 // load a long value from a local variable 2 (s2) 29: lreturn // return a long value
Bytecode of current while loop:
0: iconst_0 // push int value 0 onto the stack 1: istore_1 // store int value into variable 1 (i) 2: lconst_0 // push the long 0 onto the stack 3: lstore_2 // store a long value in a local variable 2 (s3) 4: goto 26 7: iconst_0 // push the int value 0 onto the stack 8: istore 4 // store int value into variable 4 (j) 10: goto 17 13: lload_2 // load a long value from a local variable 2 (s3) 14: lconst_1 // push the long 1 onto the stack 15: ladd // add two longs 16: lstore_2 // store a long value in a local variable 2 (s3) 17: iload 4 // load an int value from a local variable 4 (j) 19: iinc 4,1 // increment local variable 4 (j) by signed byte 1 22: iload_0 // load an int value from a local variable 0 (L) 23: if_icmplt 13 // if value1 is less than value2,branch to instruction at 13 26: iload_1 // load an int value from a local variable 1 (i) 27: iinc 1,1 // increment local variable 1 by signed byte 1 30: iload_0 // load an int value from a local variable 0 (L) 31: if_icmplt 7 // if value1 is less than value2,branch to instruction at 7 34: lload_2 // load a long value from a local variable 2 (s3) 35: lreturn // return a long value
To make the output more readable, I have attached comments describing the execution of each instruction based on "Java bytecode instruction lists"
If you look closely, you will see that there are significant differences between the two bytecodes The while loop (as well as the for loop) defines an IF statement (if_icmplt instruction) at the end of the bytecode This means that to check the exit condition of the first loop, you must call the conversion to line 26 and, similarly, go to line 17 of the second loop
The bytecode above is javac 1.6.0 on Mac OS X 0_ 45 generated
outline
I think the comparison of different quantities and the existence of goto instructions in the bytecode of while and for loops are the reasons for the performance differences between these loops