Java For-Loop - Termination Expression speed

Question

In my java program I have a for-loop looking roughly like this:

ArrayList<MyObject> myList = new ArrayList<MyObject>();
putThingsInList(myList);
for (int i = 0; i < myList.size(); i++) { 
     doWhatsoever(); 
}

Since the size of the list isn't changing, I tried to accelerate the loop by replacing the termination expression of the loop with a variable.

My idea was: Since the size of an ArrayList can possibly change while iterating it, the termination expression has to be executed each loop cycle. If I know (but the JVM doesn't), that its size will stay constant, the usage of a variable might speed things up.

ArrayList<MyObject> myList = new ArrayList<MyObject>();
putThingsInList(myList);
int myListSize = myList.size();
for (int i = 0; i < myListSize; i++) { 
     doWhatsoever(); 
}

However, this solution is slower, way slower; also making myListSize final doesn't change anything to that! I mean I could understand, if the speed didn't change at all; because maybe JVM just found out, that the size doesn't change and optimized the code. But why is it slower?

However, I rewrote the program; now the size of the list changes with each cycle: if i%2==0, I remove the last element of the list, else I add one element to the end of the list. So now the myList.size() operation has to be called within each iteration, I guessed.

I don't know if that's actually correct, but still the myList.size() termination expression is faster than using just a variable that remains constant all the time as termination expression...

Any ideas why?

Edit (I'm new here, I hope this is the way, how to do it) My whole test program looks like this:

ArrayList<Integer> myList = new ArrayList<Integer>();
for (int i = 0; i < 1000000; i++)
{
    myList.add(i);
}

final long myListSize = myList.size();
long sum = 0;
long timeStarted = System.nanoTime();
for (int i = 0; i < 500; i++)
{
    for (int j = 0; j < myList.size(); j++)
    {
        sum += j;

        if (j%2==0)
        {
            myList.add(999999);
        }
        else
        {
            myList.remove(999999);
        }
    }
}
long timeNeeded = (System.nanoTime() - timeStarted)/1000000;
System.out.println(timeNeeded);
System.out.println(sum);

Performance of the posted code (average of 10 executions): 4102ms for myList.size() 4230ms for myListSize

Without the if-then-else statements (so with constant myList size) 172ms for myList.size() 329ms for myListSize

So the speed different of both versions is still there. In the version with the if-then-else parts the percentaged differences are of course smaller because a lot of the time is invested for the add and remove operations of the list.

Answer 1

The problem is with this line:

final long myListSize = myList.size();

Change this to an int and lo and behold, running times will be identical. Why? Because comparing an int to a long for every iteration requires a widening conversion of the int, and that takes time.

Note that the difference also largely (but probably not completely) disappears when the code is compiled and optimised, as can be seen from the following JMH benchmark results:

# JMH 1.11.2 (released 7 days ago)
# VM version: JDK 1.8.0_51, VM 25.51-b03
# VM options: <none>
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
...
# Run complete. Total time: 00:02:01

Benchmark                           Mode  Cnt      Score      Error  Units
MyBenchmark.testIntLocalVariable   thrpt   20  81892.018 ±  734.621  ops/s
MyBenchmark.testLongLocalVariable  thrpt   20  74180.774 ± 1289.338  ops/s
MyBenchmark.testMethodInvocation   thrpt   20  82732.317 ±  749.430  ops/s

And here's the benchmark code for it:

public class MyBenchmark {

    @State( Scope.Benchmark)
    public static class Values {
        private final ArrayList<Double> values;

        public Values() {
            this.values = new ArrayList<Double>(10000);
            for (int i = 0; i < 10000; i++) {
                this.values.add(Math.random());
            }
        }
    }

    @Benchmark
    public double testMethodInvocation(Values v) {
        double sum = 0;
        for (int i = 0; i < v.values.size(); i++) {
            sum += v.values.get(i);
        }
        return sum;
    }

    @Benchmark
    public double testIntLocalVariable(Values v) {
        double sum = 0;
        int max = v.values.size();
        for (int i = 0; i < max; i++) {
            sum += v.values.get(i);
        }
        return sum;
    }

    @Benchmark
    public double testLongLocalVariable(Values v) {
        double sum = 0;
        long max = v.values.size();
        for (int i = 0; i < max; i++) {
            sum += v.values.get(i);
        }
        return sum;
    }
}

P.s.:

My idea was: Since the size of an ArrayList can possibly change while iterating it, the termination expression has to be executed each loop cycle. If I know (but the JVM doesn't), that its size will stay constant, the usage of a variable might speed things up.

Your assumption is wrong for two reasons: first of all, the VM can easily determine via escape analysis that the list stored in myList doesn't escape the method (so it's free to allocate it on the stack for example).

More importantly, even if the list was shared between multiple threads, and therefore could potentially be modified from the outside while we run our loop, in the absence of any synchronization it is perfectly valid for the thread running our loop to pretend those changes haven't happened at all.

Answer 2

As always, things are not always what they seem...

First things first, ArrayList.size() doesn't get recomputed on every invocation, only when the proper mutator is invoked. So calling it frequently is quite cheap.

Which of these loops is the fastest?

// array1 and array2 are the same size.
int sum;
for (int i = 0; i < array1.length; i++) {
  sum += array1[i];
}

for (int i = 0; i < array2.length; i++) {
  sum += array2[i];
}

or

int sum;
for (int i = 0; i < array1.length; i++) {
  sum += array1[i];
  sum += array2[i];
}

Instinctively, you would say that the second loop is the fastest since it doesn't iterate twice. However, some optimizations actually cause the first loop to be the fastest depending, for instance, on memory walking strides that cause a lot of memory cache misses.

Side-note: this compiler optimization technique is called loop jamming.

This loop:

int sum;
for (int i = 0; i < 1000000; i++) {
    sum += list.get(i);
}

is not the same as:

// Assume that list.size() == 1000000
int sum;
for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);
}

