Tail Functions and Unrolling

[juliusfriedman]

Proposal

Add the tail keyword which will enforce that a .tail instruction is emitted into the body of the underlying function at function calls to itself or other calls marked with the tail keyword.

The metadata could be encoded into a modopts, modreq making it unusable from compilers which didn't understand it.

Example

public static tail double Factorial(int n) => n == ? 1 : n * Factorial(n - 1)

Alternative

BCL Attribute with compiler support

Plus 1

If you could come up with a source generator / analyzer and eventually compiler support for this optimization where I could get:

public static double Factorial(int number)    
        {    
            //Ternary statement 
            if (number == 1)  return number;    
    
            //Starting result , deduced from return type
            double factorial = number - 1;    

            //Generated loop, Ending condition determined from Ternary statement 
            for (int i = number; i >= 1;--i )    
            {    
                //Logic without recursion
                factorial = factorial * i;    
            }    

            //Return
            return factorial;    
        }    
    }    

With some type of new [Unrolled] / existing [AggressiveOptimization] Attribute or otherwise.

See also: #2544

I would oppose unrolled as a keyword but not strongly.

[HaloFour]

This feels like bike-shedding for the referenced discussion. It's arguing a specific syntax rather than trying to resolve any of the mentioned implementation issues.

[juliusfriedman]

What do you want @HaloFour an example of the expected IL?

This is a long standing issue and I spoke with the team back when I implemented the Regex engine in .Net Micro Framework... See and never received a response although the Timeout feature was adopted without any issues...

[juliusfriedman]

@HaloFour, Even in the hard case of two or more different tail calls intermingling the compiler could emit the correct and efficient code, especially if I can dynamically emit it based on passed expressions... Why should I make a nuget with some kind of special TailEnumerable where I have to maintain the Dictionary e.g. check and emit when necessary... when very well the compiler could do the same thing and never even emit it into the assembly. This means its easily to implement and can already be done if you know how so why not just make it available for everyone?

The only down side I see is an Assembly makes a braking change and removes or adds tail without the other assembles in line being compiled to take advantage of that from there code but similar situations already exist aka const or if I changed a method return from dynamic to a more specific type.

[quinmars]

I'd much prefer the proposed tail calls, see #2304 (comment).

[juliusfriedman]

@quinmars I don't see why the person should have to ever write tail anywhere except in the function definition. Can you explain succinctly why you prefer it and I would gladly close this issue? e.g. in what case would I ever not want the compiler to emit the .tail instruction?

With that typed, I don't see why a hybrid approach can't be taken, e.g. if the function is marked for tail then you ask the compiler to insert it for you otherwise you always can manually have tail where you want.

[HaloFour]

@juliusfriedman

What do you want @HaloFour an example of the expected IL?

No. I just don't think it's necessary to open a second discussion that doesn't expand on anything from the referenced discussion. This isn't a proposal as much as it is a "me too!" The referenced discussion goes into a bunch of options with a bunch of ramifications. The syntax at this point seems like the least interesting aspect of the conversation, especially since syntax changes wouldn't be required to implement such a feature.

[juliusfriedman]

@HaloFour

@juliusfriedman

What do you want @HaloFour an example of the expected IL?

No. I just don't think it's necessary to open a second discussion that doesn't expand on anything from the referenced discussion. This isn't a proposal as much as it is a "me too!" The referenced discussion goes into a bunch of options with a bunch of ramifications. The syntax at this point seems like the least interesting aspect of the conversation, especially since syntax changes wouldn't be required to implement such a feature.

Doesn't expand on anything? I don't see anything about unrolling as an option in any of the other proposals. In addition to that this proposal is slightly different and could be combined with that one so I suppose I could just comment on the existing thread if that would appease you.

I don't disagree with you that this is a "me too", nor that this even requires any syntax change as the compiler itself really should be able to figure this out...

I guess my point is moot as somehow we are going to get contra variant returns before we had support for a 20 year old instruction which would have benefited a lot of people.

[HaloFour]

@juliusfriedman

I don't see anything about unrolling as an option in any of the other proposals.

Having the compiler unroll the recursion is a part of #2304.

I guess my point is moot as somehow we are going to get contra variant returns before we had support for a 20 year old instruction which would have benefited a lot of people.

The JIT does it automatically where it is deemed appropriate. The tail. modifier is there to force a tail call where it might not be as performant and I would suggest is probably a lot less relevant, but even then the JIT may ignore it.

