Adverts
Have you ever wondered what the fastest way of making a for loop execute is? I did a long while back and it changed the way I wrote loops. When looping through a list most text books show for loops written like this (yes, I know iteration is preffered but there are some times when a for loop is what you want):
Many years ago I saw an example of a for loop written like this:
My initial thought that was that this was pretty wasteful as it appears to be declaring a variable that is unnecessary at best. I was intrigued though and decided to test it out. I wrote a quick little test case and lo-and-behold the variant with the extra variable was faster. At the time I wasn't completely sure why but I used it anyway. It's clear to me now why it's faster - the repeated values.size() method call in the first version adds over head which can't be recovered by the VM.
The reson the overhead can't be recovered isn't immediatly obvious until you realize that the list may change size while the loop is executing. Sure, most of the time the list won't change size but in a multi-threaded environment it might and that's the key point. Using the extra variable is only safe if you know that the list will only ever be manipulated by one thread at a time. If you use the extra variable and another thread removes an item while the list is being looped over the code will drop off the end and die horribly with an ArrayIndexOutOfBoundsException.
So why am I re-addressing this issue now? Two reasons: firstly I am trying to convince a colleague that there is an advantage to the extra variable and secondly because I wanted to see how the new style 5.0 for loop stacked up against the old looping constructs. The results for a test are shown below:
With N Runtime: 391 milliseconds. Without N Runtime: 562 milliseconds. New Style For Runtime: 1485 milliseconds. Iterator Runtime: 1656 milliseconds.
As you can see the foor loop with the extra variable is a little faster than the version without the variable. The values.size() call is very cheap so there isn't much difference in timings but when added up across a whole application it's might be worth making the change (as long as it is safe to do so of course). The new style 5.0 for loop is faster than the iterator but I suspect that is due to the cast that is necessary with an iterator. As you can see though both are much more expensive than plain for loops.
So that you can test this yourself the test code is shown below.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class LoopSpeed {
public LoopSpeed() {
// Create a List and populate it with values.
// Tight loops like this are _fast_ so a lot of values are
// needed to show a difference in performance.
List<Integer> values = new ArrayList<Integer>();
for (int i = 0, n = 20000000; i < n; i++) {
values.add(new Integer(i));
}
runTest(values, 10);
}
private void runTest(List<Integer> values, int count) {
for (int i = 0, n = count; i < n; i++) {
System.out.println("------ Run " + i + " ------");
withN(values);
withoutN(values);
newFor(values);
iterator(values);
}
}
private void withN(List<Integer> values) {
long start = System.currentTimeMillis();
long total = 0;
for (int i = 0, n = values.size(); i < n; i++) {
total += values.get(i).intValue();
}
long end = System.currentTimeMillis();
System.out.println("With N Runtime: " + (end - start)
+ " milliseconds.");
}
private void withoutN(List<Integer> values) {
long start = System.currentTimeMillis();
long total = 0;
for (int i = 0; i < values.size(); i++) {
total += values.get(i).intValue();
}
long end = System.currentTimeMillis();
System.out.println("Without N Runtime: " + (end - start)
+ " milliseconds.");
}
private void newFor(List<Integer> values) {
long start = System.currentTimeMillis();
long total = 0;
for (Integer i : values) {
total += i.intValue();
}
long end = System.currentTimeMillis();
System.out.println("New Style For Runtime: " + (end - start)
+ " milliseconds.");
}
private void iterator(List<Integer> values) {
long start = System.currentTimeMillis();
long total = 0;
Iterator it = values.iterator();
while (it.hasNext()) {
total += ((Integer) it.next()).intValue();
}
long end = System.currentTimeMillis();
System.out.println("Iterator Runtime: " + (end - start)
+ " milliseconds.");
}
public static void main(String[] args) {
new LoopSpeed();
}
}