Counting down to zero in contrast to counting up to length - 1

Question

Is it recommended to count in small loops (where possible) down from length - 1 to zero instead of counting up to length - 1?

1.) Counting down

for (int i = a.length - 1; i >= 0; i--) {
    if (a[i] == key) return i;
}

2.) Counting up

for (int i = 0; i < a.length; i++) {
    if (a[i] == key) return i;
}

The first one is slightly faster that the second one (because comparing to zero is faster) but is a little more error-prone in my opinion. Besides, the first one could maybe not be optimized by future improvements of the JVM. Any ideas on that?

Answer 1

I would recommend you to make sure you have benchmark showing that this is a performance issue before doing too much changes like this. I'd go for the most readable any day (in my opinion it's the one counting upwards).

If you are into micro optimizations and don't trust the compiler to do the right thing, maybe you should consider caching a.length in a variable in the second loop to avoid an indirection as well.

Answer 2

If you store the result of a.length in variable, it won't be any "faster" if it is actually so. In any event, it is rarely worth worrying about the performance of such a trivial operation. Focus on the readability of the method.

For me, counting up is more readable.

Answer 3

In my opinion, it's far better to favour convention and readability (in this case, the count-up approach) over preemptive optimisation. According to Josh Bloch, it's better not to optimise your code until you are sure that optimisation is required.

Answer 4

I'd say if there is a reason to count one way vs. the other (say order of the items in the list) then don't twist yourself in a knot trying to go with convention (From experience, count up); If there isn't - make it easier for the next person to work on and just go with convention.

Comparing to 0 vs. comparing to int shouldn't really be a concern...

Answer 5

Counting downwards tends to be slower, despite the possibility to drop one machine code instruction. In the modern day, performance ain't that simple. Compilers have optimisation geared towards forward loop, so you reverse loop may miss out on optimisation. Cache hardware is designed for normal forward scanning. So don't worry about this sort of micro-optimisation (and if you ever find yourself in a situation where you really need to, measure).

Answer 6

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil", Donald Knuth.

In this case I would argue that any possible performance gain would be outweighed by the loss of readability alone. Programmer hours are much more expensive than cpu hours.

P.S.: To further improve performance you should consider testing for inequality to zero. But watch out for empty arrays ;)