Clean and performant way for iterating over an ArrayList

Question

First of all, note that there already are lots of similar questions on stackoverflow, e.g. this, this, this. However, I'd like to highlight another aspect of the problem, I don't see answered in these discussions:

Performing a benchmark of three variants of iterating over an ArrayList (specifically ArrayList, not other List implementations):

Variant No. 1:

int size = list.size();
for(int i = 0; i < size; i++)
    doSomething(list.get(i));

Variant No. 2:

for(Object element : list)
    doSomething(element);

Variant No. 3:

list.forEach(this::doSomething);

It turns out that on my machine No. 1 and No. 3 perform equally, while No. 2 takes about 55% longer. This confirms the intuition, that the Iterator created implicitly in No. 2 does more work during each iteration, than the traditional loop over an array (for which there are decades of compiler optimization research). Variant No. 3 of course does the same loop as No. 1 internally.

Now my actual question: Assuming that variant No. 3 is not applicable for some reason (side effects in the loop or no Java 8), what is the cleanest way of looping over a List in Java? As mentioned in this discussion, variant No. 1 is likely much less efficient for other Lists than ArrayList. Keeping this in mind, we could do something like this:

if(list instanceof ArrayList)
    doVariant1(list);
else
    doVariant2(list);

Unfortunately this rather smells like introducing boilerplate code. So, what would you recommend as a clean, as well as performant solution for iterating over a List?

EDIT: Here is the entire code for those wanting to reproduce the results. I am using JRE 1.8.0, JavaHotspot Sever VM build 25.0-b70 on MacOS 10 with 2 GHz Intel Core i7.

private static final int ARRAY_SIZE = 10_000_000;
private static final int WARMUP_COUNT = 100;
private static final int TEST_COUNT = 100 + (int)(Math.random() + 20);

public void benchmark()
{
    for(int i = 0; i < WARMUP_COUNT; i++)
        test();
    long totalTime = 0;
    for(int i = 0; i < TEST_COUNT; i++)
        totalTime += test();
    System.out.println(totalTime / TEST_COUNT);
}

private long test()
{
    ArrayList<Object> list = new ArrayList<>(ARRAY_SIZE);
    for(int i = 0; i < ARRAY_SIZE; i++)
        list.add(null);
    long t = System.nanoTime();
    doLoop(list);
    return System.nanoTime() - t;
}

private void doLoop(ArrayList<Object> list)
{   // replace with the variant to test.
    for(Object element : list)
        doSomething(element);
}

private void doSomething(Object element)
{
    Objects.nonNull(element);
}

Answer 1

1. Your "black hole" method doSomething, which should make use of the values iterated over, does nothing and becomes an easy target for the Dead Code Elimination optimization. When I tried to reproduce your result, I got just 125 nanoseconds per run in the case of indexedFor, compared to 3-6 milliseconds in the other two cases.

2. After that is fixed (by incrementing a static int counter and printing it in the end), the "enhanced for" variant is twice slower than the other two and the general range is 5-9 milliseconds per run. To keep things in perspective, this is 0.5-0.9 nanoseconds per element.

3. The relevance of your test is virtually none because it attempts to measure the pure overhead of iteration without actually doing anything with the elements. There are in fact no elements, just nulls.

4. If we use modified code as presented below, which does the least possible work per element (dereference its int field and add it to the counter), the differences in speed almost disappear: 9.5 ms for "enhanced for" vs. 8 ms for the other two cases. It is next to impossible to write a useful program where that difference would actually matter.

In conclusion: no recommendations for the "best idiom" will come out of this. Choose the idiom which satisfies some other criteria, like readability and simplicity. Indexed for-loop is the most complex one due to the extra i variable and checking needed to ensure you're dealing with an implementation that actually benefits from it.

---

private static final int ARRAY_SIZE = 10_000_000;
private static final int WARMUP_COUNT = 100;
private static final int TEST_COUNT = 100 + (int)(Math.random() + 20);

private static int counter;

public static void benchmark() {
    for (int i = 0; i < WARMUP_COUNT; i++)
        test();
    long totalTime = 0;
    for (int i = 0; i < TEST_COUNT; i++)
        totalTime += test();
    System.out.println(totalTime / TEST_COUNT);
    System.out.println("Nonnull count: " + counter);
}

private static long test() {
    final ArrayList<Integer> list = new ArrayList<>(ARRAY_SIZE);
    for (int i = 0; i < ARRAY_SIZE; i++)
        list.add(i % 256 - 128);
    final long start = System.nanoTime();
    forEach(list);
    return System.nanoTime() - start;
}

private static void indexedFor(ArrayList<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        doSomething(list.get(i));
    }
}

private static void enhancedFor(ArrayList<Integer> list) {
    for (Integer element : list)
        doSomething(element);
}

private static void forEach(ArrayList<Integer> list) {
    list.forEach(Testing::doSomething);
}

private static void doSomething(Integer element) {
    counter += element.intValue();
}

public static void main(String[] args) {
    benchmark();
}

Answer 2

Do you really need such micro performance? Because you are asking for "the cleanest" way, 2) and (3) are the best. Also, (2) and (3) have better performance overall since the concrete class will provide its own most suitable Iterator and that is usually the best one.

(2) has good performance for array-based List, but bad for other (e.g. LinkedList). However, even with ArrayList, most real world applications won't see much difference in performance between (1) and (2)/(3) because most of CPU time will be spent on doSomething() not looping the list.