3

When writing a for loop, we can write code like:

ArrayList<Object> myList = ...

for(int i=0; i < myList.size(); i++){
    ...
}

This way we are invoking .size() every time. Is it better to get the size in a variable and use that, i.e.

ArrayList<Object> myList = ...

int listSize = myList.size();

for(int i=0; i < listSize ; i++){
    ...
}

And there is another way for iteration, i.e.

for ( Object o : myList) { ... }

Which iteration method should be used for efficient coding pratice?

Thanks

Shafiul
  • 2,832
  • 9
  • 37
  • 55

3 Answers3

3

Check the implementation. Yes it does run in constant time, there is a field that holds the size.

Blub
  • 3,762
  • 1
  • 13
  • 24
3
  1. Yes, size is a constant-time operation.
  2. Since you're using the concrete type ArrayList, the call will almost certainly be inlined by the JIT compiler.
  3. The inlining will also probably open the door for hoisting, so the actual machine code will be exactly as if you manually extracted size into a local variable.
  4. It will almost never actually matter whether it's inlined/hoisted or not.
  5. If your loop runs for at least 100k iterations, does almost nothing in the body, and is the inner loop executed many times over, then it starts making sense to wonder about the performance impact of the size call.
Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
2

The for-each operator should be used whenever possible (that is: whenever you are not modifying the list in between), as it allows the list to choose the most efficient processing mode.

If you must use a for-loop, you can solve the constant checking in a very easy way, by running backwards:

for (int i = list.size()-1; i>= 0; --i)

Edit: As of the comment of Marko Topolnik I wrote a small program to test the efficiency of Iterators and it turned out that the Iterator is actually faster than the index implementation. See here for the code.

This is only true if the JVM has fully optimized that code, as otherwise the Iterator is about 2% slower than the index implementation, but even then this isn't any relevant time for a normal program execution.

TwoThe
  • 13,879
  • 6
  • 30
  • 54
  • or `for (int i = 0, size = list.size(); i < size; i++)`: you typically want to iterate through a list in the forward direction. But that is premature optimization anyway. The size() method will be inlined by the JIT, and calling it at every iteration won't change anything. – JB Nizet Dec 08 '13 at 10:52
  • That is of course possible, but the same like his 2nd statement, just more compact. – TwoThe Dec 08 '13 at 10:53
  • It reduces the scope of the size variable, making it less error-prone. – JB Nizet Dec 08 '13 at 10:55
  • For-each doesn't allow any choice. It uses the Iterator by specification, and the Iterator is not the most efficent processing mode for `ArrayList`. – Marko Topolnik Dec 08 '13 at 11:23
  • @Marko: Your statement is wrong, see [here](http://ideone.com/pAzqki) for a demonstration that Iterator (once optimized) is actually faster. The Iterator does not give _me_ a choice, but the implementation of the list can choose the one which is most optimized. – TwoThe Dec 08 '13 at 12:55
  • That example shows less than 1% difference in speed: that is just *noise*. All you can say is that the two are as fast. However, your statement that "it allows the list to choose the most efficient processing mode" is false: the processing mode is fixed to the *iterator* idiom. If you wanted to say that the implementation can choose the implementation of its iterator, then you should have said just that---this way it's misleading. – Marko Topolnik Dec 08 '13 at 13:01
  • I have reviewed your code: your indexed loop has one iteration less than the iterator loop. – Marko Topolnik Dec 08 '13 at 13:05
  • I have benchmarked your code on my own, but using a proper microbenchmarking tool (`jmh`). These are my results: the indexing idiom is always at an advantage. For your list size (1000) the advantage is slight (10 percent), but for list size 2 it is very large: more than twice as fast. This is consistent with the intuition that the construction of the iterator is an overhead which the indexed approach doesn't suffer from. – Marko Topolnik Dec 08 '13 at 13:21
  • Discussing the correctness of benchmarking in Java will definitely not fit into comments. Nevertheless thanks for testing this with JMH. – TwoThe Dec 08 '13 at 13:43
  • One thing which surely cannot be trusted is the timing of a run on ideone.com. There is no guarantee that the process has all the resources for itself and the opposite is in fact more than likely. – Marko Topolnik Dec 08 '13 at 13:53