Why processing arrays in F# is faster than lists

Question

I was checking the performance of F# lists and arrays. Given the code:

let list = [ 1.. 100000 ]
for i in 1 .. 100 do ignore ( list|>List.map(fun n -> n))

let array = [| 1.. 100000 |]
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n))

I would suspect both to run in very similar time. Actually it turned out that arrays are over 10 times faster : array takes 28 ms while list takes 346 ms! Why is that? I understand the concept of list in F# and the fact that for example appending values to list or taking subsequence is time consuming but in this code it just iterates through all elements so I thought the timing will be very comparable.

Tests under release mode in Visual Studio 2012 (in Debug mode arrays are about 5 times faster).

Answer 1

The main difference is that arrays are allocated as a continuous block of memory - the Array.map function knows the size of the input array and can perform just a single allocation to get all memory for the resulting array. On the other hand, the List.map function needs to separately allocate a single "cons cell" for each element of the input array.

The difference is particularly visible for the map function, because that can really benefit from the up-front allocation. However, arrays are generally faster for larger data sets. If you change the code to use filtering (where the array needs to be reallocated during construction), then the array version is ~2x faster:

for i in 1 .. 100 do ignore ( list|>List.filter(fun n -> n%5=1))
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n%5=1))

Using lists has other benefits - because they are immutable, you can safely share references to lists. Also, cloning a list and adding an element to the front is super efficient (single cell allocation), while doing similar operation with array would be really slow (copy the whole array).