13

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:

enter image description here

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.

Roman Petrenko
  • 1,052
  • 1
  • 9
  • 21
  • 2
    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. – assylias Jun 11 '13 at 11:21
  • 2
    Running java with `-XX:LogCompilation` will log JIT optimizations and you might notice some differences. – Grzegorz Żur Jun 11 '13 at 11:25
  • 1
    BTW Gb = Giga-bit, GB = Giga-Byte. – Peter Lawrey Jun 11 '13 at 11:34
  • See also the answers to this question: [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Daniel Pryden Jun 12 '13 at 07:03

2 Answers2

3

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • I tried to switch the order of tests, it shows almost same results – Roman Petrenko Jun 11 '13 at 11:24
  • 1
    Did you ignore the first run, by that JVM i.e. without restarting? – Peter Lawrey Jun 11 '13 at 11:25
  • 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 – Roman Petrenko Jun 11 '13 at 11:32
  • 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. – Peter Lawrey Jun 11 '13 at 11:33
  • 1
    @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. ;) – Peter Lawrey Jun 11 '13 at 11:41
  • 2
    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. – Peter Lawrey Jun 11 '13 at 11:45
  • 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. – assylias Jun 11 '13 at 12:19
  • @PeterLawrey can you provide an article or something about "code will be optimised based on the usage in the warmup"? – treaz Jun 11 '13 at 12:48
  • @treaz 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 http://vanillajava.blogspot.com/2012/12/performance-of-inlined-virtual-method.html – Peter Lawrey Jun 11 '13 at 13:54
1

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

Evgeniy Dorofeev
  • 133,369
  • 30
  • 199
  • 275
  • 1
    Although when only one implementation is used the JVM should optimise the call optimistically. – assylias Jun 11 '13 at 11:38
  • 1
    -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. – Peter Lawrey Jun 11 '13 at 11:46
  • @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 – Roman Petrenko Jun 11 '13 at 11:55
  • @RomanPetrenko I suspect you don't have exactly the same version of Java either. ;) – Peter Lawrey Jun 11 '13 at 12:02