Why use lists when arrays are faster?

Question

I noticed that arrays are much faster than Haxe Linked Lists (at least on cpp). The results that 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. 

It seems dazzling to me. How can an Array be so fast, although it has to constantly copy elements? And why even use lists?

 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 an Array be so fast, although it has to constantly copy elements?

Arrays are faster for linear processing because the contents of the array are stored permanently in memory. When you access memory linearly, several objects are simultaneously extracted from the processor cache. On the other hand, the nodes of the node nodes are scattered throughout the memory, so their processing linearly leads to more failures in the main memory. Reading the cache is much faster than reading the main memory.

And why even use lists?

One of the main reasons for using a linked list is that inserting new elements or deleting existing ones does not invalidate references (including iterators and pointers) to other elements of the linked list. An array cannot have such a guarantee.

Answer 2

Why use lists when arrays are faster?

Faster for what? Linked lists are generally much faster when it comes to inserting items between others or deleting items in the middle of a list. With an array (at least an array of type C) inserting or deleting at position i , each element needs to be moved after i . With linked lists, you only need to change a couple of pointers.

Try again, but instead of clicking items at the end of the list, insert them at the beginning.

Answer 3

There is an article that addresses this issue in detail:

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

TL; DR: it depends on your use case, but the list may definitely speed up in some scenarios.