[RFC FS-1087] Discussion thread for resumable-code RFC

[dsyme]

Discussion thread for F# RFC FS-1087 - Resumable code

[cartermp]

I don't see mention of this in the PR and the implementation is rather large. Are the well-known intrinsics public? I think for something this large they should stay internal only for a while to account for any churn. I'm skeptical that we'll "get it right" on the first go and won't have a desire to adjust them afterwards.

[dsyme]

Are the well-known intrinsics public?

Yes they are. They really need to be for testing purposes - it's very difficult if they aren't.

We should get the design right before it goes out of preview.

What's our policy for FSHarp.Core surface area changes for preview-only features (assume the compiler intrinsics are marked "Experimental" or "only use in preview" or whatever we can do now).

I'm ok with the whole thing being in preview a fair time (for example I'm as concerned about the use of SRTP in Tasks.fs as I am about the intrinsics - and that's also FSharp.Core surface area).

I could sort of see us taking the "task" support out of preview first, though I'm not sure that gains us that much, as if the inlined code coming from FSharp.Core must conform to the resumable code spec. It just means that if there are corner cases in the resumable code implementation not exposed by Tasks.fs then we could adjust that at a later point.

As an aside, I would like to use this for:

• compiling list computation expressions to more efficient code
• compiling array computation expressions to more efficient code
• option { .. }
• result { .. }

The first two cases give 4x speedup or more for some basic list/array constructions, see https://github.com/dotnet/fsharp/blob/92415de183daf8c6874a52b695d1da7ae6bb595e/BenchmarkDotNet.Artifacts/results/TaskPerf.ArrayBuilder-report-github.md for example

I may also look if there's a way to reimplement a 100% compatible async { ... } with this

[cartermp]

This would require the following then, yes:

[<Experimental("Experimental library feature, requires '--langversion:preview'")>]

Every new construct in FSharp.Core that is a part of a preview language feature needs to be decorated with this (unless custom work is done in the compiler itself to only light it up recognition of that construct and error out appropriately). This allows us to make a breaking change if we need, since previews are subject to breaking changes. Once that attribute goes away and we ship something, it cannot change.

[dsyme]

Regarding the faster list { .. .} and array { .. } for computed array/list....

The difference between seq { .. } |> Seq.toArray and a builder that writes into a ResizeArray then calls ToArray has been known for a while. Someone wrote a normal F# builder for that, I'll dig it out and add it as a perf comparison. I'm not certain we're gaining much over that normal builder.

But the F# computation expression list [ .. ] can be made even faster, if we put this technique in FSharp.Core (or else reveal the "mutate the end of a freshly allocated list" hack used in FSHarp.Core for fast list creation out as a compiler-known intrinsic.) That is, the operation of [ ... ] would now be to mutate the end of the list as it trundles along.

Consider [ for x in 1 .. 3 do yield x; yield x+1 ]. So this is going to be a struct state machine initially holding two registers (mutable fields)

1. the last cons cell in the list being built
2. a handle to the cons cell that forms the front of the list

• When the first yield happens, we create a cons cell and put it in both, the tail is not yet initialized

• When the second and later yields happen, we create another cons cell, put it in the tail of (1), and update (1) to be the new end cell (edited)

• Then when the code is finished the list is ready to go, we just set the tail of (1) to the empty list and return (2).

Then no ResizeArray is needed, and no Seq.toList.

[gusty]

or else reveal the "mutate the end of a freshly allocated list" hack used in FSHarp.Core for fast list creation out as a compiler-known intrinsic.

I would like to have this available, maybe in an "Unsafe Primitives" module.

[dsyme]

Yes, it would be reasonable to add this to an Unsafe or Unchecked module.

Indeed all the resumable state machine primitives could be similarly named.

[cartermp]

With the caveat that it's protected with Experimental until the API is stable :)

[dsyme]

