Java For-Loop - Termination Expression speed

Question

In my java program, I have a for-loop that looks something 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 does not change, I tried to speed up the loop by replacing the loop termination expression with a variable.

My idea: since the size of an ArrayList can change during iteration, the termination expression should be executed every loop of the loop. If I know (but the JVM does not), its size will remain constant, using a variable can speed up the process.

 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, slower; also makes ending myListSize doesn't change anything! I mean, I could understand if the speed did not change at all; because maybe the JVM just found out that the size does not change or optimize 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 delete the last element of the list, otherwise I will add one element to the end of the list. So, now the operation myList.size() should be called at each iteration, I guessed.

I don’t know if this is really correct, but still the termination expression myList.size() is faster than using only the variable, which remains constant all the time as the termination expression ...

Any ideas why?

Edit (I'm new here, I hope it will be how to do it) The 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); 

Published code performance (average 10 executions): 4102ms for myList.size () 4230ms for myListSize

Without if-then-else instructions (therefore with a constant size of myList) 172ms for myList.size () 329ms for myListSize

Thus, a speed different from both versions still exists. In the version with if-then-else parts, the percentage differences are, of course, less, because a lot of time is invested in the operations of adding and deleting the list.

Answer 1

The problem with this line is:

 final long myListSize = myList.size(); 

Change this to int , and now, the runtime will be the same. What for? Since comparing an int with a long for each iteration requires an extension of the int conversion, and it takes time.

Note that the difference also largely (but probably not completely) disappears when the code is compiled and optimized, as can be seen from the following JMH test 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 is the reference 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; } } 

Ps :.

My idea: since the size of the ArrayList can change the iteration, the termination expression should execute every loop cycle. If I know (but the JVM does not), then its size will remain constant, using a variable can speed up the process.

Your assumption is incorrect for two reasons: firstly, the virtual machine can easily determine, by analyzing the escape, that the list stored in myList will not escape the method (therefore, it can freely allocate it on the stack).

Moreover, even if the list was divided between several threads and therefore can be changed externally while we run our loop, in the absence of any synchronization, it is great for the thread on which our loop is running to pretend that there were no changes at all .

Answer 2

As always, everything is not always what it seems ...

First of all, ArrayList.size() does not receive recalculation with each call, only when the corresponding mutator is called. Therefore, it is often called quite cheap.

Which of these cycles 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 cycle is the fastest, since it does not repeat twice. However, some optimizations actually lead to the fact that the first cycle is the fastest depending on, for example, memory moves that cause many misses in the memory cache.

Side note: this compiler optimization method is called loop jamming.

This loop:

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

- this 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 compiler absolutely knows that it must iterate a million times and puts a constant in the Constant Pool, so there may be certain optimizations.

The closest equivalent will 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 listSize . The final keyword gives the compiler / runtime specific guarantees that can be used. If the loop runs long enough, JIT compilation will start, making execution faster.

Answer 3

Since this aroused my interest, 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 that you see.

2500 ns means an average runtime of more than 100,000 iterations with myList.size ()

1800ns means average run time over 100,000 iterations with myListSize

Therefore, I suspect that this is your code that executes with errors. In the example above, you can sometimes see faster execution if you only populate an ArrayList once, because doWhatsoever() will only do something in the first loop. I suspect the rest is optimized and significantly reduces execution time. You may have a similar case, but without seeing the code, it may be close to impossible to understand that it came out.

Answer 4

There is another way to speed up code usage 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 slows down the code.