c# - ordenacion - ordenamiento por seleccion ejercicios

Cómo mejorar un flujo de datos de inserción en C#para que coincida con F#en el rendimiento

Question

Un nuevo proyecto de mascota para mí es implementar líneas de datos basadas en empuje en F #. Las tuberías de empuje son más simples y más rápidas que las tuberías de extracción como LINQ (aunque no tienen todas las capacidades de las tuberías de extracción).

Algo que me desconcertó por un tiempo es que no parece que esté implementando una canalización de inserción en C # que sea tan eficiente como mis tuberías de inserción en F #. Estoy buscando información sobre cómo acercar mi implementación de C # a F #.

Una simple tubería de empuje en F # se puede representar así:

type Receiver<''T> = ''T -> unit
type Stream<''T> = Receiver<''T> -> unit

En C # podríamos escribir esto:

public delegate void Receiver<in T>(T v);
public delegate void Stream<out T>(Receiver<T> r);

La idea aquí es que un Stream<> es una función que, dado un receptor de valores, llama al receptor con todos los valores en el stream.

Esto nos permite definir un map conocido como ''Seleccionar'' como este en F #:

let inline map (m : ''T -> ''U) (s : Stream<''T>) : Stream<''U> =
fun r -> s (fun v -> r (m v))

DO#:

public static Stream<U> Map<T, U>(this Stream<T> t, Func<T, U> m) =>
r => t(v => r(m(v)));

Podemos implementar otras funciones hasta que podamos definir un flujo de datos que pruebe la sobrecarga.

let trivialTest n =
TrivialStream.range 0 1 n
|> TrivialStream.map int64
|> TrivialStream.filter (fun v -> v &&& 1L = 0L)
|> TrivialStream.map ((+) 1L)
|> TrivialStream.sum
let trivialTestCs n =
Stream
.Range(0,1,n)
.Map(fun v -> int64 v)
.Filter(fun v -> v &&& 1L = 0L)
.Map(fun v -> v + 1L)
.Sum()

En este proceso, cada operación es muy barata, por lo que cualquier gasto general de la implementación subyacente debería aparecer cuando lo medimos.