@cartermp Yup, but aspects of the mechanism is basically unchecked, e.g. the __resumeAt can be cheated by using an arbitrary integer for the destination. The code won't actually be unverifiable, and it will be the equivalent of a drop-through, but likely warrants an Unchecked. I'll add a note to the RFC

[smoothdeveloper]

Regarding "Limitation - No asynchronous tailcalls", is emitting a warning considered?

this is akin to another gotcha quoted from http://tomasp.net/blog/csharp-async-gotchas.aspx/

the most common gotcha is that tail-recursive functions must use return! instead of do! to avoid leaks

It would be great to have warnings for those.

[SteveGilham]

Seeing "resumable Tasks" makes me think of the old Workflow Foundation. Would it be expected that the machine state could be pickled and later restored?

[dsyme]

Seeing "resumable Tasks" makes me think of the old Workflow Foundation. Would it be expected that the machine state could be pickled and later restored?

Semantically, I think there's nothing you can do with resumable tasks that you can't already do with existing workflows. Existing workflow states can be pickled with some care (you need to to private reflection over the workflow state and captured values, or else make the state explicit in monadic actions)

It might in theory help to have the state organised in a way that more closely matches the structure of the code (one state machine object per "foo { ... }") but this can also make things tricker, e.g. there can be multiple not-yet-active fields for locals in the state machine.

For these reasons I wouldn't recommend thinking of this as a semantic feature at all, but rather just a performance feature. I'll add that to the RFC.

[dsyme]

BTW the best worked out framework for persisted workflows that I know of is the workflow part of the Angara framework, open sourced here: https://github.com/microsoft/Angara.Flow/blob/master/docs/content/Execution.md

It's not under active development and the docs are unfortunately not properly posted, but perhaps we can assess, learn and maybe even fork and resurrect.

[dsyme]

Regarding "Limitation - No asynchronous tailcalls", is emitting a warning considered?

this is akin to another gotcha quoted from http://tomasp.net/blog/csharp-async-gotchas.aspx/

the most common gotcha is that tail-recursive functions must use return! instead of do! to avoid leaks

It would be great to have warnings for those.

Good point on all of these. I'll make a note of them in the RFC

[NatElkins]

I have a design question. Is there any reason magic naming (e.g. __expand_) was used over, say, attributes? Was it ease of implementation, or because of limitations of attributes? Or something else?

[dsyme]

I have a design question. Is there any reason magic naming (i.e. _expand) was used over, say, attributes? Was it ease of implementation, or because of limitations of attributes? Or something else?

This is all still open for discussion. I'll add it to the RFC

Basically, attributes aren't allowed on expression-locals in F# today, and I was looking for something sufficiently weird to highlight that this is a here-be-dragons compiler optimization feature.

[baronfel]

What would the ideal representation of these features in your view be @dsyme? I could see some value is a section around 'considered-but-rejected', 'ideal-but-unimplementable', and 'compromise-current-state' syntax if there were language-restricted reasons you landed on this particular syntax. That might point towards future language features that could be fleshed out?

[abelbraaksma]

Basically, attributes aren't allowed on expression-locals in F# today, and I was looking for something sufficiently weird

@dsyme There's a design suggestion open: fsharp/fslang-suggestions#848 (allow attributes on locals), which, if supported and implemented, may allow this new feature to be triggered with attributes as opposed to magical names.

[cartermp]

I would far prefer attributes over bizarre keywords, mostly since there's already a design precedent around them being used to augment things (byref structs, readonly structs, struct DUs, struct records, etc.)

[NatElkins]

I don't even know if the CLR would allow attributes on expression locals. Allowing attributes on local functions isn't quite the same thing, since methods are acceptable targets for attributes today. Here is the closest C# language suggestion I could find: dotnet/csharplang#2478 . I think there might be incompatibility with the AttributeUsageAttribute which wouldn't be able to cover the expression local

I do wonder if instead of using special names, some combination of attributes (on things that can have attributes) and types as annotation could be used. For example, in the case of __stack_step using AttributeUsage.ReturnUsage on the expanded function and a special type for what __stack_step represents to restrict its usage to a particular pattern.

