Как улучшить push-конвейер данных в С# для соответствия F # в производительности
Рекуперация проекта для домашних животных для меня заключается в реализации push-based конвейеров данных в F #. Push-конвейеры проще и быстрее, чем тянуть трубопроводы, такие как LINQ (хотя они не имеют всех возможностей тянущих трубопроводов).
Что-то, что надвигало меня на некоторое время, заключается в том, что я, похоже, не реализую push-конвейер на С#, который эффективен, как мои push-конвейеры в F #. Я ищу информацию о том, как приблизить реализацию С# к F #.
Простой push-конвейер в F # может быть представлен следующим образом:
type Receiver<'T> = 'T -> unit
type Stream<'T> = Receiver<'T> -> unit
В С# мы могли бы написать следующее:
public delegate void Receiver<in T>(T v);
public delegate void Stream<out T>(Receiver<T> r);
Идея здесь заключается в том, что Stream<> - это функция, которая задавала приемник значений, вызывающий приемник со всеми значениями в потоке.
Это позволяет нам определить map akaSelect ', как это в F #:
let inline map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
fun r -> s (fun v -> r (m v))
С#:
public static Stream<U> Map<T, U>(this Stream<T> t, Func<T, U> m) =>
r => t(v => r(m(v)));
Мы можем реализовать другие функции, пока мы не сможем определить конвейер данных, который проверяет накладные расходы.
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()
В этом конвейере каждая операция очень дешевая, поэтому любые накладные расходы из базовой реализации должны появляться, когда мы ее измеряем.
При сравнении 4 различных конвейеров данных, императивных (на самом деле не конвейер, но там для проверки работоспособности), trivialpush, trivialpush (С#) и linq - это числа на.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
Императивное решение быстрее, и LINQ начинает тянуть канал данных, который является самым медленным. Это ожидается.
То, что не ожидалось, заключается в том, что, кажется, F # push-конвейер имеет на 3 раза меньше накладных расходов, чем конвейер С#, несмотря на очень похожую реализацию и используется аналогичным образом.
Как изменить конвейер данных С# так, чтобы он соответствовал или заменял конвейер данных F #? Я хочу, чтобы API конвейера данных был примерно таким же.
Обновление 2018-06-18
@scrwtp спросил, что произойдет, если я удалю inline в F #. Теперь я добавил inline для того, чтобы получить sum работы по назначению (в F # inline разрешено использование более продвинутых генериков)
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
Это значительно замедляет версию F #, но по-прежнему на 50% лучше, чем моя библиотека потока С#.
Интересно видеть, что inline оказывает такое глубокое влияние на производительность, когда единственное, что является встроенным, - это создание конвейера обратного вызова. Когда-то созданный конвейер обратного вызова должен выглядеть точно так же.
Обновление 2018-06-24
Я решил подробно изучить, в чем разница между конвейером данных F # и С#.
Вот как код jitted для Filter(fun v → v &&& 1L = 0L) ищет 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
Единственная настоящая большая жалоба на этот код заключается в том, что джиттер не смог встроить хвостовой вызов, и мы закончили виртуальный хвостовой вызов.
Давайте посмотрим на тот же конвейер данных в С#
; 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
Сравнивая конвейер данных F #, легко видеть, что вышеописанный код дороже:
- F # встроила тестовую функцию, тем самым избегая виртуального вызова (но почему не может джиттер девиртуализировать этот вызов и встроить его для нас?)
- F # использует хвостовые вызовы, которые в этом случае становятся более эффективными, потому что мы просто делаем виртуальный прыжок, а не виртуальный вызов на следующий шаг
- В коде F # jitted есть меньше прелюдии/эпилога, возможно, из-за хвоста?
- Существует переадресация между шагом в конвейере для кода с кодом С#.
- Код С# использует делегаты, а не абстрактные классы. Кажется, что вызов делегата немного более эффективен, чем вызов абстрактного класса.
В 64-битном режиме кажется, что основные преимущества производительности
- F # встраивание тестовой лямбда
- F # с использованием хвостового вызова (это неверно для 32 бит, когда хвостовой вызов убивает производительность)
Мы видим, что шаги конвейеров данных F # не вложены, это построение кода конвейера данных, который является встроенным. Однако, похоже, это дает некоторые преимущества в плане производительности. Возможно, потому что информация легче доступна для джиттера?
Чтобы улучшить производительность конвейера С#, мне кажется, что мне нужно структурировать код С#, чтобы джиттер девиртуализировал и ввел вызовы. У дрожания есть эти возможности, но почему они не применяются?
Я могу структурировать свой код F # так, чтобы хвостовые звонки могли быть девиртуализированы вложенными?
Полная консольная программа 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
Полная библиотека С#:
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;
}
}
}
Ответы
Ответ 1
Компилятор F # иногда выполняет встроенные функции без явных инструкций для этого. Вы можете аннотировать функции с помощью [<MethodImpl(MethodImplOptions.NoInlining)>] чтобы предотвратить это.
Обновление вашего TrivialStream следующим образом:
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
а затем обновить сам тест следующим образом:
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
При запуске в виде 32-разрядного приложения это приводит к запуску F #, который на самом деле медленнее, чем версия С#. Существует еще некоторое странное поведение с хвостовыми вызовами для 32-битной версии.
Для 64-битной версии эти изменения приводят версии F # и С# в пределах 15% друг от друга.
Если вы замените Receiver F # и Stream для делегатов С# (или просто Action<'t> и Action<Action<'t>>), то производительность этих двух примерно эквивалентна, поэтому я подозреваю, что есть дополнительные оптимизации, используя FSharpFunc которые играют.
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
Вы можете применить небольшую часть оптимизаций компилятора F # к С#, аннотируя свои методы с помощью [MethodImpl(MethodImplOptions.AggressiveInlining)], но это лишь незначительное улучшение.
