Optimizing non-tail recursions for sequences

[AlexRadch]

F# now optimizes tail recursion when generating sequences.

let rec tail b e = seq {
    if b <= e then
        yield b
        yield! tail (b+1) e
}

The above tail recursion will be successfully optimized and the performance will be linear.

let rec head b e = seq {
    if b <= e then
        yield! head b (e-1)
        yield e
}}

At the same time, the above head recursion will not be optimized, and the performance will be quadratic.

To optimize tail recursion, the GenerateNext method can return the flag (2) to go to the next iterator and thus the tail recursion execution speed will become linear rather than quadratic.

I propose adding to this method the ability to call the next iterator and return execution to the current iterator. Flag 3 will call the next iterator and return execution to the current iterator. This will optimize the speed of all simple recursions to linear, and not just simple tail recursions.

To support the ability to call the next iterator and return to the current one, add a stack of iterators in the GeneratedSequenceBase<int> class. Adding a stack of iterators will allow you to optimize all types of simple recursions, not just tail ones.

[T-Gro]

Could you please lay out any potential risks of breaking changes or disadvantages to the feature request as well, please?

If stack becomes explicit via a Stack, GC pressure will be increased - but that impact can be benchmarked of course.

[AlexRadch]

Could you please lay out any potential risks of breaking changes or disadvantages to the feature request as well, please?
If stack becomes explicit via a Stack, GC pressure will be increased - but that impact can be benchmarked of course.

I do not foresee any risk of breaking changes. The existing code will continue to function as it did before. The old code will not create a stack of enumerators, meaning there will be no unnecessary memory allocation. Tail recursion will continue to operate as before, without creating a stack on the heap. The only new addition will be a check after the last enumerator completes, ensuring that no stack has been created. This check will not impact the performance of the existing code.

For non-tail recursion, a stack of enumerators will be created to allow returning to the previous enumerator once the nested one has finished its execution. Memory for this stack will be allocated on the heap, which would otherwise be allocated indirectly on the execution stack. As a result, the overall memory requirements will not increase and will remain unchanged. The performance of the code will improve from quadratic to linear.

I should also note that the current stackless implementation does not support tail recursion optimization when the CheckClose flag is enabled. For such cases, we can create a stack for tail recursion and treat it similarly to non-tail recursion. This means that introducing a stack can also enhance the performance of tail recursion when the CheckClose flag is set.

The most challenging aspect here is implementing proper exception handling and ensuring that exceptions from nested enumerators are correctly propagated to the outer ones.