Also there are some cases I was wondering if functions can be used to restrict usage rather than asking the programmer to adhere to a particular pattern. The case I'm thinking of here is

    if __useResumableStateMachines then
        __resumableStateMachine
            { new SomeStateMachineType() with 
                member __.Step ()  = 
                   <resumable code>
            }
    else
        <dynamic-implementation>

Is there any reason a function that itself takes two functions (one for the compilation case, the other for the dynamic case) can't be used to enforce this pattern? Or an abstract class/interface that has two methods, one for each case?

To be fair, I have no idea what the implementation cost is to do it in that way vs the way it currently is.

[dsyme]

Is there any reason a function that itself takes two functions (one for the compilation case, the other for the dynamic case) can't be used to enforce this pattern? Or an abstract class/interface that has two methods, one for each case?

Any of these would be ok-ish, they are all problematic. I think the if/then/else lends itself easily to #if of the if branch if you want to compile and thest only the regular-code-dynamic-execution implementation.

I don't even know if the CLR would allow attributes on expression locals.

This is correct, I believe it's not allowed in the .NET metadata format which is why we don't support it for expression locals in F#. We could make an exception for these particular attributes in F# code but that feels as hacky as anything else.

The current approach is definitely hacky though - I'm not denying that - and am open to suggestions. It has some advantages (as noted in the RFC) - I don't think we even want this feature to feel "part of the language", even less so than [<Struct>].

It's possible we could continue to decompose it into micro features like C# did with byrefs, span etc. But I think that would lead naturally to an explosion of complexity for little gain.

For example, we could allow something like this as a first class language feature:

let f () = 
            { [<Struct]
              new IComparable with 
                member __.CompareTo (x)  = ... }

To be effective this construct would need to imply a local type definition T when T:struct and T :> IComparable. But then we'd need a new rule checking that this locally implied type was eliminated (utilised) immediately (as in the After code in the encoding in the RFC). That would be yet another new rule (checking no escape of local struct types). Yet the feature doesn't seem to be so useful and has never been requested to my knowledge.

[panesofglass]

Will task and taskSeq handle both Task and ValueTask? Will it require that all tasks use the same type, or is there some way to await a mix of the two types?

[dsyme]

Thanks, will add as an unresolved question to the RFC

[dsyme]

#534

[smoothdeveloper]

Will task and taskSeq handle both Task and ValueTask? Will it require that all tasks use the same type, or is there some way to await a mix of the two types?

is it possible to make the builder work with any "Task like" objects, maybe through SRTP, so long it follows the patterns described in generalized async return types and valuetask result?

Also, is it required to have both task and taskSeq builders or it could be a single builder distinguished with usage of yield or return?

[dsyme]

@TIHan and I spent today talking through how to add checking for resumable code at IDE-time, and not just in the late phase of state machine generation. In particular this means we could reliably give a warning if code will not compile to a state machine, in the IDE, even in debug mode, and the emit of this warning won't depend on debug/release settings

Here are our notes.

Take a sample set of functions or methods which covers the cases we care about (the names are indicative, and each method can take other non-Resumable code parameters).

    [<return: ResumableCode>]
    let Leaf(x: int) = ...
 
    [<return: ResumableCode>]
    let Composition([<ResumableCode>] __expand_code1, [<ResumableCode>] __expand_code2) = ...
     
    // note no 'ResumableCode' on return
    let Consume([<ResumableCode>] __expand_code1)  = ...

1. Anything taking a ResumableCode parameter must be 'inline'

2. A method with return: ResumableCode must be non-abstract and must return a resumable code block . A resumable code block is:

   • A delegate expression Delegate(fun sm -> <optional-resumable-stmt>)
   • A function-expression (fun sm -> <optional-resumable-stmt>)
   • A call to Composition(code1, code2), if code1 and code2 are resumable code blocks
   • A call to Leaf(x)

