Java Benchmark Adventures - ArrayList vs LinkedList

Classic interview question:

"What is the complexity of ArrayList vs LinkedList?"

Usually answered with something along the lines of:

"Removing items from LinkedList is O(1) while ..."

And that's probably it, however, this doesn't reflect the actual performance of them, and it may lead to a substantial slow down in your code.

But before we get to that, let's discuss some important implementation details for ArrayList and LinkedList in Java. Keep those in mind when looking at the benchmark results.

The Implementation Details

ArrayList

• It uses primitive array underneath to store values,
• Primitive array is stored as a continuous chunk of memory.

LinkedList

• Each element holds value and reference to next and previous element,
• It holds references to both first and last element of the list,
• It optimizes get by index: if the index is less than half the size, start from the beginning, else start from the end,
• Elements are scattered around the memory.

The Benchmark

You can see the code for the benchmark in this repo. I used objects instead of usual integer just to have something looking a bit more like a real world example, and I used JMH for benchmark.

Test cases are what you would expect in a normal project:

• findByReference
• getByKnownIndex
• iterateOver
• removeByKnownIndex
• removeByReference
• addFirst
• addInTheMiddle
• addLast
• removeFirst
• removeInTheMiddle
• removeLast

The benchmark creates 2 Lists with 1 million objects each, LinkedList and ArrayList, we also store reference to one of the objects in each List, from around the middle.

My laptop is IdeaPad Gaming 3 15IMH05 with Intel i7-10750H (12) @ 5.000GHz and 32GB of RAM. I run Azul Zulu 17.0.6 Java.

So, what are the results? On my laptop they came to:

Benchmark                             Score          Error  Units
arrayList_findByReference       2696499.728 ±    32202.502  ns/op
linkedList_findByReference      7028258.295 ±   411854.774  ns/op
arrayList_getByKnownIndex             1.355 ±        0.020  ns/op
linkedList_getByKnownIndex     14109357.750 ±  4523485.134  ns/op
arrayList_iterateOver           4241855.707 ±    51949.429  ns/op
linkedList_iterateOver         18701734.963 ±   153427.714  ns/op
arrayList_removeByKnownIndex      23807.499 ±    22832.530  ns/op
linkedList_removeByKnownIndex  13611894.721 ±   415849.451  ns/op
arrayList_removeByReference     5446367.115 ±   116991.612  ns/op
linkedList_removeByReference   13715672.076 ±  1153278.238  ns/op
arrayList_addFirst              3220312.800 ±   428670.631  ns/op
linkedList_addFirst                8515.000 ±    24870.360  ns/op
arrayList_addInTheMiddle         815357.800 ±   282617.391  ns/op
linkedList_addInTheMiddle     142979327.200 ± 18151974.063  ns/op
arrayList_addLast                  4606.600 ±    23419.256  ns/op
linkedList_addLast                 1620.400 ±      680.293  ns/op
arrayList_removeFirst           1933858.000 ±   127364.646  ns/op
linkedList_removeFirst             5216.600 ±      713.334  ns/op
arrayList_removeInTheMiddle      824331.600 ±    53493.129  ns/op
linkedList_removeInTheMiddle  143313481.400 ± 34759711.042  ns/op
arrayList_removeLast               3943.600 ±      834.749  ns/op
linkedList_removeLast              5973.800 ±      972.878  ns/op

As we can see, in only 2 of them the ArrayList was clearly slower than LinkedList, and it was only cases at the start of the List. It was similar at the end, and in all others it was at least few times faster.

You might say: "wait, but that's not what the Big O Notation says, LinkedList should be faster in deletions and inserts", and you would be right, that's exactly what it says.

So, where does the performance hit come from?

The Reason

The Big O

The O(1) for deletion doesn't count finding the element you need to delete. Yes, the operation itself is just moving around few references, but you need to find the object first. Some articles, like this one, actually take this into consideration, however, some don't.

Overall, you need to be aware that removing references is just part of the algorithm for deletion, if you include searching, then you will come to correct O(n) value for elements in the middle of the List.

As for the last element: the performance for ArrayList and LinkedList is pretty much the same, because Java implementation of LinkedList holds references to both beginning and end by default. If, for some reason, you would use LinkedList without the back reference, you would need to iterate over the entire list to get to the last element.

However, that's still not everything.

The CPU and Caches

You've probably heard that CPU has Caches - L1, L2, L3 and sometimes even L4, then there is RAM and finally disk. It looks (in great simplification) like this:

When you want to access some data in your program, like iterate over an array of elements, it is loaded into the CPU Cache for quick access. The arrows on the diagram show order in which the caches are checked for the data, if it's found in L1, great, if not go check L2 and so on, until finally it checks the disk.

What helps with loading data into caches is Cache Prefetching, but that in itself is not important for us.

The important bit of information is this: the prefetching is optimized for continuous memory access, so that it can load entire array at once, if it fits into to the cache.

Focus on the word: continuous.

Array is stored as continuous block of memory, and CPU is optimized for continuous memory access.

Here is another important piece of knowledge: accessing RAM can be 10 to 100 times slower than accessing cache.

That's the whole trick.

Since LinkedList can be randomly scattered around memory, there is no way to load it into the cache at once. You need to first get an element and check the reference of next one before you can get it. Each element has to be accessed separately, 10 to 100 times slower than the elements in ArrayList.

That is the reason for performance difference.

Is LinkedList useless then?

No. There are cases where LinkedList would be better. From the top of my head: double-ended linked list can be used as a queue with unknown number of elements, in fact a Deque is exactly that. Thanks to having references to both beginning and end, you add elements at the end, and remove at the front with the performance promised by Big O notation.

Summary

The biggest lesson here, at least for me, is to remember that the programs we write are executed by the CPU, and we should not forget that. Understanding what happens in the CPU, even generally, can be very valuable. I might not know how the prefetching works, but it's enough to know how it affects my program.

The other take from this is that ArrayList should be used pretty much everywhere by default, unless you have specific requirements that would benefit from LinkedList.

Hope you found this article useful :)