在什么情况下,F#中的列表是由编译器优化的？

Question

在什么情况下,F#中的列表通过F#编译器优化到数组,for循环,while循环等,而不创建单个链接数据的实际列表？

例如:

[1..1000] |> List.map something

可以针对for循环进行优化,而无需创建实际列表.但我不知道编译器是否真的这样做了.

可以使用循环展开等优化在大小较小的列表上进行映射.

Answer 1

我认为"永远"是答案.

Answer 2

在什么情况下,F#中的列表通过F#编译器优化到数组,for循环,while循环等,而不创建单个链接数据的实际列表？

决不.

你后来的评论很有启发性,因为你认为这是F#中的一个缺陷:

......它应该足够聪明.与Haskell编译器类似...

有点真实.

... Haskell编译器正在做很多这样的优化......

真正.

然而,这实际上是一个非常糟糕的主意.具体来说,当您真正想要的是性能时,您正在寻求优化.Haskell提供了许多奇特的优化,但其性能特征实际上非常糟糕.此外,使这些优化易于处理的Haskell属性需要在其他地方做出大量牺牲:

• 纯度使互操作性变得更加困难,因此微软杀死了Haskell.NET,而Haskell只能使用自己的不兼容虚拟机.
• Haskell VM中的GC已针对纯功能代码进行了优化,但代价是突变.
• 纯功能数据结构通常比其命令等效数据慢10倍,有时渐近地慢,在某些情况下,没有已知的纯函数等价物.
• 懒惰和纯洁是相辅相成的("严格评估是规范的副作用"),懒惰不仅会大幅降低性能,还会使其变得非常难以预测.
• 为了对抗这种糟糕的性能(例如严格性分析),Haskell增加了大量的优化,使得性能更难以预测.
• 不可预测的缓存行为使得多核上的可扩展性变得不可预测.

对于这些优化的一个简单例子而言,没有比Haskell中惯用的2行快速排序更好看,尽管它的所有优化都比Sedgewick在C中的快速排序慢了数千倍.理论上,一个足够智能的Haskell编译器可以将这些源代码优化为有效的程序.在实践中,世界上最复杂的Haskell编译器甚至不能为一个简单的两行程序做到这一点,而不是真正的软件.

计算机语言基准游戏中 Haskell程序的源代码提供了一些启发性的例子,说明优化它时Haskell代码的可怕程度.

我想要一种编程语言:

• 有一个简单的编译方法,可以保持性能可预测.
• 在需要优化的地方,可以轻松优化.
• 在性能上有很高的上限,这样我就可以在必要时接近最佳性能.

F#满足这些要求.

Answer 3

很容易看出你是否看到了反汇编 - 这很容易阅读

    // method line 4
    .method public static
           default void main@ ()  cil managed
    {
        // Method begins at RVA 0x2078
    .entrypoint
    // Code size 34 (0x22)
    .maxstack 6
    IL_0000:  newobj instance void class Test2/clo@2::'.ctor'()
    IL_0005:  ldc.i4.1
    IL_0006:  ldc.i4.1
    IL_0007:  ldc.i4 1000
    IL_000c:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> class [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32)
    IL_0011:  call class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0> class [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_0016:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0> class [FSharp.Core]Microsoft.FSharp.Collections.SeqModule::ToList<int32> (class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>)
    IL_001b:  call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!1> class [FSharp.Core]Microsoft.FSharp.Collections.ListModule::Map<int32, int32> (class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,!!1>, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!0>)
    IL_0020:  pop
    IL_0021:  ret
    } // end of method $Test2::main@

  } // end of class <StartupCode$test2>.$Test2
}

您可以看到at 000c和0011创建的枚举,然后在0016序列转换为列表

所以在这种情况下,优化不会发生.事实上,编译器很难进行这样的优化,因为在Seq.Map和之间可能存在任何数量的差异List.Map(这是最简单的优化,因为它会避免临时列表).