3. Within a resumable code block, an optional resumable statement is:

   1. if __useResumableStateMachines then <resumable-stmt> else <normal-stmt>
   2. <resumable-stmt> (not using __resumeAt, __resumableEntry)

4. A resumable statement is any of these:

   1. __resumeAt contId
   2. match __resumableEntry() with Some contId -> <resumable-stmt> | None -> <resumable-stmt>
   3. try <resumable-stmt> with <normal-stmt>
   4. let mutable __stack_var = ... in <resumable-stmt>
   5. try <resumable-stmt> finally <normal-stmt>
   6. while <normal-stmt> do <resumable-stmt>
   7. <resumable-stmt>; resumable-stmt>
   8. call/invoke a resumable code block parameter

   Note, at runtime, "__resumeAt contId" will jump directly to 'None' branches of the corresponding 'match __resumableEntry ... '. In particular all __stack_var in scope will be zero-initialized.

5. During type-checking or post-inference checks, a call to Consume(code) is"compilable as state machine" if and only if code is a resumable code block. An IDE-time warning is emitted if "code" is not a resumable expression saying "this expression will not be compiled efficiently to resumable code".

6. Internally, at compile time, Consume(code) is tranformed to __compileAsStateMachine(fun () -> Consume(code))

7. A resumable state machine expression is:

   { new StateMachine() with 
       [<ResumableCode>]
       member x.M() = 
         <optional-resumable-stmt>
   }
   

   or similarly with

    __resumableStateMachineStruct(....)
   

   as described in the RFC

No warning is given for an state machine which doesn't produce any useful resumable code:

       let f code = 
          { new StateMachine() with 
             [<ResumableCode>]
             member x.M() = code() } 
          }    

