Loop counter in Java API

Question

All,

While going through some of the files in Java API, I noticed many instances where the looping counter is being decremented rather than increment. i.e. in for and while loops in String class. Though this might be trivial, is there any significance for decrementing the counter rather than increment?

Answer 1

I've compiled two simple loops with eclipse 3.6 (java 6) and looked at the byte code whether we have some differences. Here's the code:

for(int i = 2; i >= 0; i--){}
for(int i = 0; i <= 2; i++){}

And this is the bytecode:

// 1st for loop - decrement 2 -> 0
 0 iconst_2
 1 istore_1      // i:=2
 2 goto 8
 5 inc 1 -1      // i+=(-1)
 8 iload_1
 9 ifge 5        // if (i >= 0) goto 5

// 2nd for loop - increment 0 -> 2
12 iconst_0 
13 istore_1      // i:=0
14 goto 20
17 inc 1 1       // i+=1
20 iload_1
21 iconst 2
22 if_icmple 17  // if (i <= 2) goto 17

The increment/decrement operation should make no difference, it's either +1 or +(-1). The main difference in this typical(!) example is that in the first example we compare to 0 (ifge i), in the second we compare to a value (if_icmple i 2). And the comaprision is done in each iteration. So if there is any (slight) performance gain, I think it's because it's less costly to compare with 0 then to compare with other values. So I guess it's not incrementing/decrementing that makes the difference but the stop criteria.

So if you're in need to do some micro-optimization on source code level, try to write your loops in a way that you compare with zero, otherwise keep it as readable as possible (and incrementing is much easier to understand):

 for (int i =  0; i <= 2; i++) {}  // readable
 for (int i = -2; i <= 0; i++) {}  // micro-optimized and "faster" (hopefully)

Addition

Yesterday I did a very basic test - just created a 2000x2000 array and populated the cells based on calculations with the cell indices, once counting from 0->1999 for both rows and cells, another time backwards from 1999->0. I wasn't surprised that both scenarios had a similiar performance (185..210 ms on my machine).

So yes, there is a difference on byte code level (eclipse 3.6) but, hey, we're in 2010 now, it doesn't seem to make a significant difference nowadays. So again, and using Stephens words, "don't waste your time" with this kind of optimization. Keep the code readable and understandable.

Answer 2

When in doubt, benchmark.

public class IncDecTest
{
    public static void main(String[] av)
    {
        long up = 0;
        long down = 0;
        long upStart, upStop;
        long downStart, downStop;
        long upStart2, upStop2;
        long downStart2, downStop2;

        upStart = System.currentTimeMillis();
        for( long i = 0; i < 100000000; i++ )
        {
            up++;
        }
        upStop = System.currentTimeMillis();

        downStart = System.currentTimeMillis();
        for( long j = 100000000; j > 0; j-- )
        {
            down++;
        }
        downStop = System.currentTimeMillis();

        upStart2 = System.currentTimeMillis();
        for( long k = 0; k < 100000000; k++ )
        {
            up++;
        }
        upStop2 = System.currentTimeMillis();

        downStart2 = System.currentTimeMillis();
        for( long l = 100000000; l > 0; l-- )
        {
            down++;
        }
        downStop2 = System.currentTimeMillis();

        assert (up == down);

        System.out.println( "Up: " + (upStop - upStart));
        System.out.println( "Down: " + (downStop - downStart));     
        System.out.println( "Up2: " + (upStop2 - upStart2));
        System.out.println( "Down2: " + (downStop2 - downStart2));
    }
}

With the following JVM:

java version "1.6.0_22"
Java(TM) SE Runtime Environment (build 1.6.0_22-b04-307-10M3261)
Java HotSpot(TM) 64-Bit Server VM (build 17.1-b03-307, mixed mode)

Has the following output (ran it multiple times to make sure the JVM was loaded and to make sure the numbers settled down a little).

$ java -ea IncDecTest
Up: 86
Down: 84
Up2: 83
Down2: 84

These all come extremely close to one another and I have a feeling that any discrepancy is a fault of the JVM loading some code at some points and not others, or a background task happening, or simply falling over and getting rounded down on a millisecond boundary.

While at one point (early days of Java) there might have been some performance voodoo to be had, it seems to me that that is no longer the case.

Feel free to try running/modifying the code to see for yourself.

Answer 3

It is possible that this is a result of Sun engineers doing a whole lot of profiling and micro-optimization, and those examples that you found are the result of that. It is also possible that they are the result of Sun engineers "optimizing" based on deep knowledge of the JIT compilers ... or based on shallow / incorrect knowledge / voodoo thinking.

It is possible that these sequences:

• are faster than the increment loops,
• are no faster or slower than increment loops, or
• are slower than increment loops for the latest JVMs, and the code is no longer optimal.

Either way, you should not emulate this practice in your code, unless thorough profiling with the latest JVMs demonstrates that:

• your code really will benefit from optimization, and
• the decrementing loop really is faster than the incrementing loop for your particular application.

And even then, you may find that your carefully hand optimized code is less than optimal on other platforms ... and that you need to repeat the process all over again.

These days, it is generally recognized that the best first strategy is to write simple code and leave optimization to the JIT compiler. Writing complicated code (such as loops that run in reverse) may actually foil the JIT compiler's attempts to optimize.