Cuando se comparan 4 líneas de datos diferentes, es imperativo (no es realmente una línea de trabajo pero hay que verificar la implementación), trivialpush, trivialpush (C #) y linq estos son los números en .NET 4.7.1 / x64:

Running imperative with total=100000000, outer=1000000, inner=100 ...
... 87 ms, cc0=0, cc1=0, cc2=0, result=2601L
Running trivialpush with total=100000000, outer=1000000, inner=100 ...
... 414 ms, cc0=53, cc1=0, cc2=0, result=2601L
Running trivialpush(C#) with total=100000000, outer=1000000, inner=100 ...
... 1184 ms, cc0=322, cc1=0, cc2=0, result=2601L
Running linq with total=100000000, outer=1000000, inner=100 ...
... 2080 ms, cc0=157, cc1=0, cc2=0, result=2601L

La solución imperativa es la más rápida y LINQ comenzar un flujo de datos de extracción es la más lenta. Esto es lo esperado.

Lo que no se espera es que parezca que la canalización de inserción de F # tiene una sobrecarga de 3 veces menos que la tubería de C # a pesar de tener una implementación muy similar y utilizada de manera similar.

¿Cómo cambio el flujo de datos de C # para que coincida o reemplace el flujo de datos de F #? Quiero que la API del flujo de datos sea aproximadamente la misma.

Actualización 2018-06-18

@scrwtp preguntó qué sucede si elimino inline en F #. Ahora agregué inline para obtener el trabajo de sum como estaba previsto (en F # inline permite genéricos más avanzados)

Running imperative with total=100000000, outer=1000000, inner=100 ...
... 85 ms, cc0=0, cc1=0, cc2=0, result=2601L
Running trivialpush with total=100000000, outer=1000000, inner=100 ...
... 773 ms, cc0=106, cc1=0, cc2=0, result=2601L
Running trivialpush(C#) with total=100000000, outer=1000000, inner=100 ...
... 1181 ms, cc0=322, cc1=0, cc2=0, result=2601L
Running linq with total=100000000, outer=1000000, inner=100 ...
... 2124 ms, cc0=157, cc1=0, cc2=0, result=2601L

Esto ralentiza significativamente la versión de F # pero aún funciona un 50% mejor que mi biblioteca de secuencias de C #.

Es interesante ver que la inline tiene un impacto tan profundo en el rendimiento cuando lo único que está en línea es la creación de la canalización de devolución de llamada. Una vez construido, el flujo de devolución de llamada debe verse exactamente igual.

Actualización 2018-06-24

Decidí analizar en detalle cuál es la diferencia entre el flujo de datos F # y C #.

Aquí se muestra cómo el código adaptado para el Filter(fun v -> v &&& 1L = 0L) busca F #:

; TrivialPush, F#, filter operation
00007ffc`b7d01160 488bc2 mov rax,rdx
; F# inlines the filter function: (fun v -> v &&& 1 = 0L)
; Is even?
00007ffc`b7d01163 a801 test al,1
00007ffc`b7d01165 7512 jne 00007ffc`b7d01179
; Yes, call next chain in pipeline
; Load pointer next step in pipeline
00007ffc`b7d01167 488b4908 mov rcx,qword ptr [rcx+8]
; Load Object Method Table
00007ffc`b7d0116b 488b01 mov rax,qword ptr [rcx]
; Load Table of methods
00007ffc`b7d0116e 488b4040 mov rax,qword ptr [rax+40h]
; Load address of Invoke
00007ffc`b7d01172 488b4020 mov rax,qword ptr [rax+20h]
; Jump to Invoke (tail call)
00007ffc`b7d01176 48ffe0 jmp rax
; No, the number was odd, bail out
00007ffc`b7d01179 33c0 xor eax,eax
00007ffc`b7d0117b c3 ret

La única gran queja real sobre este código es que jitter no pudo alinear la llamada de cola y terminamos con una llamada de cola virtual.

Echemos un vistazo a la misma tubería de datos en C #

; TrivialPush, C#, filter operation
; Method prelude
00007ffc`b75c1a10 57 push rdi
00007ffc`b75c1a11 56 push rsi
; Allocate space on stack
00007ffc`b75c1a12 4883ec28 sub rsp,28h
00007ffc`b75c1a16 488bf1 mov rsi,rcx
00007ffc`b75c1a19 488bfa mov rdi,rdx
; Load pointer test delegate (fun v -> v &&& 1 = 0L)
00007ffc`b75c1a1c 488b4e10 mov rcx,qword ptr [rsi+10h]
; Load Method Table
00007ffc`b75c1a20 488b4110 mov rax,qword ptr [rcx+10h]
; Setup this pointer for delegate
00007ffc`b75c1a24 488d4808 lea rcx,[rax+8]
00007ffc`b75c1a28 488b09 mov rcx,qword ptr [rcx]
00007ffc`b75c1a2b 488bd7 mov rdx,rdi
; Load address to Invoke and call
00007ffc`b75c1a2e ff5018 call qword ptr [rax+18h]
; Did filter return true?
00007ffc`b75c1a31 84c0 test al,al
00007ffc`b75c1a33 7411 je 00007ffc`b75c1a46
; Yes, call next step in data pipeline
; Load Method Table
00007ffc`b75c1a35 488b4608 mov rax,qword ptr [rsi+8]
00007ffc`b75c1a39 488d4808 lea rcx,[rax+8]
; Setup this pointer for delegate
00007ffc`b75c1a3d 488b09 mov rcx,qword ptr [rcx]
00007ffc`b75c1a40 488bd7 mov rdx,rdi
; Load address to Invoke and call
00007ffc`b75c1a43 ff5018 call qword ptr [rax+18h]
; Method prelude epilogue
00007ffc`b75c1a46 90 nop
00007ffc`b75c1a47 4883c428 add rsp,28h
00007ffc`b75c1a4b 5e pop rsi
00007ffc`b75c1a4c 5f pop rdi
00007ffc`b75c1a4d c3 ret
; (fun v -> v &&& 1 = 0L) redirect
00007ffc`b75c0408 e963160000 jmp 00007ffc`b75c1a70
; (fun v -> v &&& 1 = 0L)
00007ffc`b75c1a70 488bc2 mov rax,rdx
; Is even?
00007ffc`b75c1a73 a801 test al,1
00007ffc`b75c1a75 0f94c0 sete al
; return result
00007ffc`b75c1a78 0fb6c0 movzx eax,al
; We are done!
00007ffc`b75c1a7b c3 ret

En comparación con la tubería de datos de F #, es fácil ver que el código anterior es más caro:

1. F # incorporó la función de prueba evitando así una llamada virtual (pero, ¿por qué el jitter no puede desvirtualizar esta llamada e integrarla para nosotros?)
2. F # usa llamadas de cola que en este caso terminan siendo más eficientes porque solo hacemos un salto virtual en lugar de una llamada virtual al siguiente paso
3. ¿Hay menos preludio / jugueteando con el epílogo en el código j # F, tal vez debido a la cola?
4. Hay un salto de redireccionamiento entre el paso en la tubería para el código j # titulado.
5. El código C # usa delegados en lugar de clases abstractas. Parece que la invocación de delegado es ligeramente más eficiente que la invocación de clase abstracta.

En el modo de 64 bits parece que los principales beneficios de rendimiento provienen de

1. F # alineando la prueba lambda
2. F # usando la llamada de cola (esto no es cierto para 32 bits donde la llamada de cola mata el rendimiento)

Vemos que los pasos de las tuberías de datos F # no están en línea, es el código de creación de la línea de datos que está en línea. Sin embargo, eso parece dar algunos beneficios de rendimiento. ¿Quizás porque la información está más fácilmente disponible para el jitter?

Para mejorar el rendimiento de la tubería de C #, parece que necesito estructurar mi código de C # para que el jitter desvirtúe y alinee las llamadas. El jitter tiene estas capacidades, pero ¿por qué no se aplican?

¿Existe un código de F # que pueda estructurar para que las llamadas de la cola puedan desvirtuarse y estar en línea?

El programa completo de consola F #:

module TrivialStream =
// A very simple push stream
type Receiver<''T> = ''T -> unit
type Stream<''T> = Receiver<''T> -> unit
module Details =
module Loop =
let rec range s e r i = if i <= e then r i; range s e r (i + s)
open Details
let inline range b s e : Stream<int> =
fun r -> Loop.range s e r b
let inline filter (f : ''T -> bool) (s : Stream<''T>) : Stream<''T> =
fun r -> s (fun v -> if f v then r v)
let inline map (m : ''T -> ''U) (s : Stream<''T>) : Stream<''U> =
fun r -> s (fun v -> r (m v))
let inline sum (s : Stream<''T>) : ''T =
let mutable ss = LanguagePrimitives.GenericZero
s (fun v -> ss <- ss + v)
ss
module PerformanceTests =
open System
open System.Diagnostics
open System.IO
open System.Linq
open TrivialStreams
let now =
let sw = Stopwatch ()
sw.Start ()
fun () -> sw.ElapsedMilliseconds
let time n a =
let inline cc i = GC.CollectionCount i
let v = a ()
GC.Collect (2, GCCollectionMode.Forced, true)
let bcc0, bcc1, bcc2 = cc 0, cc 1, cc 2
let b = now ()
for i in 1..n do
a () |> ignore
let e = now ()
let ecc0, ecc1, ecc2 = cc 0, cc 1, cc 2
v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2
let trivialTest n =
TrivialStream.range 0 1 n
|> TrivialStream.map int64
|> TrivialStream.filter (fun v -> v &&& 1L = 0L)
|> TrivialStream.map ((+) 1L)
|> TrivialStream.sum
let trivialTestCs n =
Stream
.Range(0,1,n)
.Map(fun v -> int64 v)
.Filter(fun v -> v &&& 1L = 0L)
.Map(fun v -> v + 1L)
.Sum()
let linqTest n =
Enumerable
.Range(0, n + 1)
.Select(fun v -> int64 v)
.Where(fun v -> v &&& 1L = 0L)
.Select(fun v -> v + 1L)
.Sum()
let imperativeTest n =
let rec loop s i =
if i >= 0L then
if i &&& 1L = 0L then
loop (s + i + 1L) (i - 1L)
else
loop s (i - 1L)
else
s
loop 0L (int64 n)
let test () =
printfn "Running performance tests..."
let testCases =
[|
"imperative" , imperativeTest
"trivialpush" , trivialTest
"trivialpush(C#)" , trivialTestCs
"linq" , linqTest
|]
do
// Just in case tiered compilation is activated on dotnet core 2.1+
let warmups = 100
printfn "Warming up..."
for name, a in testCases do
time warmups (fun () -> a warmups) |> ignore
let total = 100000000
let outers =
[|
10
1000
1000000
|]
for outer in outers do
let inner = total / outer
for name, a in testCases do
printfn "Running %s with total=%d, outer=%d, inner=%d ..." name total outer inner
let v, ms, cc0, cc1, cc2 = time outer (fun () -> a inner)
printfn " ... %d ms, cc0=%d, cc1=%d, cc2=%d, result=%A" ms cc0 cc1 cc2 v
printfn "Performance tests completed"
[<EntryPoint>]
let main argv =
PerformanceTests.test ()
0

La biblioteca completa de C #:

namespace TrivialStreams
{
using System;
public delegate void Receiver<in T>(T v);
public delegate void Stream<out T>(Receiver<T> r);
public static class Stream
{
public static Stream<int> Range(int b, int s, int e) =>
r =>
{
for(var i = 0; i <= e; i += s)
{
r(i);
}
};
public static Stream<T> Filter<T>(this Stream<T> t, Func<T, bool> f) =>
r => t(v =>
{
if (f(v)) r(v);
});
public static Stream<U> Map<T, U>(this Stream<T> t, Func<T, U> m) =>
r => t(v => r(m(v)));
public static long Sum(this Stream<long> t)
{
var sum = 0L;
t(v => sum += v);
return sum;
}
}
}

Answer 1

El compilador de F # a veces integrará funciones sin instrucciones explícitas para hacerlo. Puede anotar funciones con [<MethodImpl(MethodImplOptions.NoInlining)>] para evitar esto.

Actualizando tu TrivialStream esta manera:

open System.Runtime.CompilerServices
[<MethodImpl(MethodImplOptions.NoInlining)>]
let range b s e : Stream<int> =
fun r -> Loop.range s e r b
[<MethodImpl(MethodImplOptions.NoInlining)>]
let filter (f : ''T -> bool) (s : Stream<''T>) : Stream<''T> =
fun r -> s (fun v -> if f v then r v)
[<MethodImpl(MethodImplOptions.NoInlining)>]
let map (m : ''T -> ''U) (s : Stream<''T>) : Stream<''U> =
fun r -> s (fun v -> r (m v))
[<MethodImpl(MethodImplOptions.NoInlining)>]
let sum (s : Stream<''T>) : ''T =
let mutable ss = LanguagePrimitives.GenericZero
s (fun v -> ss <- ss + v)
ss

y luego actualizando la prueba como esta:

open System.Runtime.CompilerServices
[<MethodImpl(MethodImplOptions.NoInlining)>]
let parseToInt64 = int64
[<MethodImpl(MethodImplOptions.NoInlining)>]
let filterImpl = fun v -> v &&& 1L = 0L
[<MethodImpl(MethodImplOptions.NoInlining)>]
let mapImpl = ((+) 1L)
let trivialTest n =
TrivialStream.range 0 1 n
|> TrivialStream.map parseToInt64
|> TrivialStream.filter filterImpl
|> TrivialStream.map mapImpl
|> TrivialStream.sum

Cuando se ejecuta como una aplicación de 32 bits, esto se traduce en una ejecución de F # que en realidad es más lenta que la versión C #. Hay un comportamiento extraño adicional en las llamadas de cola para la versión de 32 bits.

Para la versión de 64 bits, estos cambios hacen que las versiones F # y C # estén dentro del 15% entre sí.

Si intercambias F # Receiver y Stream por los delegados de C # (o simplemente Action<''t> y Action<Action<''t>> ), el rendimiento de los dos es aproximadamente equivalente, por lo que sospecho que hay optimizaciones adicionales al usar FSharpFunc que están en juego.

 open TrivialStreams
// A very simple push stream
//type Receiver<''T> = ''T -> unit
//type Stream<''T> = Receiver<''T> -> unit
module Details =
module Loop =
let rec range s e (r:Receiver<''t> ) i = if i <= e then r.Invoke i; range s e r (i + s)
open Details
open System.Runtime.CompilerServices
[<MethodImpl(MethodImplOptions.NoInlining)>]
let range b s e =
Stream<''t>(fun r -> (Loop.range s e r b))
[<MethodImpl(MethodImplOptions.NoInlining)>]
let filter f (s : Stream<''T>) =
Stream<''T>(fun r -> s.Invoke (fun v -> if f v then r.Invoke v))
[<MethodImpl(MethodImplOptions.NoInlining)>]
let map m (s : Stream<''T>) =
Stream<''U>(fun r -> s.Invoke (fun v -> r.Invoke (m v)))
[<MethodImpl(MethodImplOptions.NoInlining)>]
let sum (s : Stream<''T>) : ''T =
let mutable ss = LanguagePrimitives.GenericZero
s.Invoke (fun v -> ss <- ss + v)
ss

Puede aplicar una pequeña parte de las optimizaciones del compilador F # a C # anotando sus métodos con la propiedad [MethodImpl(MethodImplOptions.AggressiveInlining)] , pero esto es solo una mejora marginal.