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.