为什么 Seq.init 比带 'for' 的序列表达式慢？

Question

以下代码显示使用包含 for 的序列表达式生成序列比使用 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

问题：

1)速度差异的原因是什么？

2) 在某种意义上 Seq.init 替代 "more functional" 然后是序列表达式替代？

3) 就线程安全而言，这两种选择是否等效？

Answer 1

速度差的原因是什么？

Seq.init 很慢，因为它使用的 Seq.upto 很慢。 Seq.upto 很慢主要是因为它为管道中的每个对象创建了一个 Lazy 实例。这也解释了GC压力。

在 Fsharp.Core 的当前状态下，如果您需要性能 Seq 不是正确的选择。

这将在合并 manostick PR 时改变。

此外，甚至
```
seq {for i in 0..(count - 1) -> rnd.NextDouble()}
```
与 nessos 或改进的 manostick 等管道相比速度较慢 Seq.
在某种意义上Seq.init替代"more functional"然后是序列表达式替代？

序列表达式又名序列理解与数学中的集合理解有关。 IMO 两者都具有功能 "taste"。
这两个替代方案在线程安全方面是否等效？

是的，因为两者都没有提供线程安全。

PS。 Seq 和 LINQ 速度慢的另一个原因是它们依赖于拉式管道。推送管道更快。 Nessos 和 manofstick 管道同时支持 AFAICT 并尽可能选择推送。

P.S。我写了一个不同管道的快速性能比较。结果是 sum 而不是隔离实际管道性能的列表，而不是创建列表的成本。我还改变了内部和外部迭代的数量，以检测创建管道的开销：

// 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

结果如下（.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 . . .

所以 Seq.init 表现最差，"Tail-recursion"（本质上是一个循环）在 CPU 性能和内存使用方面表现最好。

实际上生成随机数本身需要一些时间，所以如果我改用 id，数字看起来像这样：

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

为什么 Seq.init 比带 'for' 的序列表达式慢？

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

f#

lazy-sequences