在什么情况下,f#中的列表被f#编译器优化为数组,for循环,while循环等,而不创建单个链接数据的实际列表?
例如:
[1..1000] |> List.map something
可以在不创建实际列表的情况下优化为for循环。但我不知道编译器是否在做那个。
映射较小的列表可以通过循环展开等来优化
在什么情况下,f#中的列表被f#编译器优化为数组,for循环,while循环等,而不创建单个链接数据的实际列表?
。
你后面的评论很有启发性,因为你认为这是f#的一个缺陷:
…它应该足够聪明才能做到这一点。类似于Haskell编译器…
有些真实的。
…Haskell编译器正在做很多这样的优化…
。
然而,这实际上是一个非常糟糕的主意。具体来说,当您真正想要的是性能时,您正在追求优化。Haskell提供了许多奇异的优化,但它的性能特征实际上非常糟糕。此外,Haskell的属性使得这些优化易于处理,需要在其他地方做出巨大的牺牲:
- 纯度使互操作性变得更加困难,所以微软杀死了Haskell。. NET和Haskell只能与自己不兼容的VM共存。
- Haskell的VM中的GC已经为纯功能代码进行了优化,代价是突变。
- 纯函数数据结构通常是10×比它们的命令式对等物慢,有时渐近慢,在某些情况下没有已知的纯功能对等物。
- 懒惰和纯粹是齐头并进的("严格的评估是规范的副作用"),懒惰不仅会大大降低性能,而且使其变得难以预测。 为了对抗这种糟糕的性能(例如严格性分析),大量的优化添加到Haskell中,使性能变得更加不可预测。
- 不可预测的缓存行为使得多核的可伸缩性不可预测。
对于这些优化没有回报的一个小例子,看看Haskell中习惯的2行快速排序,尽管它进行了所有的优化,但仍然比c中的Sedgewick快速排序慢数千倍。理论上,一个足够聪明的Haskell编译器可以将这样的源代码优化成一个有效的程序。在实践中,世界上最复杂的Haskell编译器甚至不能为一个微不足道的两行程序做到这一点,更不用说真正的软件了。
The Computer Language benchmark Game上的Haskell程序源代码提供了一些有启发性的例子,说明当你优化Haskell代码时,它会变得多么可怕。
我想要一种编程语言:
- 有一个简单的编译方法,保持性能可预测。
- 使需要优化的地方易于手工优化。
- 设置较高的性能上限,以便在必要时接近最佳性能。
f#满足这些要求
我认为"never"是答案。
如果你看一下反汇编,这很容易理解
// 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
}
您可以看到在000c
和0011
处创建了可枚举对象,然后在0016
处将序列转换为列表
所以在这种情况下,优化不会发生。事实上,编译器很难进行这样的优化,因为Seq.Map
和List.Map
之间可能存在许多差异(这是最简单的优化,因为它可以避免临时列表)。
虽然这个问题是前段时间提出的,但目前的情况有些不同。
许多list模块函数实际上在内部使用数组。
例如,pair的当前实现是
[<CompiledName("Pairwise")>]
let pairwise (list: 'T list) =
let array = List.toArray list
if array.Length < 2 then [] else
List.init (array.Length-1) (fun i -> array.[i],array.[i+1])
也是FoldBack
(尽管仅适用于长度大于4的列表)
// this version doesn't causes stack overflow - it uses a private stack
[<CompiledName("FoldBack")>]
let foldBack<'T,'State> f (list:'T list) (acc:'State) =
let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
match list with
| [] -> acc
| [h] -> f.Invoke(h,acc)
| [h1;h2] -> f.Invoke(h1,f.Invoke(h2,acc))
| [h1;h2;h3] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,acc)))
| [h1;h2;h3;h4] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,f.Invoke(h4,acc))))
| _ ->
// It is faster to allocate and iterate an array than to create all those
// highly nested stacks. It also means we won't get stack overflows here.
let arr = toArray list
let arrn = arr.Length
foldArraySubRight f arr 0 (arrn - 1) acc
这里,foldArraySubRight
实际上使用一个迭代循环来处理数组。
其他具有类似优化的函数几乎包括任何名称为*Back
的函数以及所有sort*
函数和permute
函数。