Anyway, I'm not trying to say that I disagree with the value of tail calls, and it does seem to be on the team's radar given we have two separate discussions submitted by team members. It's my opinion that the conversation is best left to one place, but I'll leave that for the team to decide.

[foxesknow]

public static tail double Factorial(int n) => n == ? 1 : n * Factorial(n - 1)

The example you've posted isn't tail recursive, it's more "tail recursion modulo cons". If you've flagged the method as tail would you expect the compiler to raise an error as the method isn't actually tail recursive?

[juliusfriedman]

@foxesknow, Error No, but Warning yes. I find it similar to an unused variable or marking a method as AgressiveInlining / AgresiveOptomization neither of which will give a compiler warning or error if applied incorrectly and technically this proposal could also be implemented via attribute.

[juliusfriedman]

@HaloFour that discussion outlines a way to not use .tail by implementing a goto / jmp... It also requires the user to use tail at every return statement they want the behavior...

While its in the same dimension it's not entirely the same thing as I said in my Plus 1 but if you and or the team feel that strongly about it I will move my comments to that discussion and take up my gripes there.

This was specifically separated not to start a argument in someone else's proposal and referencing it from there seemed like the right thing to do at the time.

[juliusfriedman]

See also this GIST Debug GIST Prod which indicates that using the [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)] might also work right now with little work.

[quinmars]

@juliusfriedman, first I think the recursion is an implementation detail and shouldn't be at such a prominent position of the method signature. I do acknowledge though that there is already precedence by the async keyword. More important, the tail keyword at a method level is not very precise. Take for example the following code:

tail void QuickSort<T>(T[] arr, int low, int high) 
{ 
    if (low >= high)
        return;
        
    var pivot = Partition(arr, low, high); 
   
    if (pivot - low < high - pivot)
    {
        QuickSort(arr, low, pivot - 1); 
        QuickSort(arr, pivot + 1, high);
        Console.WriteLine("DEBUG");
    }
    else
    {
        QuickSort(arr, pivot + 1, high);
        QuickSort(arr, low, pivot - 1);
    }
}

What should the compiler do with it? Give a warning, because the second call in the first if branch will not be optimized? Or give a warning because the first calls in both if branches are not tail calls? If you put the keyword at the position where you expect the tail call optimization everything is clear for you and the compiler:

void QuickSort<T>(T[] arr, int low, int high) 
{ 
    if (low >= high)
        return;
        
    var pivot = Partition(arr, low, high); 
   
    if (pivot - low < high - pivot)
    {
        QuickSort(arr, low, pivot - 1); 
        tail QuickSort(arr, pivot + 1, high);
        // Console.WriteLine("DEBUG"); // uncommenting this line would be an error
    }
    else
    {
        QuickSort(arr, pivot + 1, high);
        tail QuickSort(arr, low, pivot - 1);
    }
}

Error No, but Warning yes. I find it similar to an unused variable or marking a method as AgressiveInlining / AgresiveOptomization neither of which will give a compiler warning or error if applied incorrectly and technically this proposal could also be implemented via attribute.

It is very important, that the compiler can and will perform the tail call optimization, where the author intented it to be happened. This is not an ordinary optimization that brings you some speed improvements. If the optimization is omitted, your program will crash with a stackoverflow exception. Therefore I need guarantees and not good intentions, else I will rewrite the method without recursion myself.

[Unknown6656]

public static tail double Factorial(int n) => n == ? 1 : n * Factorial(n - 1)

Not wanting to be an ass, but his code is not a valid tail function. In the code above, the last term is n * Factorial(n - 1) - meaning that the result is a multiplication - not a tail call.

---

That being said, I'd like to see the compiler using tail calls wherever possible (without any special syntax) - except if a method is marked with [MethodImpl(MethodImplOptions.NoInlining)].

[juliusfriedman]

@juliusfriedman, first I think the recursion is an implementation detail and shouldn't be at such a prominent position of the method signature. I do acknowledge though that there is already precedence by the async keyword. More important, the tail keyword at a method level is not very precise. Take for example the following code:

tail void QuickSort<T>(T[] arr, int low, int high) 
{ 
    if (low >= high)
        return;
        
    var pivot = Partition(arr, low, high); 
   
    if (pivot - low < high - pivot)
    {
        QuickSort(arr, low, pivot - 1); 
        QuickSort(arr, pivot + 1, high);
        Console.WriteLine("DEBUG");
    }
    else
    {
        QuickSort(arr, pivot + 1, high);
        QuickSort(arr, low, pivot - 1);
    }
}

