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.

Answer 2

I felt my first answer was not satisfactory and really didn't help to explain the question; I had posted the link to this site and elaborated a bit, which covered some basic use cases, but not the nitty-gritty of the issue. So, I went ahead and did a little hands-on research instead.

I ran two separate codes:

    // Code 1
    int i = 0;
    Integer[] array = { 1, 2, 3, 4, 5 };
    for (Integer obj : array) {
        i += obj;
    }
    System.out.println(i);

    // Code 2
    int i = 0;
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (Integer obj : list) {
        i += obj;
    }
    System.out.println(i);

Of course, both print out 15, and both use an Integer array (no ints).

Next, I used javap to disassemble these and look at the bytecode. (I ignored the initialization; everything before the for loop is commented out.) Since those are quite lengthy, I posted them at PasteBin here.

Now, while the bytecode for code 1 is actually longer, it is less intensive. It uses invokevirtual only once (aside from the println), and no other invocations are necessary. In code 1, it seems to optimize the iteration to a basic loop; checking the array length, and loading into our variable, then adding to i. This appears to be optimized to behave exactly as for (int i = 0; i < array.length; i++) { ... }.

Now, in code 2, the bytecode gets much more intensive. It has to make 2 invokeinterface calls (both to Iterator) in addition to every other call that is needed above. Additionally, code 2 has to call checkcast because it is a generic Iterator (which is not optimized, as I mentioned above). Now, despite the fact that there are less calls to load and store operations, these aforementioned calls involve a substantial amount more overhead.

As he says in the video, if you find yourself needing to do a lot of these, you may run into problems. Running one at the start of an Activity, for example, probably is not too big a deal. Just beware creating many of them, especially iterating in onDraw, for example.

Answer 3

I guess that the compiler optimizes (3) to this (this is the part where I'm guessing):

for (int i =0; i < array.length; ++i)
{
    Type obj = array[i];

}

And (7) can't be optimized, since the compiler doesn't know what kind of Iterable it is. Which means that it really has to create a new Iterator on the heap. Allocating memory is expensive. And every time you ask for the next object, it goes trough some calls.

To give a rough sketch of what is happens when (7) gets compiled (sure about this):

Iterable<Type> iterable = get_iterable();
Iterator<Type> it = iterable.iterator(); // new object on the heap
while (it.hasNext()) // method call, some pushing and popping to the stack
{
    Type obj = it.next(); // method call, again pushing and popping


}

Answer 4

I guess you have to marshall the objects into a "linked list" based Iterator, and then support an API, as opposed to a chunk of memory and a pointer (array)

Answer 5

Third variant is faster then 7 because array is reified type and JVM should just assign a pointer to a correct value. But when you iterate over a collection , then compiler can perform additional casts because of erasure. Actually compiler insert this casts to generic code to determine some dirty hacks like using deprecated raw types as soon as possible.

P.S. This is just a guess. In fact, I think that the compiler and JIT compiler can perform any optimisation (JIT even in runtime) and result can depend on particular details like JVM version and vendor.

Answer 6

In case of Android, this is the video from Google Developers in 2015.

To Index or Iterate? (Android Performance Patterns Season 2 ep6) https://www.youtube.com/watch?v=MZOf3pOAM6A

They did the test on DALVIK runtime, 4.4.4 build, 10 times, to got average results. The result shows "For index" is the best.

int size = list.size();
for (int index = 0; index < size; index++) {
    Object object = list.get(index);
    ...
}

They also suggest to do similar test by yourself on your platform at the end of the video.