Efficient loop through Java List

Question

The following list is from the google I/O talk in 2008 called "Dalvik Virtual Machine Internals" its a list of ways to loop over a set of objects in order from most to least efficient:

(1) for (int i = initializer; i >=0; i--) //hard to loop backwards
(2) int limit = calculate_limit(); for (int i= 0; i< limit; i++)
(3) Type[] array = get_array(); for (Type obj : array)
(4) for (int i =0; i< array.length; i++) //gets array.length everytime
(5) for (int i=0; i < this.var; i++) //has to calculate what this.var is
(6) for (int i=0; i < obj.size(); i++) //even worse calls function  each time
(7) Iterable list = get_list(); for (Type obj : list) //generic object based iterators slow!

The first 3 are in the same territory of efficiency, avoid 7 if possible. This is mainly advice to help battery life but could potentially help java SE code too.

My question is: why (7) is slow and why (3) is good? I thought it might be the difference between Array and List for (3) and (7). Also, as Dan mentioned (7) creates loads of small temporary objects which have to be GCed, I'm a bit rusty on Java nowadays, can someone explain why? It's in his talk video at 0:41:10 for a minute.

Answer 1

This list is a bit outdated, and shouldn't be really useful today.

It was a good reference some years ago, when Android devices were slow and had very limited resources. The Dalvik VM implementation also lacked a lot of optimizations available today.

On such devices, a simple garbage collection easily took 1 or 2 seconds (for comparison, it takes around 20ms on most devices today). During the GC, the device just freezed, so the developers had to be very careful about memory consumption.

You shouldn't have to worry too much about that today, but if you really care about performance, here are some details :

(1) for (int i = initializer; i >= 0; i--) //hard to loop backwards
(2) int limit = calculate_limit(); for (int i=0; i < limit; i++)
(3) Type[] array = get_array(); for (Type obj : array)

These ones are easy to understand. i >= 0 is faster to evaluate than i < limit because it doesn't read the value of a variable before doing the comparison. It works directly with an integer literal, which is faster.

I don't know why (3) should be slower than (2). The compiler should produce the same loop as (2), but maybe the Dalvik VM didn't optimize it correctly at this time.

(4) for (int i=0; i < array.length; i++) //gets array.length everytime
(5) for (int i=0; i < this.var; i++) //has to calculate what this.var is
(6) for (int i=0; i < obj.size(); i++) //even worse calls function  each time

These ones are already explained in the comments.

(7) Iterable list = get_list(); for (Type obj : list)

Iterables are slow because they allocate memory, do some error handling, call multiple methods internally, ... All of this is much slower than (6) which does only a single function call on each iteration.