The frustrating state of tails calls in .NET #2191
Comments
Dotnet-GitSync-Bot
added
the
untriaged
jkotas
added
the
area-CodeGen-coreclr
|
Thanks sound great you are working on tail calls. The PR mentions that there is no need to change x86 tail call because that is already fast. From my my experience of x86 tail calls might not be as bad as x64 but it's IMHO not fast. I find that x86 tail call makes the simple pushstream pipeline take 3.6 sec in my quick benchmark vs x86 non-tail that take 0.6 sec. With that overhead I would still try to avoid the overhead of tail calls in the push stream example. |
|
It has been a while since I looked at x86 but my impression when I did was that there was not much that could be done to make the general case faster. This is because the calling convention in x86 means that we have to adjust stack pointers and move arguments and the return pointer. There is no easy workaround to make this faster; it is slower simply because it has more stuff to do. The state of tailcalls is that it is not always an optimization, so compilers will simply not do the transformation when this is the case. But F# is very aggressive at emitting tail. because true tailcalls are sometimes required for correct functional programs. Omitting the prefix simply makes the code incorrect, so that is not an option for the compiler. In your particular case, the program with the match might be faster, but from the perspective of the F# compiler it is an incorrect transformation. And from the perspective of the runtime, the F# compiler has told it that it needs to do a tailcall, so the runtime has to obey this and unfortunately it needs to jump through hoops to do this in some cases–there simply is more work to do. The work in #341 will make x64 quite a bit faster and add support for tailcalls for other platforms, but it will still be slower than not having tailcalls in the general case. However it will make programs relying on tail. correct. So to sum up I do not think it is possible to make tail. calls always faster than normal calls. The best you can do is expose some way in F# to let the programmer tell the compiler that a tailcall is not required for a call site. But otherwise you are choosing between fast programs (without tail.) and correct programs (with tail.), and overhead in some cases is to be expected. |
|
I understand from the respect of jitter it has to implement tail correctly but as for correctness isn't the problem to prevent long tail call chains from running out stackspace? Or are there other differences I am not aware of? I guess I should register an issue in the F# compiler to allow us suppress .tail attributes reliably. |
|
It is a subte area, with much misunderstanding and confusion. I guess, I think, there should be two tail call operators: Presently there is only #2 which I believe F# outputs aggressively, and C# outputs never. Maybe the effort is better spent on the compiler frontends noticing near tailcall opportunities and advising developer to change his code a little. I realize these compilers are not that sophisticated. Maybe the JIT could issue such warnings, but it feels like the wrong time. Even C++ compilers don't do this, but maybe they should. Also tailcall serves two purposes, from the two ideas above.
|
Right, it is not easy for the jit to give feedback to the developer. There are tools like the Inlining Analyzer that show some promise here. I am not sure how hard it would be to pull something like this off in F#. The jit relays tail call outcomes back to the runtime, and these end up as ETL records if you enable the jit tracing keyword (say, by checking the normally unchecked "Jit Inlining" checkbox in perfview). There isn't a nice display for this that I know of; perhaps in the short run we can get something added in perfview or a tail call diagnoser added to BenchmarkDotNet.
|
|
The issue I see for a library LINQ-like library that relies on tail calls is that the user of the library will sometimes get really good performance and sometimes really bad performance. They might not be the user that checks ETL records for what is wrong and even if they do they can't really do much to eliminate the tail calls as that is part of the library. This means that as a LINQ-library developer I need to protect my user from the bad outliers and I have to remove the tail calls somehow. However, as library developed the ETL records are interesting, thanks for sharing. Perhaps it's too much to ask for but perhaps you could enlighten me a bit on the complexities of making a tail-call so I learn to appreciate it :) |
|
The basic reason some things go slow, is that Roughly speaking, an "easy" one has a key characteristic:
Before working on this area, I would have deemed "difficult" There are also criteria, like passing the address of a local: And then, depending on ABI details, passing value types by value: x86 and ARM pass structs by value "inline", ARM64 and AMD64 pass the address As to how the difficult/slow ones work, see here, it is complicated: https://github.com/dotnet/runtime/blob/master/docs/design/features/tailcalls-with-helpers.md As to how the fast/easy ones work, it is really easy. There are other cases, like cannot tailcall within try/finally or try/catch. There is essentially no downside to the easy/fast cases. I have seen code that is broken by that, because it does runtime stack walks, but it is bad and rare code imho.
|
|
Ah, there already is a tail call diagnoser for BenchmarkDotNet, though I can't figure out how to get it to compile on this example. cc @adamsitnik |
|
In full framework (not Core) JIT could detect tail recursion in IL and generate iteration instead of recursion even without Is this still the same behaviour for Core JIT? And why only x64 Release? |
It is an optimization. The JIT does 99% of optimizations in Release only.
For compatibility, the 32-bit JIT for .NET Framework is very different codebase from the 64-bit JIT. |
I got it running and shared it here: https://github.com/adamsitnik/TryNewDisassembler/tree/fsharpTailCalls git clone https://github.com/adamsitnik/TryNewDisassembler
cd TryNewDisassembler
checkout fsharpTailCalls
dotnet run -c Release -f netcoreapp3.0 --filter '*' --runtimes net461 netcoreapp3.0 |
|
Just FYI; tried the github project above and it reproduces the performance numbers I have seen. I learnt abit about BenchMarksDotNet as well from the code :) One interesting thing to note unrelated to the issue is that the push stream is 20% slower on dotnet core than on .net framework 🤔 I am personally totally ok losing frames, that's kind of the point IMHO :). Anyway, I am out of my league here but should/can the jitter be more aggressive on inlining tail calls due to the cost of the complex tail calls? |
|
@adamsitnik Thanks -- did not realize it required an extra package. When I run this the results look odd... more like it is looking at inlining events than tail call events. |
It has surprised me as well, to the point that I double-checked the source code to make sure that we sign up for the right events. We do: I am open to any suggestions that could improve the output. |
I think I ran into this problem before, and I believe it was an EventPipe issue. The events if you use the in-process events (like in PMI) were right back then. |
I think we can be more aggressive, but we also need to be careful; see notes in #12304. |
Aside from fixing whatever bug is reporting wrong-looking data, it would be good to surface the tail call type and tail prefix for successful tail calls; the "interesting" case is the one where we have a successful call with an explicit |
It looks like this issue is fixed in a newer version of
this is already possible, it's configurable via attribute optional parameter: [<TailCallDiagnoser(logFailuresOnly = false, filterByNamespace = false)>]@AndyAyersMS in the meantime you can use the following app. <Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFrameworks>netcoreapp2.1;netcoreapp2.2;netcoreapp3.0</TargetFrameworks>
</PropertyGroup>
<ItemGroup>
<Compile Include="Program.fs" />
</ItemGroup>
<ItemGroup>
<PackageReference Include="Microsoft.Diagnostics.Tracing.TraceEvent" Version="2.0.49" />
</ItemGroup>
</Project>module TailCall =
open System.Linq
// let inline push r v = match r v with () -> ()
// let inline push r v = r v
// Minimalistic PushStream
// A PushStream accepts a receiver function that will be called
// with each value in the PushStream
type 'T PushStream = ('T -> unit) -> unit
module PushStream =
let inline zero () = LanguagePrimitives.GenericZero
let inline push r v = r v
// Creates a PushStream with all integers from b to e (inclusive)
let inline fromRange b e r = for i = b to e do push r i
// Maps all values in ps using mapping function f
let inline map f ps r = ps (fun v -> push r (f v))
// Filters all values in ps using filter function f
let inline filter f ps r = ps (fun v -> if f v then push r v)
// Sums all values in ps
let inline sum ps = let mutable s = zero () in ps (fun v -> s <- s + v); s
module Tests =
open System
type Benchmarks () =
member val public Count = 100 with get, set
member x.SimpleImperativeTest () =
let mutable i = x.Count
let mutable sum = 0L
while i >= 0 do
let v = int64 i
i <- i - 1
if (v &&& 1L) = 0L then
sum <- sum + (v + 1L)
sum
member x.SimpleLinqTest () =
Enumerable.Range(0, x.Count)
.Select(int64)
.Where(fun v -> (v &&& 1L) = 0L)
.Select((+) 1L)
.Sum()
member x.SimplePushStreamTest () =
PushStream.fromRange 0 x.Count
|> PushStream.map int64
|> PushStream.filter (fun v -> (v &&& 1L) = 0L)
|> PushStream.map ((+) 1L)
|> PushStream.sum
member x.StructLinqStreamTest () =
Enumerable.Range(0, x.Count)
.Select(int64)
.Select(fun v -> struct ((v &&& 1L) = 0L, v))
.Select(fun struct (b, v) -> struct (b, v + 1L))
.Select(fun struct (b, v) -> if b then v else 0L)
.Sum()
member x.StructPushStreamTest () =
PushStream.fromRange 0 x.Count
|> PushStream.map int64
|> PushStream.map (fun v -> struct ((v &&& 1L) = 0L, v))
|> PushStream.map (fun struct (b, v) -> struct (b, v + 1L))
|> PushStream.map (fun struct (b, v) -> if b then v else 0L)
|> PushStream.sum
type ReflectionHelper () =
member x.UseReflectionToInvokeMethods (methodName : string) =
let typeInfo = typeof<ReflectionHelper>
let benchmarkType = typeInfo.Assembly.GetType(typeInfo.FullName.Replace("ReflectionHelper", "Benchmarks"))
let method = benchmarkType.GetMethod(methodName)
let instance = Activator.CreateInstance(benchmarkType)
method.Invoke(instance, null)
open TailCall.Tests
open System
open System.Diagnostics
open System.Threading
open System.Threading.Tasks
open Microsoft.Diagnostics.Tracing.Session
open Microsoft.Diagnostics.Tracing.Parsers
open Microsoft.Diagnostics.Tracing.Parsers.Clr
open Microsoft.Diagnostics.Tracing
[<EntryPoint>]
let main argv =
let currentProcessId = Process.GetCurrentProcess().Id
use session = new TraceEventSession("tailCallsSession")
session.EnableProvider(ClrTraceEventParser.ProviderGuid, TraceEventLevel.Verbose, uint64 ClrTraceEventParser.Keywords.JitTracing, options = null) |> ignore
let onMethodTailCallSucceeded = System.Action<MethodJitTailCallSucceededTraceData>(fun e ->
if e.ProcessID = currentProcessId then printfn "OK, callee: %s compiled: %s TailPrefix: %b TailCallType: %A" e.CalleeName e.MethodBeingCompiledName e.TailPrefix e.TailCallType
)
let onMethodTailCallFailed = System.Action<MethodJitTailCallFailedTraceData>(fun e ->
if e.ProcessID = currentProcessId then printfn "NOT, callee: %s compiled: %s FailReason: %A" e.CalleeName e.MethodBeingCompiledName e.FailReason
)
let onMethodTailCallFailedAnsi = System.Action<MethodJitTailCallFailedAnsiTraceData>(fun e ->
if e.ProcessID = currentProcessId then printfn "NOTa, callee: %s compiled: %s FailReason: %A" e.CalleeName e.MethodBeingCompiledName e.FailReason
)
session.Source.Clr.add_MethodTailCallSucceeded onMethodTailCallSucceeded
session.Source.Clr.add_MethodTailCallFailed onMethodTailCallFailed
session.Source.Clr.add_MethodTailCallFailedAnsi onMethodTailCallFailedAnsi
// we use reflection helper to make sure that the "Benchmarks" type is not JITed before the tracing has started
let sut = ReflectionHelper
let result1 = sut().UseReflectionToInvokeMethods("SimpleImperativeTest")
let result2 = sut().UseReflectionToInvokeMethods("SimpleLinqTest")
let result3 = sut().UseReflectionToInvokeMethods("SimplePushStreamTest")
let result4 = sut().UseReflectionToInvokeMethods("StructLinqStreamTest")
let result5 = sut().UseReflectionToInvokeMethods("StructPushStreamTest")
printfn "%A %A %A %A %A" result1 result2 result3 result4 result5
let action = System.Action(fun _ -> session.Source.Process() |> ignore)
let task = Task.Factory.StartNew(action, TaskCreationOptions.LongRunning)
// give it some time & wait for delayed events
let timeToSleep = TimeSpan.FromSeconds(10.0)
Thread.Sleep(timeToSleep)
0 // return an integer exit code |
|
Thanks @adamsitnik -- works well. Had to add in the namespace part to make sense of things, though: At any rate, we should try running the code here with the tail call changes from #341. Will put it on my todo list but may not get to it for a while. |
|
I ran the benchmark with the changes from #341. That change speeds up StructPushStreamTest 7-8 times. Here are the numbers ( I'm working with @jakobbotsch on getting #341 merged soon. |
|
Based on my reading of this issue, #341 will improve the situation a great deal, especially for F#. I don't see any other reason to keep this issue open, so I'm closing it. |
BruceForstall
removed
the
untriaged
ghost
locked as resolved and limited conversation to collaborators
The frustrating state of tails calls in .NET
I listened to Microsoft Language & Runtime Community standup on twitch
were they said they like "aggressive" well-informed feedback from the community
so I figured I bring up something that has been rubbing me the wrong way a long
time in .NET; tail call performance.
I am sure that has been discussed before but I am going to add more fuel to the debate.
Tails calls in .NET
In .NET it's possible that annotate calls with a
.tailattribute allowing thejitter to eliminate stack frames and thus avoiding to run out of stack space.
If you are a C# developer you probably never encountered tail calls as the C#
compiler as of now (AFAIK?) doesn't emit
.tailattributes (might change withtail return?).It's different for F# developers though where the compiler does emit
.tailattributes.
The problem
Avoiding running out stack space is a good thing so what's the problem?
The problem is the abysmal performance of tail calls in the general case.
Let me demonstrate by implementing a simple data pipeline based on push rather than pull (
IEnumerable<_>is pull based).For a simple data pipeline designed to detect the overhead of the pipeline the push stream shows some promising performance when comparing it to LINQ.
The imperative "pipeline" does the best as expected as there's no pipeline
overhead but the push stream is doing a lot better than LINQ. Great right?
Not so fast! If we add a second test which does the same thing in a slightly
different way then what happens?
Suddenly the push stream performance is abysmal.
We see the LINQ now performs 20x times better? What's going on?
Let's fix the problem using magic! Rewrite the
pushfunction from this:Replace it with this nonsense:
Now push stream compares favorably in all cases
What's going on?
The difference are the tail calls.
With the original
pushfunction the IL code to invoke the receiver function looks like this:The modified
pushfunction which doesn't change the meaning of the program at all the IL code looks like this:As the modified
push"looks" at the value (match) and then loads a new result this doesn't fit the pattern of a tail call. Thus the compiler doens't inject the.tailattribute.Why do
.tailcalls sometimes go fast and sometimes go really really slow?Let's look at the assembly code when
.tailcall executes quickly.Fast
.tailcalls (Yay!)So apart from the odd nop in the beginning and the usual vtable dance over
virtual functions (what are the conditions to make the jitter succeed with
devirtualizations?) it's quite ok. Actually suprisingly just 5x slower than the
fast imperative solution considering how much more junk happens in each step.
Let's look at the slow
.tailcallSlow
.tailcalls (Boo!)So, there's lot more setup here but this is because this function actually needs
a stackframe to store intermediate results. Also I suspect because the stackframe
is needed it has to call
coreclr!JIT_TailCallat the end which is the CPU hog.I don't know exactly what
coreclr!JIT_TailCalldoes but it does a lot whenstepping through the assembly code. However, my suspicion is that its purpose is
eliminate the stackframe and call the next function. While it eliminates the stackframe it adds about 60x overhead to the
PushStreampipeline.Finally let's look at the code for the modified
pushfunction to get backpredictable performance
Predictable calls
Because juggling with struct tuple is more complex than the first example it is
more complex code but at least the next step in the pipeline is invoked without
the need of
coreclr!JIT_TailCallwhich means the performance is reasonable andpredictable.
It turns out that the only overhead of
match r v with () -> ()ends up being axor eax,eaxwhich is essentially free compared to everything else.Frustration sets in...
I believe for most of us we only have to make that we just have to avoid writing
code that has TRUELY TERRIBLE PERFORMANCE. We can get away with bad performance
in 99% of all code we write.
However, if I need to write performant code in F# (and maybe future versions of
C#) because tail calls are really really slow I have to be very careful to ensure
with the code I write so that the F# compiler don't emit the
.tailattribute.Sure, I have a pattern that allows me to do it in this case but what if F# compiler improves in future releases and eliminate the nonsense code I wrote to avoid tail calls? The F# compiler has compiler options that allows me to suppress tail calls but F# also supports true inlining which means even if my library is compiled without tail calls when the functions are inlined into the calling assembly it might well inject tail calls.
Further, sometimes the tail calls does go faster when no stack frame is needed.
This puts me in a frustrating spot; I want tail calls but I don't want to pay the
price of the worst case tail call performance.
Obviously the best solution would be that tail calls are always faster than normal
calls but I am sure that is tricky to implement (otherwise it would have been done already).
The second best solution for my particular scenario would be, if the tail call
can be faster than normal calls let's do it otherwise fallback to normal calls.
That is probably confusing as then it doesn't always have the correct semantics
of a tail call but for this particular scenario that is what I want.
I realize F# is a small language so I am hoping that the C# compiler will start
emitting
.tailattributes so that the big C# community will notice the awkwardperformance of tail calls.
Be sure to complain to Microsoft Language & Runtime Community standup on twitch
if you were bored by this rant and want to see less of it.
Regards.
Full sample code
category:cq
theme:tail-call
skill-level:expert
cost:medium
The text was updated successfully, but these errors were encountered: