Comparing Apex Loops and why Iterators are dramatically slower than for loops?

Question

I decided to use iterators to work with collections in a functional style at some point in development, but immediately noticed a CPU time performance drawdown. So I decided to do a simple performance test of different iterating approaches by getting each element and adding it into a new list (to eliminate possible dead code):

List<String> strings = new List<String>();
for (Integer i = 0; i < 50000; i++) {
    strings.add('');
}
Iterator<String> iterator = strings.iterator();
List<String> strs = new List<String>();

// Start measuring
Integer start = Limits.getCpuTime();
/*
// optimized indexed for loop
for (Integer i = 0, size = strings.size(); i < size; i++) strs.add(strings[i]);
// indexed for loop
for (Integer i = 0; i < strings.size(); i++) strs.add(strings[i]);
// indexed get for loop
for (Integer i = 0; i < strings.size(); i++) strs.add(strings.get(i));
// for each loop
for (String s : strings) strs.add(s);
// iterator for loop
for (;iterator.hasNext();) strs.add(iterator.next());
// iterator while loop
while (iterator.hasNext()) strs.add(iterator.next());
*/
// End measuring
Integer duration = (Limits.getCpuTime() - start);
System.debug(LoggingLevel.INFO, duration);

Results for 50 trials each of 50.000 iterations:

Loop	AVG CPU (ms)	STD (σ)
optimized indexed for	136.00	16.03
indexed for	230.50	26.62
indexed get for	287.60	30.00
for each	282.60	27.30
iterator for / iterator while	1163.00	77.65

I am aware that results depend on many factors and may vary, and I also know that adding an element to a list also consumes some CPU time. But the relative results speak for themselves. I've also tested the same loops in JAVA but the results did not differ as much from each other as in APEX. It turns out that iterating through collections using an iterator is several times slower than using for loops, which negates all its usefulness in similar scenarios.

Questions:

1. Why is iterating through collections with an iterator SO slow or what I'm missing?
2. Is there a way to speed up or optimize iterators somehow when it comes to getting every single element of collection? (Custom / [Lazy] iterators are even slower)

Answer 1

Looking at the code posted above, we understand that, Apex List is implemented as ArrayList which allows RandomAccess. Therefore it suffers from the same performance issue that Java suffers when iterating random access lists.

Refer the Interface RandomAccess

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

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

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

This interface is a member of the Java Collections Framework.