Why is Seq.init slower than a sequence expression with 'for'?

Question

The following code showed that generating a sequence using a sequence expression containing for was approximately five times faster than generating the same sequence using Seq.init.

open System
let rand count =
    let rnd = Random() // if this value is not created all numbers are equal
    seq {for i in 0..(count - 1) -> rnd.NextDouble()}


/// Perhaps more "functional" than rand but slower
let rand2 count =
    let rnd = Random()
    let rnd2 (i: int) = rnd.NextDouble()
    Seq.init count rnd2

> rand 1000000 |> List.ofSeq |> List.head;;
Real: 00:00:00.092, CPU: 00:00:00.093, GC gen0: 3, gen1: 2, gen2: 0
val it : float = 0.1358240168

> rand2 1000000 |> List.ofSeq |> List.head;;
Real: 00:00:00.473, CPU: 00:00:00.484, GC gen0: 21, gen1: 20, gen2: 1
val it : float = 0.4128856414

Questions:

1) What is the reason for the speed difference?

2) Is the Seq.init alternative in some sense "more functional" then the sequence expression alternative?

3) Are the two alternatives equivalent in terms of thread-safety?

Answer 1

1. What is the reason for the speed difference?

   Seq.init is slow because it uses Seq.upto which is slow. Seq.upto is slow mainly because it creates a Lazy instance for every object in the pipeline. This also explains the GC pressure.

   In the current state of Fsharp.Core, if you need performance Seq isn't the right option.

   This will change though when the manostick PR is merged.

   In addition, even

   seq {for i in 0..(count - 1) -> rnd.NextDouble()}
   

   is slow compared to pipelines such as nessos or manostick improved Seq.

2. Is the Seq.init alternative in some sense "more functional" then the sequence expression alternative?

   Sequence expressions aka sequence comprehension is related to set comprehensions in mathematics. IMO both have functional "taste" to them.

3. Are the two alternatives equivalent in terms of thread-safety?

   Yes, in that neither provide thread-safety.

PS. Another reason Seq and LINQ are slow is that they rely on pull pipelines. Push pipelines are faster. Nessos and manofstick pipelines support both AFAICT and choose push if possible.

P.S. I wrote a quick little performance comparison of different pipelines. The result is sum not a list to isolate the actual pipeline performance, not the cost of creating lists. I also vary the number of inner and outer iterations in order to detect overhead from creating pipelines:

// A simplistic push-pipeline
type Receiver<'T> = 'T -> bool
type Stream<'T>   = Receiver<'T> -> unit

module Stream =
  let inline init count gen : Stream<_> =
    fun r ->
      let rec loop i =
        if i < count && r (gen i) then
          loop (i + 1)
      loop 0

  let inline sum (s : Stream<_>) : _ =
    let mutable a = LanguagePrimitives.GenericZero<_>
    s (fun v -> a <- a + v; true)
    a

let rnd = System.Random ()
let gen = fun _ -> rnd.NextDouble ()

let clock =
  let sw = System.Diagnostics.Stopwatch ()
  sw.Start ()
  fun () -> sw.ElapsedMilliseconds

open System

let timeIt n a = 
  let r                 = a ()  // Warm-up

  GC.Collect (2, GCCollectionMode.Forced, true)

  let inline cc g       = GC.CollectionCount g
  let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
  let before            = clock ()

  for i = 1 to n do
    a () |> ignore

  let after             = clock ()
  let acc0, acc1, acc2  = cc 0, cc 1, cc 2

  after - before, acc0 - bcc0, acc1 - bcc1, acc2 - bcc2, r

open System.Linq

[<EntryPoint>]
let main argv =
  let count = 10000000
  let outers =
    [|
      1000000
      10000
      100  
      1
    |]

  for outer in outers do
    let inner = count / outer
    let testCases = 
      [|
        "Push stream"       , fun ()  -> Stream.init inner gen                  |> Stream.sum
        "LINQ"              , fun ()  -> (Enumerable.Range (0, inner)).Select(gen).Sum()
        "Seq.init"          , fun ()  -> Seq.init    inner gen                  |> Seq.sum
        "Seq comprehension" , fun ()  -> seq { for i in 0..inner - 1 -> gen i } |> Seq.sum
        "Tail-recursion"    , fun ()  -> 
          let rec loop a i =
            if i < inner then
              loop (a + gen i) (i + 1)
            else
              a
          loop 0. 0
      |]
    printfn "Using outer = %A, inner = %A, total is: %A" outer inner count
    for nm, a in testCases do
      printfn "  Running test case: %A" nm
      let tm, cc0, cc1, cc2, r = timeIt outer a
      printfn "   it took %A ms (%A, %A, %A), result is: %A" tm cc0 cc1 cc2 r
  0

The results are as follows (.NET 4.6.2, x64, Release):

