Add tail call support to TaskBuilder using the new ReturnFromFinal method

[majocha]

I'd like to draft an idea of implementation that has a chance to actually work.

consider

let rec t n = task {
    if n % 1000 = 0 then printfn "in t %d" n
    if n > 0 then
        return! t (n - 1)   
}

t 10_000

This is currently ReturnFrom:

member inline this.ReturnFrom(task: Task<'T>) : TaskCode<'T, 'T> =
    this.Bind(task, this.Return)

ReturnFromFinal should do something like

member inline this.ReturnFromFinal(task: Task<'T>) : TaskCode<'T, 'T> =
    if not thisTaskIsCurrentTailCallTarget then
        this.EnterTailCallLoop(task)
    else updateTailCallTarget task

Let's call the first task that does return! and enters the loop "the runner".

The runner would execute the tail call loop. It would await the tailCallTarget. If tailCallTarget got updated to a next one - do another iteration, if not - finish and return its result.

Now, the problem to solve is how to communicate between state machines. The task awaited as tail call target needs to know it is a tail call target. In case it executes return! itself, it needs to do updateTailCallTarget for the runner to see.

One way to solve this is to keep that data in a static AsyncLocal. That way it would be available as a communication channel between the runner task and its subsequent tail call targets.

Another is to use a ConditionalWeakTable to attach the needed data to task instances.

[majocha]

The general problem with hot start task is that even before ReturnFromFinal(task) gets called, the task is already started. This means MoveNext on the inner task state machine is called before ReturnFromFinal on the enclosing one. Because ReturnFromFinal haven't executed yet, we don't know yet that we're in a tail call context.

In effect, if we have a degenerated situation with a task that does not yield at all, like in the example above, it will stack overflow no matter what. There are ways to work around this, but it gets rather ugly quickly.

[T-Gro]

Is the "missing" machinery a signal from the compiler to the outer task to tell it that all it's inside workings will ever do a tail call (or terminate), but never recurse?

[majocha]

Ah, I think I see what you mean. We indeed pretty much do have this info after checking a CE, it's just not surfaced to the builder in any way.
But I'm not sure that would be useful. if a given return! is a tail call, it is already enough info to safely hand off the execution and abandon the previous state machine. The problem is actually doing it.

[majocha]

And there is already a built-in way to achieve any depth of recursion, tail-call or not, without stack overflow. Just make sure initial MoveNext of one state machine doesn't call another initial MoveNext directly ad-infinitum, but break the chain from time to time.

This actually runs fine:

let rec t n = backgroundTask {
    try 
        if n % 1000 = 0 then
            printfn "in t %d" n
            do! System.Threading.Tasks.Task.Yield() // This prevents stack overflow by deferring ReturnFrom to next state machine step.
        if n > 0 then
            return! t (n - 1)
        else printfn "done!"
    finally ()
}

t 1000_000 |> _.Wait()

The real problem is that if this throws somewhere deep, stack unwind will take forever.

[majocha]

I gave it some more thought and came to a conclusion this makes no sense.
The consumers of task { } can already protect any expression from stack overflow by inserting a do! Task.Yield() which is basically queueing on the threadpool.

The only thing to gain would be to prevent the allocation of intermediate Tasks in recursive CEs but this is impossible by definition: at the moment of ReturnFromFinal call, the target task is already allocated.

[T-Gro]

This might make more sense in a cold task scenario, to plan upfront what/when to allocate?

[majocha]

Yes but it is a minor optimization and not that easy to pull off. Basically, AsyncTaskMethodBuilder<'T> instantiates the resulting Task<'T> lazily, but we instead request it eagerly. This causes a chain of intermediate Task<'T> instantiations in recursive execution.
With ReturnFromFinal it should be theoretically possible to hand off the current AsyncTaskMethodBuilder to the next iteration instead.

But not if we bind on Task<'T> or, in case of cold task, unit -> Task<_> . We would instead need an Invokable exposing some interface like HandOff: AsyncTaskMethodBuilder<'T> -> unit.
That implies cold start. But that seems actually doable. I'm experimenting with a async2 resumable implementation at the moment, it might be interesting to try this.

[T-Gro]

I understand now.
The immediate semantics of Tasks are not preventing this optimization.

Are you thinking in the lines of using your async2 in the F.C.S. codebase to reduce recursive cancellable/async allocations? 👍

[majocha]

Yep, that's what I wanted to try. I don't expect any big performance gains, though.