Почему Seq.sortBy в F# работает намного медленнее, чем метод расширения IEnumerable<T>.OrderBy в LINQ?

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)

В файле, содержащем 100 000 строк, состоящих из двух двойных значений, на моем компьютере последняя версия занимает в два раза больше времени, чем первая (при использовании 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<_>)

оба Operations.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 с очень большими (> миллионами) входными последовательностями, но не на порядок.Ваш пробег, как всегда, может варьироваться.

Answer 2

Разница в x2 невелика, если сортировка равна O(n.log(n)).

Небольшие различия в структурах данных (например.оптимизация для ввода ICollection<T>) может иметь такое масштабное значение.

А F# в настоящее время находится в бета-версии (не так много внимания уделяется оптимизации, а не разработке).правильное использование языка и библиотек), а также общность функций F# (поддержка частичного применения и т. д.) могут привести к небольшому замедлению скорости вызова:более чем достаточно, чтобы объяснить разницу.