Why ArrayList performance differs if it is referenced as List?

Question

It was mentioned in the kjellkod's article that if we pass ArrayList in the method which receives List as an argument, then we lose in performance because ArrayList implements additional RandomAccess interface. Example from article:

// SLOWER: as shown in http://ideone.com/1wnF1
private static void linearInsertion(Integer[] intArray, List<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

// FASTER: as shown in http://ideone.com/JOJ05
private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

From reference:

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.

However, if we really pass ArrayList in the above methods and check list instanceof RandomAccess, it will be true in both cases. So, my first question is why the Java VM should interpret this as a sequential list in the first method?

I have modified tests from article to check this behavior on my machine. When test is ran on the ideone, it shows results similar to kjellkod's. But when I ran it locally, I got unexpected results, which are contrary to article explanation as well as to my understanding. It seems that in my case ArrayList as List iteration is 5-25% faster than referencing it as an ArrayList:

How can this difference be explained? Does it depend on architecture or number of processor cores? My working machine configuration is Windows 7 Professional x64, Intel Core i5-3470 (4 cores, 4 threads), 16 GB RAM.

Tingley

This article does not make sense to me... When you iterate over a list, the method called is that of the specific implementation used, not a random inefficient implementation. – Reptant

Running java with -XX:LogCompilation will log JIT optimizations and you might notice some differences. – Dysfunction

BTW Gb = Giga-bit, GB = Giga-Byte. – Cammack

See also the answers to this question: How do I write a correct micro-benchmark in Java? – Melinite

Answer 1

So, my first question is why the Java VM should interpret this as a sequential list in the first method?

The JVM has no concept of sequential or random access lists. (Apart from the marker interface) It is the developer of the implementation which recognises that ArrayList perform random access lookups in O(1) time instead of O(n) time.

Does it depend on architecture or number of processor cores?

No, you will see a difference between -client e.g. 32-bit Windows and -server e.g. any 64-bit JVM.

---

I suspect you ran the List test second. This is likely to be faster as the code is more warned up both in the JIT as well as the CPU cache. I suggest you perform each test at least three times, running your longest tests first and ignore the first run you do.

Note: contains() is O(n) for a List which is why your timings grow O(n^2) Obviously you wouldn't use a List if you wanted to ignore duplicates and looking at the behaviour of really inefficient code can be confusing as you are very susceptible to the subtleties of what gets optimised and what doesn't. You will get much more meaningful results from comparing code which is already reasonably optimal.

Cammack

I tried to switch the order of tests, it shows almost same results – Tingley

Did you ignore the first run, by that JVM i.e. without restarting? – Cammack

Yes, I tried to do so. Also, in my tests (as well as in the original article) there is a "warm up" section before running actual tests – Tingley

Since you are ignoring duplicates I suggest you try using a Set instead. When you have really inefficient code, you can get odd results because you are very sensitive to an extra machine code instruction here or there. You get much more consistent results from efficient code. – Cammack

@RomanPetrenko So you are very dependent on how ArrayList.contains() gets optimised for an Integer type. The actual calls you make are not important. Try using another type like Long as a extra tests and you might see that Integer becomes slower after wards. ;) – Cammack

If you have a warmup, the code will be optimised based on the usage in the warmup. This means the order you warm up code can matter. – Cammack

Interestingly the JIT code is not exactly the same and the arraylist version seems to always run slightly slower on hotspot 7 (32ms vs 34ms on average). Not sure why to be honest. – Reptant

@PeterLawrey can you provide an article or something about "code will be optimised based on the usage in the warmup"? – Swelter

@Swelter This is what dynamic compilation means to me. Here is an article I wrote which shows the number of methods actually called at a site changes the performance vanillajava.blogspot.com/2012/12/… – Cammack

Answer 2

Though the code is the same in both methods still theoretically there may be a difference because at JVM level invoking an interface method is different than invoking a class method. They are 2 different bytecode operations: invokeinterface and invokevirtual. See http://bobah.net/d4d/source-code/misc/invokevirtual-vs-invokeinterface-performance-benchmark

Sian

Although when only one implementation is used the JVM should optimise the call optimistically. – Reptant

-1 invokeinterface should always be slower if there is is any difference as it has to do more work. This is what your link also claims. The difference the OP see is that it is faster. i.e. the behaviour the OP sees is the opposite of your answer. – Cammack

@PeterLawrey Actually, it seems that the difference depends on working machine, because my computer shows better performance when using List and ideone shows the opposite result – Tingley

@RomanPetrenko I suspect you don't have exactly the same version of Java either. ;) – Cammack