What should the compiler do with it? Give a warning, because the second call in the first if branch will not be optimized? Or give a warning because the first calls in both if branches are not tail calls? If you put the keyword at the position where you expect the tail call optimization everything is clear for you and the compiler:

void QuickSort<T>(T[] arr, int low, int high) 
{ 
    if (low >= high)
        return;
        
    var pivot = Partition(arr, low, high); 
   
    if (pivot - low < high - pivot)
    {
        QuickSort(arr, low, pivot - 1); 
        tail QuickSort(arr, pivot + 1, high);
        // Console.WriteLine("DEBUG"); // uncommenting this line would be an error
    }
    else
    {
        QuickSort(arr, pivot + 1, high);
        tail QuickSort(arr, low, pivot - 1);
    }
}

Error No, but Warning yes. I find it similar to an unused variable or marking a method as AgressiveInlining / AgresiveOptomization neither of which will give a compiler warning or error if applied incorrectly and technically this proposal could also be implemented via attribute.

It is very important, that the compiler can and will perform the tail call optimization, where the author intented it to be happened. This is not an ordinary optimization that brings you some speed improvements. If the optimization is omitted, your program will crash with a stackoverflow exception. Therefore I need guarantees and not good intentions, else I will rewrite the method without recursion myself.

I would expect the compiler to emit the tail at every call to QuickSort and if the user wanted to narrow it further he would remove tail from the signature and or apply it directly in the body where required for whatever reason and in that case the compiler would not emit it at all calls to QuickSort withing QuickSort but from outside it would.

I still think your implementation is a bit contrived because I would assume that all the calls to QuickSort should have tail can you explain why you don't want them on a few calls yet on others? (I can't tell from your example AFG)

[chrisoverzero]

I would expect the compiler to emit the tail at every call to QuickSort […]

…and:

[…] I would assume that all the calls to QuickSort should have tail[.]

Not all recursion is tail recursion, and not all recursion can be tail-call optimized.

[juliusfriedman]

I would expect the compiler to know what can and cannot be since it has all the context.

[HaloFour]

I think the point is that not all recursion within a single method should be a tail call. The working stack space of a quick sort implementation can be reduced from O(n) to O(log n) by having half of the recursions be tail recursion. Tail recursion is a function of the method invocation (specifically that it can be converted into a jump), there are numerous scenarios where it doesn't apply across the entirety of a single method.

Scala has a similar method-wide annotation for requiring tail recursion, and as a result it's implementation of quick sort cannot use it. It has to rely on the compiler detecting that half of the calls could use tail recursion and for it to be applied automatically, which makes the solution much more fragile.

[juliusfriedman]

@HaloFour I like to think of C# as more like C but perhaps that's the wrong way to think? (What about AOT)

In C or C++ you don't have tail.

I would argue that the C# compiler should be better than scala compiler... not a copy of it's mistakes

[HaloFour]

In C or C++ you don't have tail.

C and C++ don't have a lot of things that C# has. :)

I would argue that the C# compiler should be better than scala compiler... not a copy of it's mistakes

I agree, which is why I don't really think that "tail" recursion should be enabled or enforced at the method level. Of the existing proposals/discussions I kind of prefer the tail return approach best as it is explicit syntax applied at the return site which the compiler can use to enforce the pattern and then properly rewrite that part of the method. But as you can see from that proposal I have concerns about whether the team will cover those use cases where tail recursion would expect to work and how "friendly" it would be.

Using the existing runtime facilities, whether that be the tail. prefix or some attribute to influence JIT, can have a more holistic view of the IL and handle cases such as tail calls between mutually recursive functions, but at the same time it is disconnected from the compiler and what it can ensure will happen. If that is the approach chosen I'd rather add to the options that MethodImplAttribute accepts and let it treat any qualified recursion as a tail call. Analyzers could theoretically identify cases of recursion that would or would not be eligible for tail call optimization.

But that's just my opinion.

[juliusfriedman]

The next step would be then to apply that attribute (or use existing) when the compiler notices a recursive and it meets the correct criteria automatically.

The problem would then be how to get it to turn it off when I don't want it which is the inverse problem and much harder to solve (required a don't tail keyword)