Why does ArrayList seriously outperform LinkedList?

Question

I did some research and wrote the following article: http://www.heavyweightsoftware.com/blog/linkedlist-vs-arraylist/ and wanted to post a question here.

class ListPerformanceSpec extends Specification {
    def "Throwaway"() {
        given: "A Linked List"
        List<Integer> list
        List<Integer> results = new LinkedList<>()

        when: "Adding numbers"
        Random random = new Random()
        //test each list 100 times
        for (int ix = 0; ix < 100; ++ix) {
            list = new LinkedList<>()
            LocalDateTime start = LocalDateTime.now()

            for (int jx = 0; jx < 100000; ++jx) {
                list.add(random.nextInt())
            }

            LocalDateTime end = LocalDateTime.now()
            long diff = start.until(end, ChronoUnit.MILLIS)
            results.add(diff)
        }

        then: "Should be equal"
        true
    }

    def "Linked list"() {
        given: "A Linked List"
        List<Integer> list
        List<Integer> results = new LinkedList<>()

        when: "Adding numbers"
        Random random = new Random()
        //test each list 100 times
        for (int ix = 0; ix < 100; ++ix) {
            list = new LinkedList<>()
            LocalDateTime start = LocalDateTime.now()

            for (int jx = 0; jx < 100000; ++jx) {
                list.add(random.nextInt())
            }

            long total = 0

            for (int jx = 0; jx < 10000; ++jx) {
                for (Integer num : list) {
                    total += num
                }
                total = 0
            }

            LocalDateTime end = LocalDateTime.now()
            long diff = start.until(end, ChronoUnit.MILLIS)
            results.add(diff)
        }

        then: "Should be equal"
        System.out.println("Linked list:" + results.toString())
        true
    }

    def "Array list"() {
        given: "A Linked List"
        List<Integer> list
        List<Integer> results = new LinkedList<>()

        when: "Adding numbers"
        Random random = new Random()
        //test each list 100 times
        for (int ix = 0; ix < 100; ++ix) {
            list = new ArrayList<>()
            LocalDateTime start = LocalDateTime.now()

            for (int jx = 0; jx < 100000; ++jx) {
                list.add(random.nextInt())
            }

            long total = 0

            for (int jx = 0; jx < 10000; ++jx) {
                for (Integer num : list) {
                    total += num
                }
                total = 0
            }

            LocalDateTime end = LocalDateTime.now()
            long diff = start.until(end, ChronoUnit.MILLIS)
            results.add(diff)
        }

        then: "Should be equal"
        System.out.println("Array list:" + results.toString())
        true
    }

}

Why does ArrayList outperform LinkedList by 28% for sequential access when LinkedList should be faster?

My question is different from When to use LinkedList over ArrayList? because I'm not asking when to choose it, but why it's faster.

Answer 1

Array-based lists, as Java ArrayList, use much less memory for the same data amount than link-based lists (LinkedList), and this memory is organized sequentially. This essentially decreases CPU cache trashing with side data. As soon as access to RAM requires 10-20 times more delay than L1/L2 cache access, this is causing sufficient time difference.

You can read more about these cache issues in books like this one, or similar resources.

OTOH, link-based lists outperform array-based ones in operation like insering to middle of list or deleting there.

For a solution that have both memory economy (so, fast iterating) and fast inserting/deleting, one should look at combined approaches, as in-memory B⁺-trees, or array of array lists with proportionally increased sizes.

Answer 2

Why does ArrayList outperform LinkedList by 28% for sequential access when LinkedList should be faster?

You're assuming that, but don't provide anything to back it up. But it's not really a great surprise. An ArrayList has an array as the underlying data store. Accessing this sequentially is extremely fast, because you know exactly where every element is going to be. The only slowdown comes when the array grows beyond a certain size and needs to be expanded, but that can be optimised.

The real answer would probably be: check the Java source code, and compare the implementations of ArrayList and LinkedList.

Answer 3

From LinkedList source code:

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

From ArrayList source code:

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

 private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

So linked list has to create new node for each element added, while array list does not. ArrayList does not reallocate/resize for each new element, so most of time array list simply set object in array and increment size, while linked list does much more work.

You also commented:

When I wrote a linked list in college, I allocated blocks at a time and then farmed them out.

I do not think this would work in Java. You cannot do pointer tricks in Java, so you would have to allocate a lot of small arrays, or create empty nodes ahead. In both cases overhead would probably be a bit higher.

Answer 4

One explanation is that your base assumption (that multiplication is slower than memory fetches) is questionable.

Based on this document, a AMD Bulldozer takes 1 clock cycles to perform a 64 bit integer multiply instruction (register x register) with 6 cycles of latency¹. By contrast, a memory to register load takes 1 clock cycle with 4 cycles of latency. But that assumes that you get a cache hit for the memory fetch. If you get a cache miss, you need to add a number of cycles. (20 clock cycles for an L2 cache miss, according to this source.)

Now that is just one architecture, and others will vary. And we also need to consider other issues, like constraints on the number of multiplications that can be overlapped, and how well the compiler can organize the instructions to get them minimize instruction dependencies. But the fact remains that for a typical modern pipelined chip architecture, the CPU can execute integer multiplies as fast as it can execute memory to register moves, and much faster if there are more cache misses in the memory fetches.

Your benchmark is using lists with 100,000 Integer elements. When you look at the amount of memory involved, and the relative locality of the heap nodes that represent the lists and the elements, the linked list case will use significantly more memory, and have correspondingly worse memory locality. That will lead to more cache misses per cycle of the inner loop, and worse performance.

Your benchmark results are not surprising² to me.

---

The other thing to note is that if you use Java LinkedList, a separate heap node is used to represent the list nodes. You can implement your own linked lists more efficiently if your element class has its own next field that can be used to chain the elements. However, brings its own limitations; e.g. an element can only be in one list at a time.

Finally, as @maaartinus points out, a full IMUL is not required in the case of a Java ArrayList. When reading or writing the ArrayList's array, the indexing multiplication will be either x 4 or x 8 and that can be performed by a MOV with one of the standard addressing modes; e.g.

MOV EAX, [EDX + EBX*4 + 8]

This multiplication can be done (at the hardware level) by shifting with much less latency than 64 bit IMUL.

---

^{1 - In this context, the latency is the number of cycles delay before the result of the instruction is available ... to the next instruction that depends on it. The trick is to order the instructions so that other work is done during the delay.}

^{2 - If anything, I am surprised that LinkedList appears to be doing so well. Maybe calling Random.nextInt() and autoboxing the result is dominating the loop times?}