runtime: tail. call got stack overflow error !?
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 Sub
Recursion 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 Sub
Tail 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
About this issue
- Original URL
- State: closed
- Created 4 years ago
- Comments: 23 (17 by maintainers)
Regardless of the platform this should also be fixed in .NET 5.0 by #341.
@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.
Thanks @RevensofT – will report back what I see soon.
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.
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?