Warum ist F # 's Seq.sortBy viel langsamer als LINQ IEnumerable .OrderBy Erweiterungsmethode?

Question

Ich habe vor kurzem ein Stück Code zu lesen, einige Daten aus einer Datei, speichern Sie es in einem Tupel geschrieben und sortiert alle gesammelten Daten durch das erste Element des Tupels. Nach einigen Tests habe ich bemerkt, dass die Verwendung von Seq.sortBy (und Array.sortBy) ist extrem langsamer als IEnumerable.OrderBy verwenden. Im Folgenden sind zwei Code-Schnipsel, die das Verhalten zeigen sollte ich spreche:

(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))

und

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)

Auf eine Datei 100000 Linien aus zwei Doppelzimmern enthält, auf meinem Computer die letztere Version mehr als doppelt so lang wie die ersten nimmt (keine Verbesserungen bei Verwendung von Array.sortBy erhalten). Ideen?

Answer 1

die f # -Implementierung verwendet einen strukturellen Vergleich des erhaltenen Schlüssels.

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<_>)

(auch sort)

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

beide Operators.compare und die ComparisonIdentity.Structural.Compare werden (eventuell)

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 #)

aber der Weg zu diesem für den Betreiber ist vollständig inline, also die JIT-Compiler einen direkten Doppelvergleichsbefehls Einfügen ohne zusätzlichen Methodenaufruf Overhead mit Ausnahme des (erforderlich in beiden Fällen sowieso) Delegate-Aufruf am Ende werden.

Die sortBy verwendet ein Vergleich so wird einen zusätzlichen virtuellen Methodenaufruf durchläuft, ist aber im Grunde in etwa gleich.

Im Vergleich auch die OrderBy Funktion durch virtuelle Methodenaufrufe für die Gleichheit gehen muss (mit EqualityComparer<T>.Default), aber der wesentliche Unterschied ist, dass es an Ort und Stelle sortiert und verwendet den Puffer für diese als Ergebnis erstellt. Im Vergleich, wenn Sie einen Blick auf die sortBy nehmen, werden Sie sehen, dass es die Liste sortiert (nicht vorhanden, verwendet es die StableSortImplementation, die Art zu sein scheint zu merge) und erstellt dann eine Kopie davon als neues Array. Diese zusätzliche Kopie (die Größe der Eingangsdaten gegeben) ist wahrscheinlich die Hauptursache für die Verlangsamung obwohl die unterschiedliche Art Implementierungen kann auch eine Wirkung hat.

Das heißt all ist zu raten . Wenn dieser Bereich ist ein Problem für Sie in Bezug auf die Leistung dann sollten Sie einfach Profil , um herauszufinden, was die Zeit nimmt.

Wenn Sie möchten, um zu sehen, welche Auswirkungen die Sortierung / Kopieren ändern versuchen haben würde diese alternative:

// 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<_>)

ich einig vernünftigen Prozentsatz speedups im ers mit sehr großen (> Millionen) Eingangssequenzen aber nichts, wie eine Größenordnung. Ihre Laufleistung, wie immer, kann unterschiedlich sein.

Answer 2

Ein Unterschied von x2 ist nicht viel, wenn Sorten sind OS (n.log (n)).

Kleine Unterschiede in Datenstrukturen (z Optimierung für die Eingabe ist ICollection<T>) könnten diese Skala Unterschied.

Und F # ist derzeit Beta (nicht so viel Fokus auf die Optimierung vs. die Sprache und Bibliotheken immer rechts) sowie die Allgemeingültigkeit von F # Funktionen (mit Unterstützung für Teil Anwendung etc.) zu einem leichten führen könnte verlangsamen Geschwindigkeit in anrufen: mehr als genug für die verschiedenen berücksichtigen.