F#"​​for loop"优化

Question

代码示例:

let foo1 (arr : int[]) = 
    for i = 0 to arr.Length-1 do
        arr.[i] <- i

let foo2 (arr : int[]) = 
    for i in [0..arr.Length-1] do
        arr.[i] <- i

我认为这个功能应该相互对应(在性能方面).但如果我们查看IL列表,我们会看到:

第一个功能,15行,没有动态分配,没有try操作员,没有虚拟呼叫:

IL_0000: nop
IL_0001: ldc.i4.0
IL_0002: stloc.0
IL_0003: br.s IL_0011
// loop start (head: IL_0011)
    IL_0005: ldarg.0
    IL_0006: ldloc.0
    IL_0007: ldloc.0
    IL_0008: stelem.any [mscorlib]System.Int32
    IL_000d: ldloc.0
    IL_000e: ldc.i4.1
    IL_000f: add
    IL_0010: stloc.0

    IL_0011: ldloc.0
    IL_0012: ldarg.0
    IL_0013: ldlen
    IL_0014: conv.i4
    IL_0015: blt.s IL_0005
// end loop

IL_0017: ret

第二个 - 几乎100行,大量的分配/解除分配,虚拟函数的调用,大量的try/ Dispose:

IL_0000: nop
IL_0001: ldc.i4.0
IL_0002: ldc.i4.1
IL_0003: ldarg.0
IL_0004: ldlen
IL_0005: conv.i4
IL_0006: ldc.i4.1
IL_0007: sub
IL_0008: call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32)
IL_000d: call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
IL_0012: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToList<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
IL_0017: stloc.0
IL_0018: ldloc.0
IL_0019: unbox.any class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>
IL_001e: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator()
IL_0023: stloc.1
.try
{
    // loop start (head: IL_0024)
        IL_0024: ldloc.1
        IL_0025: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
        IL_002a: brfalse.s IL_003e

        IL_002c: ldloc.1
        IL_002d: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current()
        IL_0032: stloc.3
        IL_0033: ldarg.0
        IL_0034: ldloc.3
        IL_0035: ldloc.3
        IL_0036: stelem.any [mscorlib]System.Int32
        IL_003b: nop
        IL_003c: br.s IL_0024
    // end loop

    IL_003e: ldnull
    IL_003f: stloc.2
    IL_0040: leave.s IL_005b
} // end .try
finally
{
    IL_0042: ldloc.1
    IL_0043: isinst [mscorlib]System.IDisposable
    IL_0048: stloc.s 4
    IL_004a: ldloc.s 4
    IL_004c: brfalse.s IL_0058

    IL_004e: ldloc.s 4
    IL_0050: callvirt instance void [mscorlib]System.IDisposable::Dispose()
    IL_0055: ldnull
    IL_0056: pop
    IL_0057: endfinally

    IL_0058: ldnull
    IL_0059: pop
    IL_005a: endfinally
} // end handler

IL_005b: ldloc.2
IL_005c: pop
IL_005d: ret

我的问题是为什么F#编译器使用如此复杂的代码foo2？为什么用它IEnumerable来实现如此微不足道的循环？

Answer 1

在第二个例子中,如果你使用范围表达式,它将被转换为正常for循环:

let foo2 (arr : int[]) = 
    for i in 0..arr.Length-1 do
        arr.[i] <- i

并成为等同于foo1.

我引用F#语言规范中的第6.3.12节范围表达式:

expr1中的var形式的序列迭代表达式expr2 do expr3有时被详细描述为一个简单的for循环表达式(§6.5.7).

但是,你的第二个例子更像是:

let foo2 (arr : int[]) = 
    let xs = [0..arr.Length-1] (* A new list is created *)
    for i in xs do
        arr.[i] <- i

您已明确创建新列表的位置.

Answer 2

您所看到的是使用基于索引的枚举和IEnumerable基于枚举(或在C#术语forvs foreach)之间的标准差异.

在第二个示例中,表达式[0..arr.Length-1]创建一个集合,F#IEnumerable<T>用于枚举值.此枚举样式的一部分涉及使用IEnumerator<T>哪些实现IDisposable.try / finally生成的块是生成的,以确保IDisposable::Dispose在枚举结束时调用该方法,即使面对异常也是如此.

F#可以优化第二个例子到第一个例子并避免所有额外的开销吗？他们可能会做这个优化.基本上是通过范围表达式查看,而不仅仅是一个简单的数值范围,因此生成等效for代码.

应该F#优化第二个例子.我的投票结果是否定的.像这样的功能通常从外面看起来微不足道,但实际上实现它们,更重要的是维护它们,可能相当昂贵.精明的用户总是可以将他们的代码转换回标准for版本并避免IEnumerable<T>开销(如果探查器将其显示为问题).不实施优化可以释放F#团队以实现其他非常棒的功能.