In the first case, the compile absolutely knows that it must iterate a million times and puts the constant in the Constant Pool, so certain optimizations can take place.

A closer equivalent would be:

int sum;
final int listSize = list.size();
for (int i = 0; i < listSize; i++) {
    sum += list.get(i);
}

but only after the JVM has figured out what the value of listSize is. The final keyword gives the compiler/run-time certain guarantees that can be exploited. If the loop runs long enough, JIT-compiling will kick in, making execution faster.

Answer 3

Because this sparked interest in me I decided to do a quick test:

public class fortest {
    public static void main(String[] args) {
        long mean = 0;
        for (int cnt = 0; cnt < 100000; cnt++) {
            if (mean > 0)
                mean /= 2;

            ArrayList<String> myList = new ArrayList<String>();
            putThingsInList(myList);

            long start = System.nanoTime();


            int myListSize = myList.size();
            for (int i = 0; i < myListSize; i++) doWhatsoever(i, myList);

            long end = System.nanoTime();
            mean += end - start;
        }
        System.out.println("Mean exec: " + mean/2);
    }

    private static void doWhatsoever(int i, ArrayList<String> myList) {
        if (i % 2 == 0)
            myList.set(i, "0");
    }

    private static void putThingsInList(ArrayList<String> myList) {
        for (int i = 0; i < 1000; i++) myList.add(String.valueOf(i));
    }
}

I do not see the kind of behavior you are seeing.

2500ns mean execution time over 100000 iterations with myList.size()

1800ns mean execution time over 100000 iterations with myListSize

I therefore suspect that it's your code that is executed by the functions that is at fault. In the above example you can sometimes see faster execution if you only fill the ArrayList once, because doWhatsoever() will only do something on the first loop. I suspect the rest is being optimized away and significantly drops execution time therefore. You might have a similar case, but without seeing your code it might be close to impossible to figure that one out.

Answer 4

There is another way to speed up the code using for each loop

ArrayList<MyObject> myList = new ArrayList<MyObject>();
putThingsInList(myList);
for (MyObject ob: myList) { 
     doWhatsoever(); 
}

But I agree with @showp1984 that some other part is slowing the code.