why is Seq.iter and Seq.map so much slower?
-
12-06-2021 - |
Question
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?
Solution
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
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow