对我来说,一个经常发生的宠物项目是在F#中实现基于推式的数据管道。推式管道比LINQ之类的拉式管道更简单,更快捷(尽管它们不具备拉式管道的全部功能)。
令我困扰不已的是,我似乎没有在C#中实现推送管道,而在F#中它却像在我的推送管道中那样高效。我正在寻找有关如何使C#实现更接近F#的意见。
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<>
是一个函数,给定值的接收者调用流中所有值的接收器。这使我们可以在F#中定义
map
aka«Select`: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开始拉取数据管道是最慢的。这是预期的。
出乎意料的是,尽管实现方式和使用方式相似,但F#推送管道的开销似乎比C#管道少3倍。
如何更改C#数据管道,以使其匹配或取代F#数据管道?我希望数据管道的API大致相同。
更新2018-06-18
@scrwtp询问如果我在F#中删除
inline
会发生什么。现在,我添加了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#版本的速度,但仍比我的C#流库好50%。
有趣的是,当内联的唯一内容是建立回调管道时,
inline
对性能具有如此深远的影响。一旦建立,回调管道应该看起来完全一样。更新2018-06-24
我决定详细研究F#和C#数据管道之间的区别。
这是
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
关于此代码的唯一真正的大提示是,抖动未能内联尾调用,而我们最终得到了虚拟尾调用。
让我们看看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#数据管道相比,可以很容易地看到上面的代码更昂贵:
在64位模式下,主要的性能优势似乎来自
我们看到没有内联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;
}
}
}
最佳答案
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#运行实际上比C#版本慢。对于32位版本的尾部调用,还有一些其他奇怪的行为。
对于64位版本,这些更改使F#和C#版本之间的误差不超过15%。
如果将F#
Receiver
和Stream
交换为C#委托(delegate)人(或只是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
您可以使用
[MethodImpl(MethodImplOptions.AggressiveInlining)]
属性为方法添加注释,从而将F#编译器优化的一小部分应用于C#,但这只是一个小小的改进。
关于c# - 如何在C#中改进推送数据管道以使其性能与F#相匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50776674/