A while back when I was looking into different implementations for a queue in Java, I was reading the java docs for ArrayDeque. I had been used to using a LinkedList when a queue is needed prior to reading the comment:
This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
Since then I have been using ArrayDeque as my implementation for a queue but it had me thinking, how much faster is it to use an ArrayDeque instead of a LinkedList for a queue? Are we talking about milliseconds or nanoseconds? Is ArrayDeque always faster at the same percentage?
What is the Difference?
LinkedList in Java is basically a doubly Linked List (a very profound statement, I know…). There is some extra baggage that comes along with linked list that can make it expensive: using memory to hold objects and to contain ‘links’ that point to other objects, related objects in non-contiguous memory (which slows down iteration), etc.
So why is the ArrayDeque much faster? First of all, it removes the need for extra memory used to create a ‘link’ that points to other objects. An ArrayDeque is backed by a circular array (hopefully that was obvious by the name), so all objects are ordered next to each other in the array. The objects sitting contiguously in memory also helps out in cache hits as well.
To test this I wrote up a simple Java application. I have a link to the code here, but here is an overview of the test setup:
- Prior to each test being run, an array with a set number of objects is created prior to calculating how long each test took.
- Each test object is a 500 character String. Each String is a different object in memory.
- The size of the test array will be varied during the tests.
- For each array size/Queue-implementation combination, 100 tests are run and average time-per-test is calculated.
- Each tests consists of filling each queue with all objects, then removing them all.
- Measure time in terms of milliseconds.
The result of “ArrayDeque is faster than LinkedList” isn’t really surprising. Here are some results worth noting though:
- Below 10,000 elements, both LinkedList and ArrayDeque tests averaged at a sub 1 ms level.
- As the sets of data get larger, the differences between the ArrayDeque and LinkedList average test time gets larger.
- At the test size of 9,900,000 elements, the LinkedList approach took ~165% longer than the ArrayDeque approach.
Here is the results graph for the average:
So in conclusion… yep, ArrayDeque is faster!
Also, as the amount of elements increase, the difference in performance grows in favor as the ArrayDeque as well.