Проект повторного восстановления для меня заключается в том, чтобы внедрить конвейеры передачи данных на основе push в F #.Push-конвейеры проще и быстрее, чем pull-конвейеры, такие как LINQ (хотя они не имеют всех возможностей pull-конвейеров).
Что-то, что меня несколько озадачило, так это то, что я, кажется, не реализую push-конвейерв C # это эффективно, как мои push-конвейеры в F #.Я ищу информацию о том, как приблизить мою реализацию C # к F #.
Простой push-конвейер в F # можно представить так:
type Receiver<'T> = 'T -> unit
type Stream<'T> = Receiver<'T> -> unit
В C # мы могли бы написать это:
public delegate void Receiver<in T>(T v);
public delegate void Stream<out T>(Receiver<T> r);
Идея здесь заключается в том, что Stream<> - это функция, которая предоставляет получателю значений вызов приемника со всеми значениями в потоке.
Это позволяет нам определить mapaka ´Select`, например, в F #:
let inline map (m : 'T -> 'U) (s : Stream<'T>) : Stream<'U> =
fun r -> s (fun v -> r (m v))
C #:
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 (C #) и 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 начинает тянуть конвейер данныхсамый медленныйЭто ожидаемо.
Чего не ожидается, так это то, что, по-видимому, push-конвейер F # имеет в 3 раза меньше служебных данных, чем конвейер C #, несмотря на очень похожую реализацию и использование аналогичным образом.
Как мнеизменить конвейер данных C # так, чтобы он соответствовал или заменял конвейер данных 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%лучше, чем моя потоковая библиотека C #.
Интересно видеть, что inline оказывает такое глубокое влияние на производительность, когда единственное, что встроено, - это создание конвейера обратного вызова.После построения конвейер обратного вызова должен выглядеть точно так же.
Обновление 2018-06-24
Я решил подробно рассмотреть, в чем разница между F # иКонвейер данных C #.
Вот как выглядит код F для объединенного кода для Filter(fun v -> v &&& 1L = 0L):
; 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
Единственная реальная жалоба в отношении этого кода состоит в том, что джиттер не смог встроить хвостовой вызови мы заканчиваем виртуальным хвостовым вызовом.
Давайте посмотрим на тот же конвейер данных в 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
По сравнению с конвейером данных F # легко увидеть, что приведенный выше код дороже:
- F # встроил тестовую функцию, таким образом, избегая виртуального вызова (но почему джиттер не может унаследовать этот вызов и встроить его для нас?)
- F # использует хвостовые вызовы, которые в этомКейс в конечном итоге более эффективен, потому что мы просто выполняем виртуальный переход, а не виртуальный вызов для следующего шага
- В коде F # с перекрещиванием меньше прелюдии / эпилога, возможно из-за хвостового вызова?
- Есть Переадресация перехода между шагами в конвейере для сопряженного кода C #.
- Код C # использует делегаты, а не абстрактные классы.Кажется, что вызов делегата немного более эффективен, чем вызов абстрактного класса.
В 64-битном режиме кажется, что основное преимущество в производительности достигается за счет
- F #, встроенного в тестовую лямбду
- F # с использованием хвостового вызова (это не так для 32-битной системы, где хвостовой вызов убивает производительность)
Мы видим, что шаги конвейеров данных F # не встроены, это встроенный код построения конвейера данных.Это, однако, кажется, дает некоторые преимущества в производительности.Возможно, из-за того, что информация легче доступна для джиттера?
Чтобы улучшить производительность конвейера C #, мне кажется, что мне нужно структурировать мой код C # так, чтобы джиттер искажал и вставлял вызовы.У джиттера есть эти возможности, но почему они не применяются?
Можно ли структурировать мой код 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
Полная библиотека 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;
}
}
}