Using outer = 1000000, inner = 10, total is: 10000000
  Running test case: "Push stream"
  it took 145L ms (22, 0, 0), result is: 5.348407591
  Running test case: "LINQ"
  it took 296L ms (63, 0, 0), result is: 5.056716735
  Running test case: "Seq.init"
  it took 1490L ms (724, 0, 0), result is: 3.977087705
  Running test case: "Seq comprehension"
  it took 333L ms (66, 0, 0), result is: 5.208401204
  Running test case: "Tail-recursion"
  it took 109L ms (0, 0, 0), result is: 5.898073628
Using outer = 10000, inner = 1000, total is: 10000000
  Running test case: "Push stream"
  it took 118L ms (0, 0, 0), result is: 510.943297
  Running test case: "LINQ"
  it took 210L ms (0, 0, 0), result is: 488.3970571
  Running test case: "Seq.init"
  it took 1411L ms (661, 0, 0), result is: 505.2632877
  Running test case: "Seq comprehension"
  it took 264L ms (0, 0, 0), result is: 502.1710107
  Running test case: "Tail-recursion"
  it took 101L ms (0, 0, 0), result is: 487.9451813
Using outer = 100, inner = 100000, total is: 10000000
  Running test case: "Push stream"
  it took 118L ms (0, 0, 0), result is: 49850.99306
  Running test case: "LINQ"
  it took 202L ms (0, 0, 0), result is: 50113.06557
  Running test case: "Seq.init"
  it took 1398L ms (661, 0, 0), result is: 49923.14521
  Running test case: "Seq comprehension"
  it took 262L ms (0, 0, 0), result is: 50196.00191
  Running test case: "Tail-recursion"
  it took 98L ms (0, 0, 0), result is: 49878.16573
Using outer = 1, inner = 10000000, total is: 10000000
  Running test case: "Push stream"
  it took 117L ms (0, 0, 0), result is: 5000088.583
  Running test case: "LINQ"
  it took 201L ms (0, 0, 0), result is: 5000569.657
  Running test case: "Seq.init"
  it took 1388L ms (661, 0, 0), result is: 5000169.339
  Running test case: "Seq comprehension"
  it took 260L ms (0, 0, 0), result is: 5000263.083
  Running test case: "Tail-recursion"
  it took 97L ms (0, 0, 0), result is: 4999990.197
Press any key to continue . . .

So Seq.init does the worst and "Tail-recursion" (essentially a loop) does the best in both CPU performance and memory usage.

Actually generating the random numbers itself takes some time, so if I use id instead, the numbers look like this:

Using outer = 1000000, inner = 10, total is: 10000000
  Running test case: "Push stream"
  it took 47L ms (22, 0, 0), result is: 45.0
  Running test case: "LINQ"
  it took 211L ms (63, 0, 0), result is: 45.0
  Running test case: "Seq.init"
  it took 1364L ms (724, 0, 0), result is: 45.0
  Running test case: "Seq comprehension"
  it took 241L ms (66, 0, 0), result is: 45.0
  Running test case: "Tail-recursion"
  it took 10L ms (0, 0, 0), result is: 45.0
Using outer = 10000, inner = 1000, total is: 10000000
  Running test case: "Push stream"
  it took 28L ms (0, 0, 0), result is: 499500.0
  Running test case: "LINQ"
  it took 125L ms (0, 0, 0), result is: 499500.0
  Running test case: "Seq.init"
  it took 1285L ms (661, 0, 0), result is: 499500.0
  Running test case: "Seq comprehension"
  it took 170L ms (0, 0, 0), result is: 499500.0
  Running test case: "Tail-recursion"
  it took 8L ms (0, 0, 0), result is: 499500.0
Using outer = 100, inner = 100000, total is: 10000000
  Running test case: "Push stream"
  it took 27L ms (0, 0, 0), result is: 4999950000.0
  Running test case: "LINQ"
  it took 121L ms (0, 0, 0), result is: 4999950000.0
  Running test case: "Seq.init"
  it took 1289L ms (661, 0, 0), result is: 4999950000.0
  Running test case: "Seq comprehension"
  it took 169L ms (0, 0, 0), result is: 4999950000.0
  Running test case: "Tail-recursion"
  it took 9L ms (0, 0, 0), result is: 4999950000.0
Using outer = 1, inner = 10000000, total is: 10000000
  Running test case: "Push stream"
  it took 28L ms (0, 0, 0), result is: 4.9999995e+13
  Running test case: "LINQ"
  it took 121L ms (0, 0, 0), result is: 4.9999995e+13
  Running test case: "Seq.init"
  it took 1289L ms (661, 0, 0), result is: 4.9999995e+13
  Running test case: "Seq comprehension"
  it took 169L ms (0, 0, 0), result is: 4.9999995e+13
  Running test case: "Tail-recursion"
  it took 8L ms (0, 0, 0), result is: 4.9999995e+13