Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

why is Seq.iter and Seq.map so much slower?

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?

like image 668
theburningmonk Avatar asked Jun 03 '12 22:06

theburningmonk


1 Answers

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

like image 67
John Palmer Avatar answered Oct 22 '22 00:10

John Palmer