Repository navigation
tail. call got stack overflow error !? #40581
Description
Description
I try to convert while loop code to to tail call recursion function but I got a stack overflow error when use tail. call while jmp has no problem.
Runtime framework version
.Net Core 3.1
Base code
Sub double_to_fraction()
Dim Base = System.Math.PI
Dim N1, N2 As Integer
Dim Tmp = 1.0
While Tmp <> Base
If Tmp < Base Then
N1 += 1
Else
N2 += 1
N1 = System.Math.Round(N2 * Base)
End If
Tmp = N1 / N2
End While
Console.WriteLine(N1 & "/" & N2)
End SubRecursion form
Sub double_to_fraction2()
Dim Base = System.Math.PI
Dim N = (T:=1, B:=1, N:=1.0).
do(Base,
Function(V, S) V.N = S,
Function(V, S)
If V.N < S Then
V.T += 1
Else
V.B += 1
V.T = System.Math.Round(V.B * S)
End If
V.N = V.T / V.B
Return V
End Function)
Console.WriteLine(N.T & "/" & N.B)
End SubTail call recursion method (do method) [Error : Stack overflow]
//===========================
// la.2.0.1 used f: la ; : la.3.0.1 used.1 la.1.2.3 re use-me
//===========================
// "using data" isn't appear in code but I use it for shorten code on this post.
using data = ValueTuple`3[int,int,double];
data do(data, double, Func`3[data,double,bool], Func`3[data,double,data])
{
ldarg 2
ldarg 0
ldarg 1
call bool Invoke(data, double)
brfalse 0
ldarg 0
ret
0:
ldarg 3
ldarg 0
ldarg 1
call data Invoke(data, double)
ldarg 1
ldarg 2
ldarg 3
tail.call data do(data, double, Func`3[data,double,bool], Func`3[data,double,data])
ret
}
Jump op recursion (do method) [Worked]
//===========================
// la.2.0.1 used t: la.3.0.1 used.1 sa jmp-me : la
//===========================
// "using data" isn't appear in code but I use it for shorten code on this post.
using data = ValueTuple`3[int,int,double];
data do(data, double, Func`3[data,double,bool], Func`3[data,double,data])
{
ldarg 2
ldarg 0
ldarg 1
call Boolean Invoke(data, Double)
brtrue 0
ldarg 3
ldarg 0
ldarg 1
call data Invoke(data, Double)
starg 0
jmp data do(data, Double, Func`3[data,double,bool], Func`3[data,double,data])
0:
ldarg 0
ret
}
Comment
Tail op is supposed to fixed stack overflow from recursion method not cause it so I believe this should be a bug.
Addition info
I write do method via System.Reflection.Emit.DynamicMethod, if nothing wrong in runtime framework, it might be cause from ILGenerator.
Reproduce error project
This is repo of vs solution of tail call stack over flow error, for source code of ILS.dll view at IL Script.
category:correctness
theme:tail-call
skill-level:expert
cost:large
Activity
Dotnet-GitSync-Bot commentedon Aug 8, 2020
I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.
AndyAyersMS commentedon Aug 9, 2020
There are various limitations handling tail calls with structs that depend on architecture and ABI. We have been working to relax these over time.
If this was runs on windows x64, I suspect it might have been fixed in 5.0 with #33004. Can you give 5.0 a try?
AndyAyersMS commentedon Aug 10, 2020
cc @dotnet/jit-contrib
jakobbotsch commentedon Aug 10, 2020
Regardless of the platform this should also be fixed in .NET 5.0 by #341.
AndyAyersMS commentedon Aug 11, 2020
I'll take a look. @RevensofT any chance you can point me at a more complete repro case?
AndyAyersMS commentedon Aug 11, 2020
I was able to construct what I think is a faithful repro. This appears to be fixed in 5.0.
Logical depth of recursion is the sum of the numerator and denominator above, so around 100 million calls.
Disassembly for the
domethod on x64 windows is:@jakobbotsch do we expect to see code like this after the call to
DispatchTailCalls?Still chasing down where things fail with 3.1; moving to future as this isn't a 5.0 work item.
echesakov commentedon Aug 11, 2020
@AndyAyersMS The code after
DispatchTailCallsis what I added in #39815 - it copies the value from a buffer on stack that holds a return value during a call toDispatchTailCallsto the return buffer ofHelper:Do(that can point to the GC heap)AndyAyersMS commentedon Aug 11, 2020
Maybe I'm confused, but if
DispatchTailCallsreturns control back toDo, then I don't see howDocan be properly tail recursive.The only reachable return in
Doshould be the first one; the code after the call toDispatchTailCallsshould never be executed. So that last bit of code (including epilog) looks like it should be dead code and not needed.11 remaining items
AndyAyersMS commentedon Nov 11, 2020
I reran using the zipped repro above. Runs to completion under VS in release with jit optimizations enabled, but I do see a stack overflow in debug
@RevensofT were you running debug versions above? I could not see which config you were launching from your video. If so, this behavior is by design. Debug versions of methods can have larger stack frames.
RevensofT commentedon Nov 17, 2020
@AndyAyersMS thanks for update info, it's run on debug setting, can I enlarge stack frame on debug setting ?
AndyAyersMS commentedon Apr 7, 2021
@RevensofT Your best bet is to try and reduce stack consumption by not relying so heavily on recursion.
But if that's not possible, you can change the default stack size for the main thread using editbin as a post-build step (see for example this stack overflow thread.
For worker threads there is a thread constructor that lets you specify the stack size.
RevensofT commentedon Apr 8, 2021
Thank you very much @AndyAyersMS , it's help me a lot.
AndyAyersMS commentedon Oct 12, 2021
@RevensofT anything else you need here? Can we close this one?
RevensofT commentedon Oct 14, 2021
@AndyAyersMS Thanks for asking, I don't have any question about this topic, thanks again for your help.