11

Consider this code in F#:

let n = 10000000
let arr = Array.init n (fun _ -> 0)

let rec buildList n acc i = if i = n then acc else buildList n (0::acc) (i + 1)
let lst = buildList n [] 0

let doNothing _ = ()
let incr x = x + 1

#time

arr |> Array.iter doNothing         // this takes 14ms
arr |> Seq.iter doNothing           // this takes 74ms

lst |> List.iter doNothing          // this takes 19ms
lst |> Seq.iter doNothing           // this takes 88ms

arr |> Array.map incr               // this takes 33ms
arr |> Seq.map incr |> Seq.toArray  // this takes 231ms!

lst |> List.map incr                // this takes 753ms
lst |> Seq.map incr |> Seq.toList   // this takes 2111ms!!!!

Why is the iter and map functions on the Seq module so much slower than the Array and List module equivalents?

1 Answer 1

14

Once you call in to Seq you lose the type information - moving to the next element in the list requires a call to IEnumerator.MoveNext. Compare to for Array you just increment an index and for List you can just dereference a pointer. Essentially, you are getting an extra function call for each element in the list.

The conversions back to List and Array also slow the code down for similar reasons

1
  • 2
    Though you are probably right about the actual cause. It doesn't really answer the question on a deeper level. Why did they choose to use MoveNext. As done through out the linq library you could start with a type check and in the case of a list or an array choose the matching version then difference for large sequences would then be neglect-able
    – Rune FS
    Commented Dec 19, 2014 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.