Why use Lists, when Arrays are faster?

Question

I noticed that Arrays perform much, much faster than Haxe's Linked Lists (atleast on cpp). The results I got are as follows.

Main.hx:40: With 1 items, Array is 14% faster than List.
Main.hx:40: With 5 items, Array is 58% faster than List.
Main.hx:40: With 10 items, Array is 59% faster than List.
Main.hx:40: With 100 items, Array is 54% faster than List.
Main.hx:40: With 1000 items, Array is 56% faster than List.
Main.hx:40: With 10000 items, Array is 55% faster than List.
Main.hx:40: With 100000 items, Array is 52% faster than List.

This strikes me as bedazzling. How can Array be so fast even though it has to copy around items continuously? And why even use Lists then?

package tests;

import haxe.Timer;

class Main 
{

    static function main() 
    {
        var arr:Array<Int> = new Array();
        var list:List<Int> = new List();
        var result = new List();

        for (items in [1, 5, 10, 100, 1000, 10000, 100000]) {
            var listtime = timeit(10000, function() {
                for (i in 0...items)
                    list.add(i);
                for (x in list)
                    result.add(x);
                result.clear();
                list = new List();
            });

            var arrtime = timeit(10000, function() {
                for (i in 0...items)
                    arr.push(i);
                for (x in arr)
                    result.add(x);
                result.clear();
                arr = new Array();
            });

            if (arrtime < listtime)
                trace('With $items items, Array is ${Std.int((1-arrtime/listtime)*100)}% faster than List.');
            else
                trace('With $items items, List is ${Std.int((1-listtime/arrtime)*100)}% faster than Array.');
        }
    }

    static public function timeit<T>(times:Int, f:Void -> T):Float {
        var start = Timer.stamp();
        for (i in 0...times) {
            f();
        }
        var time = Timer.stamp() - start;
        return time;
    }

}

Wallywalnut

Locality of reference – Pd

Also, if you look at how lists are implemented in haxe, they create a bunch of mini arrays for whatever reason and add 2 elements to each, and naturally that's slower than just adding to an array. – Gilmer

Answer 1

How can Array be so fast even though it has to copy around items continuously?

Arrays are faster for linear processing because array contents are stored contiguously in memory. When you access memory linearly, multiple objects are fetched to the processor cache simultaneously. Linked list nodes on the other hand are scattered throughout the memory, so processing them linearly results in more acccesses in main memory. Reading cache is much, much faster than reading main memory.

And why even use Lists then?

One major reason to use a linked list, is that inserting new elements, or removing existing ones, does not invalidate references (including iterators and pointers) to other elements in the linked list. An array can not have such guarantee.

Protectionism

Chose this one as accepted, because it has more information. – Wallywalnut

Answer 2

Why use Lists, when Arrays are faster?

Faster for what? Linked lists are typically a lot faster when it comes to inserting elements between others or deleting elements in the middle of the list. With an array (at least, an C-style array) inserting or deleting at position i requires moving every element after i. With linked lists, you need only change a couple of pointers.

Try your test again, but instead of pushing elements onto the end of the list, insert them at the beginning.

Stuffed

Hmm, I see. Don't know why I didn't think about that. – Wallywalnut

For your "insert at beginning" example, std::deque would be faster than a list, so I don't think it's very good at justifying the use of lists by itself. – Protectionism

@user2079303 You miss the point, which is that different data structures have different strengths and weaknesses. I said insert them at the beginning because in the context of the OP's test, that's an easy change that shows a case where lists are faster than arrays. – Stuffed

@Stuffed you miss the point of my comment which is that question that was asked is "Why use Lists(, when Arrays are faster)?" Lists being faster than an array in one context is only an argument for not using an array in that context. If there are no use cases where there is no better alternative than a list, then it is not useful to ever use a list. I do admit that your example does point out well the misguided reasoning that lead Seeq to post the question. – Protectionism

Answer 3

There is an article that goes over this matter extensively :

https://github.com/delahee/haxe.opt/blob/master/list_vs_array.md

TLDR : it depends of your use case but list can definitely go faster in some scenarios.

Quinlan