¿Por qué es mucho más lento que Seq.sortBy IEnumerable de LINQ método de extensión .OrderBy F # 's?

Question

He escrito recientemente un pedazo de código para leer algunos datos de un archivo, almacenarlo en una tupla y ordenar todos los datos recogidos por el primer elemento de la tupla. Después de algunas pruebas que me he dado cuenta de que el uso de Seq.sortBy (y Array.sortBy) es extremadamente lento que el uso IEnumerable.OrderBy. A continuación se presentan dos fragmentos de código que debe mostrar el comportamiento que estoy hablando:

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

y

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)

En un archivo que contiene 100000 líneas hechas de dos dobles, en mi equipo toma la última versión de más de dos veces más largo que el primero (no hay mejoras se obtienen si se utiliza Array.sortBy). Ideas?

Answer 1

f # aplicación utiliza una comparación estructural de la clave resultante.

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

(también clasificar)

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

tanto Operators.compare y la ComparisonIdentity.Structural.Compare convertido (con el tiempo)

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

pero la ruta a esto para el operador es completamente en línea, por lo que el compilador JIT va a terminar la inserción de una instrucción directa comparación doble con ninguna sobrecarga de invocación de método adicional, excepto para la invocación delegado (necesario en ambos casos, de todos modos).

El sortBy utiliza un comparador de modo pasará a través de una llamada de método virtual adicional, sino que se trata básicamente de la misma.

En comparación la función OrdenarPor también debe ir a través de llamadas a métodos virtuales para la igualdad (Usando EqualityComparer<T>.Default) pero la diferencia significativa es que se ordena en su lugar y utiliza el búfer creado para esto como el resultado. En comparación, si se echa un vistazo en el sortBy verá que se ordena la lista (no en su lugar, utiliza la StableSortImplementation que parece estar ordenamiento por mezcla) y luego crea una copia de la misma como una nueva matriz. Esta copia adicional (dado el tamaño de los datos de entrada) es probablemente la principal causa de la desaceleración, aunque las implementaciones diferentes ordenar pueden también tener un efecto.

Una vez dicho todo esto es adivinando . Si esta área es una preocupación para usted en términos de rendimiento, entonces debería simplemente perfil para averiguar lo que está tomando el tiempo.

Si desea ver el efecto que el cambio de clasificación / copia tendría que probar esta alternativa:

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

consigo algunas aceleraciones porcentaje razonable dentro de la réplica con secuencias muy grandes (> millones) de entrada, pero nada como un orden de magnitud. Su kilometraje, como siempre, puede variar.

Answer 2

A diferencia de x2 no es mucho cuando tipo son O (n.log (n)).

Las pequeñas diferencias en las estructuras de datos (por ejemplo, la optimización por ser de entrada ICollection<T>) podrían hacer de esta escala de diferencia.

Y F # es actualmente Beta (no tanto esfuerzo de optimización vs conseguir el lenguaje y las bibliotecas derecha), además de la generalidad de F funciones # (soporte de aplicaciones, etc. parcial) podría dar lugar a una ligera desaceleración en llamar a la velocidad: más que suficiente para dar cuenta de lo diferente.