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;
    }

}

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.

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.

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.