For example (in fragments)

    [<return: ResumableCode>]
    member inline _.Zero() : TaskSeqCode<'T> =
        (fun _sm -> TaskSeqStatus.DONE)

    [<return: ResumableCode>]
    member inline _.Combine([<ResumableCode>] __expand_task1: TaskSeqCode<'T>, [<ResumableCode>] __expand_task2: TaskSeqCode<'T>) : TaskSeqCode<'T> = ...

    member inline _.Run([<ResumableCode>] __expand_code : TaskSeqCode<'T>) : IAsyncEnumerable<'T> = 
        let sm = 
            { new TaskSeqStateMachine<'T>(-1) with 
                [<ResumableCode>]
                member sm.Step () = 
                    if __useResumableStateMachines then
                        //-- RESUMABLE CODE START
                        __resumeAt sm.ResumptionPoint
                        __expand_code sm
                        //-- RESUMABLE CODE END
                    else 
                        let code = sm.ResumptionFunc sm
                        match code with 
                        | TaskSeqStatus.AWAIT ->
                            sm.Awaiter.UnsafeOnCompleted(Action(fun () -> sm.MoveNext()))
                        | _ -> ()
                        code
            }
        if not __useResumableStateMachines then
            sm.ResumptionFunc <- __expand_code
        sm.Start()

    [<return: ResumableCode>]
    member inline _.Yield (v: 'T) : TaskSeqCode<'T> =
        (fun sm -> 
            if __useResumableStateMachines then 
                match __resumableEntry() with
                | Some contID ->
                    sm.ResumptionPoint <- contID
                    sm.Current <- ValueSome v
                    TaskSeqStatus.YIELD
                | None -> 
                    TaskSeqStatus.DONE
            else
                sm.ResumptionFunc <- (fun sm -> TaskSeqStatus.DONE)
                sm.Current <- ValueSome v
                TaskSeqStatus.YIELD)

Given this

taskSeq { yield 1 }  [    --> taskSeq.Run(taskSeq.Yield(1))  ]

          --> yes, argument to Run is resumable code because Yield always returns ResumableCode, state machine always generated, no warning

[<return: ResumableCode>]
let inline myYield1 ([<ResumableCode>] x) = taskSeq.Yield(1)
taskSeq.Run(myYield(1))

          --> yes, argument to Run is resumable code, state machine always generated, no warning

let inline myYield1 x = taskSeq.Yield(1)
taskSeq.Run(myYield(1))

          --> no, state machine not always generated, warning in IDE at myYield(1) because not a resumable code block but Run equests one

let myYield1 x = taskSeq.Yield(1)
taskSeq.Run(myYield(1))

          --> no, state machine not always generated, warning in IDE at myYield(1) because not a resumable code block but Run equests one 

taskSeq.Run(TaskCode(fun sm -> ...))

          --> yes, argument to Run is resumable code, state machine always generated, no warning

[dsyme]

I have implemented a variation on these rules in the RFC and all resumable state machine samples we have are now being checked with them. The rules are certainly useful for checking the general well-formedness of resumable code (though there are still many subtleties) and removing a few basic errors.

[dsyme]

The RFCs for resumable code and tasks have been separated out into two RFCs, though the implementation remains one PR.

The implementation of both now satisfies all requirement

• I will start to check things like debugging.

• There is a question about what to do for ContextInsensitiveTasks in TaskBuilder.fs

[dsyme]

I've added a significant unresolved question to the RFC about the potential for people to start to over-use resumable code for other non-resumable optimized code purposes, see https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1087-resumable-code.md#potential-for-over-use

I'm experimenting with solutions to this now which tease apart the mechanisms a little further.

[dsyme]

As mentioned above, I'm concerned that people will complicated resumable code to get high-performance synchronous code - indeed I've been doing that already with the option { ... }, list { .. .}, array { ... }, voption { ... } computation expression builder samples.

I really want to get to to the heart of this problem. As a result I've done the following:

1. prototyped a very simple InlineIfLambda mechanism for attributing parameters
2. checked this improves the inlined code for Array.map when the lambda is large
3. implemented the "option { .. }" builder in terms of it
4. Made one small improvement to Optimizer.fs for applying computed functions

This is a much simpler mechanism to use and has many, many applications across FSharp.Core and elsewhere. @TIHan also pointed out that Kotlin makes this the default for function arguments on inlined functions (though we can't really do that by default because it can cause code explosion).

Here are the builders implemented in the different ways:

• option { ... } using resumable state machines
• optioni { ... } using InlineIfLambda
• optionSlow { ... } using standard F# computation expressions ("old builder")

The results are good, see table below. Here MultiStepOption_InlineIfLambda beats MultiStepOption_StateMachine and MultiStepOption_OldBuilder and is basically the same as MultiStepOption_NoBuilder (see this code)
The InlineIfLambda implementation just requires the InlineIfLambda attribute on function parameters.

I will now validate the same for list { ... } and array { ... }. But in short this convinces me that we should have InlineIfLambda in the F# design as a much nicer way of achieving high-performance synchronous code.

It's an open question if task { ... } can use this feature. However adding this feature makes it much less imperative to allow arbitrary non-FSharp.Core users to write resumable code, and it's possible we can restrict the definition of resumable code to FSharp.Core only (or at least keep the open use of the general mechanism in preview much longer).

Method	Categories	Mean	Error	StdDev	Ratio	RatioSD	Gen 0	Gen 1	Gen 2	Allocated
MultiStepOption_StateMachine	MultiStepOption	31.81 ms	0.4295 ms	0.3587 ms	1.00	0.00	13406.2500	-	-	70399992 B
MultiStepOption_InlineIfLambda	MultiStepOption	19.59 ms	0.2070 ms	0.1936 ms	0.62	0.01	13406.2500	-	-	70399968 B
MultiStepOption_OldBuilder	MultiStepOption	60.56 ms	1.1502 ms	1.0197 ms	1.91	0.04	38555.5556	-	-	202666632 B
MultiStepOption_NoBuilder	MultiStepOption	16.63 ms	0.2021 ms	0.1792 ms	0.52	0.01	13406.2500	-	-	70399968 B
MultiStepValueOption_StateMachine	MultiStepValueOption	33.65 ms	0.6403 ms	0.5989 ms	1.00	0.00	-	-	-	24 B
MultiStepValueOption_InlineIfLambda	MultiStepValueOption	27.92 ms	0.3036 ms	0.2840 ms	0.83	0.02	-	-	-	-
MultiStepValueOption_OldBuilder	MultiStepValueOption	64.20 ms	1.4694 ms	1.3745 ms	1.91	0.04	19000.0000	-	-	100266664 B
MultiStepValueOption_NoBuilder	MultiStepValueOption	27.86 ms	0.3661 ms	0.3424 ms	0.83	0.01	-	-	-	-

[dsyme]

I've made a major set of updates to the RFC for resumable code https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1087-resumable-code.md. Please review

The implementation of coroutines (essentially, Task without any async I/O) using resumable code has been particularly instructive, and will probably be the running example in the RFC. I'll tidy up the example further. https://github.com/dotnet/fsharp/pull/6811/files#diff-98653d141f298053882d239a60805d78b485fad19c14c830fe47cba0d8f755b4R1

[dsyme]

I did a trial re-implementation of F# async (imperfectly and only a subset of the API) using resumable code. You can take a look at the subset that's implemented by looking in the signature file

• Implementation: https://github.com/dotnet/fsharp/blob/feature/tasks/tests/fsharp/perf/tasks/FS/async2.fs

• Signature fle: https://github.com/dotnet/fsharp/blob/feature/tasks/tests/fsharp/perf/tasks/FS/async2.fsi

Recall how async differs from tasks:

	async-waits	results	hot/cold/multi	tailcalls	cancellation token propagation	cancellation checks
F# async	async-waits	one result	multiple cold starts	tailcalls	implicit	implicit
F# task/C# task	async-waits	one result	once-hot-start	no-tailcalls	explicit	explicit

Anyway the approximate reimplementation appears to run as fast as TaskBuilder for sync cases, and as fast as tasks for async cases. That makes it like 10-20x faster than the current F# async implementation. Stack traces etc. would be greatly improved to.

However it's not a perfect reimplementation - there are no tailcalls nor cancellation checks yet - and perfect compat is probably impossible sadly, there are lots of subtleties. For example async.Return() and other direct use of CE methods change type from Async<T> to AsyncCode<T>, so the API is not perfect compat (an Async.Return etc. would be needed instead). We could possible fix that in the F# compiler though there are lots of other little niggles too.

That said it should be good enough to allow an FSharp.Control.Async2 package that is a drop-in replacement for F# async for 99.9% compat. (The Async2<T> would be a different type in that case, though that may matter less now Task<T> is so established more as an interop standard)

[dsyme]

There's a discussion going on about whether to have "affine tasks" (aka "context insenstive tasks"), or else have a backgroundTask { ... } that does an immediate "SwitchToThreadPool" thing (e.g. do! Task.Yield().ConfigureAwait(false) or something like that).

The idea of backgroundTask { ... } seems pretty popular but may have ramifications I haven't thought of and there may be better naming.

See rspeele/TaskBuilder.fs#35 (comment)

[dsyme]

As part of the linked discussion there's a proposal to change the spec of backgroundTask { ... } to only call Task.Run if on a UI thread (i.e. SynchronizationContext.Current <> null)

See rspeele/TaskBuilder.fs#35 (comment)

Please let me know what you think.

[0x53A]

how hard would it be to implement custom behavior in user code, for example dotnet/runtime#47433 (comment)?

Would something like that be possible by just overriding one/two method(s), or would the whole builder need to be re-created?

[dsyme]

Would something like that be possible by just overriding one/two method(s), or would the whole builder need to be re-created?

It should be possible by a new builder that delegates to the existing builder except where necessary

[ysangkok]

The link to FS-1087-resumable-code.md is dead, where did it go?

[baronfel]

It's here now that it's been integrated into a preview