To Index or Iterate

The dark side of the Moon

Some time ago I watched Colt McAnlis video from Performance Patterns video list about choice between indexing or iterating. I know, I know. It’s been a while since it was published in May 2015, but I discovered “Performance Patterns” series only recently. And I want to share my thoughts about problem of choice between readability and performance.

Video about loops performance

Make it work, make it right, make it fast

In order to proceed with the next measurements and conclusions I want you to know, that I try to keep in mind next slightly modified directive “First, make code work, then make it right, then make it fast…if it isn’t fast enough”. Original expression ascribed to Kent Beck. But the ending I took from Joshua Bloch’s book ‘Concurrency in Practice’. I like it. Last part of this sentence tells us that we should care about performance only if it time to do that.

So now let’s come back to the video. When I saw part with benchmark results, I suspected that something is wrong here. Why index is almost 2 times faster than foreach. I red Effective Java and Joshua Bloch convinced me that foreach is best practice and in terms of performance the difference between index and foreach is negligible. What’s wrong with that I thought and dived into google. My search led me to next links: here, here and here.

I was not alone. Many other developers shared my position. So how it was possible? As Colt McAnlis suggested in his ‘episode 6’: “Always verify your assumptions”. So let’s verify them.

Naive tests

Pure Java

First, let’s write some simple test to check how all three loops will work in terms of some simple task. For example, I have some pack of random strings and I want to concatenate them. I go through my list of strings and just add them to output string object.

We start with simple unit test that measures time performance of all three loops (index, foreach and iterator) for simple concatenation of all strings in given ArrayList. We will increase count of strings from 0 to 30K with step 1K and will measure execution time of all three loops for each step. Also we will generate each string as String.valueof(rnd.nextInt()) where rnd is instance of Random.class. You can find it here (please, don’t look at bad code, main task is just to measure time). In addition, we will measure each loop performance of each step exactly 15 times. And result will be average number of measurements. Now let’s see our results.

A graph of execution time of loops by given input strings count

As we see here Iterator failing in a relation to other loops. But why? Let’s look in more details at one of the iterations. Just grab step for 16K string and see graph of attempts.

A graph of execution time of loops for 16K strings clustered by attempts

So through this graph it is now clear for us, that in the beginning all three loops are quite same. But then the JIT compiler comes and optimizes foreach and index loops for us. Thus, iterator loop starts to lose ground.

Android

Okey, okey, that was a pure java. Let’s see, what situation comes in Android. Let’s run our test on Google Nexus 4 Genymotion Emulator with API 19. We will slightly change max 30K strings to 10K strings. Also we will reduce 15 attempts to 5 attempts. You can find test here.

A graph of execution time of loops by given input strings count

And also let’s see graph of attempts for step with 6K strings.

A graph of execution time of loops for 6K strings clustered by attempts

As we see here no JIT, no optimizations, pain and hell. So how it could be? How test in video was so different from what we received? Why even despite android performance tips about using loops we have such interesting results in video.

Only loops test

The answer is that in video only iterating through loop was tested. So let’s go back to the video and fulfill all test conditions:

• running Android One device — I don’t have one, but I will test it in Google Nexus 4 emulator;
• lists contain 400K random integers — I will allow myself to test it on 4M random integers
• list is walked 10 times — okey
• min & max times are through out — okey

You can find source code of this test here.

A graph of execution time of loops for 4M integers clustered by attempts

And in this time we still have almost same outcome indicators. So why? If we will closer look, we will see that we did not get list size before index loop, but get it for every time the boundary condition is invoked, so let’s replace:

for (int i = 0; i < integers.size(); i++) {
    Object object = integers.get(i);
    //...
}

with:

int size = integers.size();
for (int i = 0; i < size; i++) {
    Object object = integers.get(i);
    //...
}

And voila, we have similar results as in video:

For index loop is working almost 2 times faster compare to for each loop and for iterator loop. But it is for 4M items and we only iterate through them nothing more. And we have difference in 50 milliseconds approximately. Considering that in real life we will use much much less items, I suspect that using for index loop with predeclared list size is a micro-optimization of your application.

Of course it depends on the circumstances. For example, in View.onDraw you should not use iterators, because every time you wanted to go through list, new iterator is created. Or another example, somehow in your life you using LinkedList. So here you will lose pretty much amount of time if will consider to apply for index loop on it (so for each loop is your friend here). And final example is when you want to modify your collection, when going through it. Assume you want to delete some items. Then Iterator is your best friend. All depends on the circumstances.

Conclusion

I want to thank Colt McAnlis for his video (and all episodes). These videos don’t let you always sacrifice performance for the sake of readability or stability. But we should always think and balance between readability and performance. We should always think about our teammates and our code agreements. And we should optimise something only when it time to do that and there are no more necessary optimizations. My personal opinion is that replacing for each loop to for index loop is an micro-optimization in most of the cases. Again, it all depends on circumstances.

I think that phrase “First, make code work, then make it right, then make it fast…if it isn’t fast enough” is one of the best helpers in that situations (situations with micro-optimizations).

P.S.: Android 7.0 adds JIT compiler, so now it returns back and operates in conjunction with ART compiler. So I hope that in future android JIT compiler will be able to optimise foreach loops in some cases to for index loop and for index loop to for index loop with predeclared list size, when it will be possible.