为什么F#的Seq.sortBy比LINQ的IEnumerable <T> .OrderBy扩展方法慢得多？

Question

我最近编写了一段代码来从文件中读取一些数据,将其存储在元组中,并通过元组的第一个元素对所有收集的数据进行排序.经过一些测试后,我注意到使用Seq.sortBy(和Array.sortBy)比使用IEnumerable.OrderBy慢得多.下面是两段代码,它们应该显示我正在谈论的行为:

(filename
|> File.ReadAllLines
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) 
                                |> Array.map(double) 
                                |> Array.sort in arr.[0], arr.[1])
).OrderBy(new Func(fun (a,b) -> a))

和

filename
|> File.ReadAllLines
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1])
|> Seq.sortBy(fun (a,_) -> a)

在包含由两个双打组成的100000行的文件上,在我的计算机上,后一版本占用了第一个版本的两倍(如果使用Array.sortBy则不会获得任何改进).想法？

Answer 1

f#实现使用结果密钥的结构比较.

let sortBy keyf seq =
    let comparer = ComparisonIdentity.Structural
    mkDelayedSeq (fun () -> 
        (seq 
        |> to_list 
        |> List.sortWith (fun x y -> comparer.Compare(keyf x,keyf y)) 
        |> to_array) :> seq<_>)

(也排序)

let sort seq =
    mkDelayedSeq (fun () -> 
        (seq 
        |> to_list 
        |> List.sortWith Operators.compare 
        |> to_array) :> seq<_>)

Operators.compare和ComparisonIdentity.Structural.Compare都成为(最终)

let inline GenericComparisonFast<'T> (x:'T) (y:'T) : int = 
    GenericComparisonIntrinsic x y
        // lots of other types elided
        when 'T : float = if (# "clt" x y : bool #) 
                          then (-1) 
                          else (# "cgt" x y : int #)

但是运营商的这条路线完全是内联的,因此JIT编译器最终会插入一个直接的双重比较指令而没有额外的方法调用开销,除了(无论如何都需要)委托调用.

sortBy使用比较器,因此将进行额外的虚拟方法调用,但基本上是相同的.

相比之下,OrderBy函数也必须通过虚方法调用来进行相等(使用EqualityComparer<T>.Default),但重要的区别在于它就地排序并使用为此创建的缓冲区作为结果.相比之下,如果您查看sortBy,您将看到它对列表进行排序(不到位,它使用似乎是合并排序的StableSortImplementation),然后创建它作为新数组的副本.这个额外的副本(给定输入数据的大小)可能是减速的主要原因,尽管不同的排序实现也可能有效.

这就是猜测.如果这个领域在性能方面是您关注的问题,那么您应该简单地进行分析以找出花费时间的内容.

如果您希望看到排序/复制更改会尝试此备用的效果:

// these are taken from the f# source so as to be consistent
// beware doing this, the compiler may know about such methods
open System.Collections.Generic
let mkSeq f = 
    { new IEnumerable<'b> with 
        member x.GetEnumerator() = f()
      interface System.Collections.IEnumerable with 
        member x.GetEnumerator() = (f() :> System.Collections.IEnumerator) }

let mkDelayedSeq (f: unit -> IEnumerable<'T>) = 
    mkSeq (fun () -> f().GetEnumerator())

// the function
let sortByFaster keyf seq =
    let comparer = ComparisonIdentity.Structural
    mkDelayedSeq (fun () -> 
        let buffer = Seq.to_array seq
        Array.sortInPlaceBy (fun x y -> comparer.Compare(keyf x,keyf y)) buffer
        buffer :> seq<_>)

我在repl中获得了一些合理的百分比加速,具有非常大(>百万)的输入序列,但没有像一个数量级.您的里程一如既往可能会有所不同.