.net - 为什么数组的序列表达式在 F# 中如此缓慢？

Question

代码:

#time "on"

let newVector = [| 
  for v in 1..10000000 ->
    v |] 

let newVector2 = 
  let a = Array.zeroCreate 10000000
  for v in 1..10000000 do
    a.[v-1] <- v
  a

let newVector3 = 
  let a = System.Collections.Generic.List() // do not set capacity
  for v in 1..10000000 do
    a.Add(v)
  a.ToArray()

在 FSI 中给出时间:

--> Timing now on

> 
Real: 00:00:01.121, CPU: 00:00:01.156, GC gen0: 4, gen1: 4, gen2: 4

val newVector : int [] =  [|1; 2; 3; 4; ...|]

> 
Real: 00:00:00.024, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0

val newVector2 : int32 [] =  [|1; 2; 3; 4; ...|]

> 
Real: 00:00:00.173, CPU: 00:00:00.156, GC gen0: 2, gen1: 2, gen2: 2

val newVector3 : int32 [] =  [|1; 2; 3; 4;  ...|]

在独立应用程序中差别不大， Release模式，没有调试，平均运行 5 次:

序列表达式:425

预分配:13

列表:80

第三种方法不知道原始容量，但仍然快了近 7 倍。为什么数组的序列表达式在 F# 中如此缓慢？

更新:

let seq = seq { for v in 1..10000000 do yield v }
let seqArr = seq |> Seq.toArray
Real: 00:00:01.060, CPU: 00:00:01.078, GC gen0: 2, gen1: 2, gen2: 2

let newVector4 = 
  let a = System.Collections.Generic.List() // do not set capacity
  for v in seq do
    a.Add(v)
  a.ToArray()
Real: 00:00:01.119, CPU: 00:00:01.109, GC gen0: 1, gen1: 1, gen2: 1

open System.Linq
let newVector5 =  seq.ToArray()
Real: 00:00:00.969, CPU: 00:00:00.968, GC gen0: 0, gen1: 0, gen2: 0

这给出了与第一个相同的时间，并且不依赖于 GC。所以 真题是，为什么要枚举 1..10000000慢得多 for在第二种和第三种情况下循环？

更新 2

open System
open System.Linq
open System.Collections.Generic
let newVector5 =  seq.ToArray()

let ie count = 
  { new IEnumerable<int> with
      member x.GetEnumerator(): Collections.IEnumerator = x.GetEnumerator() :> Collections.IEnumerator

      member x.GetEnumerator(): IEnumerator<int> = 
        let c = ref 0
        { new IEnumerator<int> with
            member y.MoveNext() = 
              if !c < count then
                c := !c + 1
                true
              else false

            member y.Current with get() = !c + 1
            member y.Current with get() = !c + 1 :> obj
            member y.Dispose() = () 
            member y.Reset() = ()       
        }
  }


let newVector6 = 
  let a = System.Collections.Generic.List() // do not set capacity
  for v in ie 10000000 do
    a.Add(v)
  a.ToArray()
Real: 00:00:00.185, CPU: 00:00:00.187, GC gen0: 1, gen1: 1, gen2: 1

手动实现 IEnumerable 相当于 for循环。我想知道为什么要扩展 lo..hi对于一般情况，应该慢得多。至少对于最常见的类型，它可以通过方法重载来实现。

Answer 1

在这种情况下，我总是使用 .NET 中许多优秀的反编译器之一检查生成的代码。

let explicitArray () = 
  let a = Array.zeroCreate count
  for v in 1..count do
    a.[v-1] <- v
  a

这被编译成等效的 C#:

public static int[] explicitArray()
{
    int[] a = ArrayModule.ZeroCreate<int>(10000000);
    for (int v = 1; v < 10000001; v++)
    {
        a[v - 1] = v;
    }
    return a;
}

这与它获得的效率差不多。

let arrayExpression () = 
  [|  for v in 1..count -> v |] 

另一方面，这变成:

public static int[] arrayExpression()
{
    return SeqModule.ToArray<int>(new Program.arrayExpression@7(0, null, 0, 0));
}

这相当于:

let arrayExpression () = 
  let e = seq { for v in 1..count -> v }
  let a = List() // do not set capacity
  for v in e do
    a.Add(v)
  a.ToArray()

迭代 seq 时( IEnumerable 的别名)第一个 MoveNext被调用，然后 Current .这些是 JIT:er 很少可以内联的虚拟调用。检查 JIT:ed 汇编代码，我们看到:

mov         rax,qword ptr [rbp+10h]  
cmp         byte ptr [rax],0  
mov         rcx,qword ptr [rbp+10h]  
lea         r11,[7FFC07830030h]  
# virtual call .MoveNext
call        qword ptr [7FFC07830030h]  
movzx       ecx,al  
# if .MoveNext returns false then exit
test        ecx,ecx  
je          00007FFC079408A0  
mov         rcx,qword ptr [rbp+10h]  
lea         r11,[7FFC07830038h]  
# virtual call .Current
call        qword ptr [7FFC07830038h]  
mov         edx,eax  
mov         rcx,rdi  
# call .Add
call        00007FFC65C8B300  
# loop
jmp         00007FFC07940863  

如果我们将其与使用 ResizeArray 的代码的 JIT:ed 代码进行比较( List )

lea         edx,[rdi-1]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
mov         edx,edi  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
lea         edx,[rdi+1]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
lea         edx,[rdi+2]  
mov         rcx,rbx  
# call .Add
call        00007FFC65C8B300  
add         edi,4  
# loop
cmp         edi,989682h  
jl          00007FFC07910384  

这里 JIT:er 在这里展开了 4 次循环，我们只有对 List.Add 的非虚拟调用。 .

这解释了为什么 F# 数组表达式比其他两个示例慢。

为了解决这个问题，必须修复 optimizer在 F# 中识别表达式的形状，例如:

seq { for v in 1..count -> v } |> Seq.toArray

并将它们优化为:

let a = Array.zeroCreate count
for v in 1..count do
    a.[v-1] <- v
a

挑战在于找到一种既通用又实用又不破坏 F# 语义的优化。