sorting - 为什么是 F#'s Seq.sortBy much slower than LINQ' s IEnumerable.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 行由两个 double 组成的文件上，在我的计算机上，后一个版本占用的时间是第一个版本的两倍(如果使用 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 #)

但是 Operator 的路径完全是内联的，因此 JIT 编译器最终将插入直接双重比较指令，除了(在两种情况下都需要)委托(delegate)调用之外没有额外的方法调用开销。

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 中获得了一些合理的百分比加速，输入序列非常大(> 百万)，但没有一个数量级。与往常一样，您的里程可能会有所不同。