Discussion on async/cancellation and exceptions

[dsyme]

@TIHan and I have been discussing using FSharp.Data.Adaptive in future work on making parts of the F# compiler and FSharp.Compiler.Service more incremental.

We've some questions about async, cancellation and exceptions.

As context, in our current incremental model the operations to evaluate final nodes in the dependency graph are always cancellable. In the language of FSharp.Data.Adaptive I believe this means as follows. Consider these operations:

ASet.map: ('T -> 'U) -> aset<'T> -> aset<'T>
Aset.contains: aval<'T> -> aset<'T> -> aval<'T>
Aset.elements: aset<'T> -> aval<Set<'T>>
Aval.force: aval<'T> -> 'T

In these cases, the 'T -> 'U functions are not cancellable and might throw exceptions. My understanding is that

1. if any such function throws an exception then FSharp.Data.Adaptive never "saves" the exception as a result, it is just always propagated all the way up to the routine that requested the result.

2. some parts of the dependency graph calculation may have been committed, and this is done in an atomic way (there is a related question about concurrent update requests)

3. there is no special treatment if OperationCancelledException is thrown, and so throwing that exception is a valid way to represent cancellation.

4. however there is no cancellation token propagated, so these functions have to capture an exterior cancellation token.

Now one could imagine a variation on FSharp.Data.Adaptive that either

1. propagates a cancellation token

2. uses a computation expression like cancellable { ... } to represent synchronous cancellable code

3. uses an existing computation like async { ... } that has cancellation built in (but is richer, as it represents asynchronous code)

Which would lead to signatures like this (option 1)

ASet.mapCancellable: (CancellationToken -> 'T -> 'U) -> aset<'T> -> aset<'T>
Aval.force: aval<'T> * ?cancellationToken: CancellationToken -> 'T

or this (option 2)

ASet.mapCancellable: ('T -> Cancellable<'U>) -> aset<'T> -> aset<'T>
Aval.force: aval<'T> -> Cancellable<'T>
Cancellable.run: Cancellable<'T> * ?cancellationToken: CancellationToken -> 'T

or this (option 3)

ASet.mapAsync: ('T -> Async<'U>) -> aset<'T> -> aset<'T>
Aval.force: aval<'T> -> Async<'T>

or this (combo of option 2 and 3 for tasks)

ASet.mapAsync: (CancellationToken -> 'T -> Task<'U>) -> aset<'T> -> aset<'T>
Aval.force: aval<'T> * ?cancellationToken: CancellationToken -> Task<'T>

I'm curious about your thinking about this. Obviously complicates things.

[krauthaufen]

Hey, sounds interesting.

Current

My understanding is that

1. if any such function throws an exception then FSharp.Data.Adaptive never "saves" the exception as a result, it is just always propagated all the way up to the routine that requested the result.
2. there is no special treatment if OperationCancelledException is thrown, and so throwing that exception is a valid way to represent cancellation.
3. however there is no cancellation token propagated, so these functions have to capture an exterior cancellation token.

Yep, that's right

2. some parts of the dependency graph calculation may have been committed, and this is done in an atomic way (there is a related question about concurrent update requests)

Concurrency is sort of supported. A short overview on what happens:

1. One can modify things concurrently without breaking anything in the system
2. When doing this computations like AVal.map (-) (AVal.map id a) a may temporarily return unexpected results when changing the input. However for most use-cases this can be worked around.

Integration Ideas

Now one could imagine a variation on FSharp.Data.Adaptive that either

1. propagates a cancellation token

This would actually be quite easy by adding a field to AdaptiveToken

2. uses a computation expression like cancellable { ... } to represent synchronous cancellable code

I think using such a thing would severely complicate things and a facade mimicing this could also be implemented when 1 is implemented.

3. uses an existing computation like async { ... } that has cancellation built in (but is richer, as it represents asynchronous code)

Async/Task sort of raises a fundamental question:
files |> ASet.mapAsync File.ReadAsync may initially be empty and change whenever a file is read or wait until all reads are finished, etc.

Nonetheless we had ASet.mapAsync in a very old version but these things tend to get very unpredictable in precense of adaptive re-execution.

Thoughts

So overall I think passing a CancellationToken around is very straight-forward and enables users to cancel synchronous computations via exceptions (which of course is a bit wonky but that's just the only way that doesn't affect the standard API

Hope that helps a bit and I'd be happy to help with adding some adaptivity to the compiler/FCS. 😎
Cheers

[dsyme]

Hey cool, yes, that makes sense

TBH the "standard" representation of synchronous code in .NET is really functions 'Args * CancellationToken -> 'Result where the thing raises OperationCancellationException on cancellation. So it sounds like adding CancellationToken to AdaptiveToken is the right way to go

... files |> ASet.mapAsync File.ReadAsync ...

FWIW I think this is no different to files |> ASet.map File.Read and so the problem already exists. But yes any mention of async tends to also imply uses of asynchronous I/O or parallel execution (and other spliting into multiple sub-computations), though strictly speaking I think it's orthogonal - any of our other computation modalities may have that problem

BTW another topic that came up is about polling and watching in the file system. The F# compiler currently polls the timestamps on all dependent files prior to every step of the background computation. Presumably this would mean polling and modifying a cval for each file at the start of each transact or force. There is presumably no other choice, e.g. no way to register "objects to be polled for changes on any transaction".

It may also be interesting to give more samples/demos with database and file system connections into this system, e.g. a sea of adaptives adapting to changes on disk. And in general more systems programming samples. Every time I build a project/file-watcher tool like fsdocs I think it should be using adaptive....

[krauthaufen]

FWIW I think this is no different to files |> ASet.map File.Read and so the problem already exists. But yes any mention of async tends to also imply uses of asynchronous I/O or parallel execution (and other spliting into multiple sub-computations), though strictly speaking I think it's orthogonal - any of our other computation modalities may have that problem

Our implementation was actually starting the tasks (conceptually) in parallel and the entries were fed into the set as they arrived. So there was a huge difference to files |> ASet.map File.Read since the system internally managed everything. In other words aval<'T> is somewhat similar to Task<'T> in that sense that a task changes its value exactly once and an aval may change its value more often. One combinator we had in early prototypes was AVal.ofTask : defaultValue : 'a -> Task<'a> -> aval<'a> that initially held defaultValue and when the task was finished changed to its result.

It may also be interesting to give more samples/demos with database and file system connections into this system, e.g. a sea of adaptives adapting to changes on disk. And in general more systems programming samples. Every time I build a project/file-watcher tool like fsdocs I think it should be using adaptive....

Point taken, however there's an example for precisely that (admittedly not really succinct) 😁
https://github.com/fsprojects/FSharp.Data.Adaptive/blob/master/src/Demo/EventInterop/Program.fs#L58

Maybe we should just add common things like a AdaptiveFileSystem to a new lib FSharp.Data.Adaptive.IO ?
What do you think?

[dsyme]

Point taken, however there's an example for precisely that (admittedly not really succinct) 😁

Cool, I hadn't seen that! I'll take a close look.

Maybe we should just add common things like a AdaptiveFileSystem to a new lib FSharp.Data.Adaptive.IO ? What do you think?

Yes, I think that would be great though I don't mean to distract - I wouldn't use it myself immediately but might when I next revisit fsdocs

[krauthaufen]

Hey, I just added a CancellationToken to AdaptiveToken which allows us to implement cancelable adaptive computations. It's currently not exposed in a user-friendly way, but it can be used via (AVal|ASet|AList|AMap).custom (getting the AdaptiveToken explicitly)

For the moment I think we should just keep it that way and wait until user-combinators converge to some decent API for that.
We could certainly use async in e.g. AVal.mapAsync : ('a -> Async<'b>) -> aval<'a> -> aval<'b> but that would still mean that things run synchronously (but cancelable) which might be confusing .

[krauthaufen]

After some benchmarking by @luithefirst we found that including the CancellationToken in the AdaptiveToken causes significant overhead.

With CancellationToken

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
CValGetValue	261.7 ns	2.42 ns	2.26 ns	-	-	-	-
AValueGetValue	262.2 ns	1.59 ns	1.33 ns	-	-	-	-
CValUpdate	1,155.7 ns	8.26 ns	7.32 ns	0.1259	-	-	792 B

Without CancellationToken

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
CValGetValue	26.70 ns	0.139 ns	0.130 ns	-	-	-	-
AValueGetValue	28.01 ns	0.187 ns	0.175 ns	-	-	-	-
CValUpdate	904.03 ns	8.161 ns	7.234 ns	0.1259	-	-	792 B

So I think it should probably be passed via a ThreadStatic variable or something similar. Actually that could be done in an external library but nonetheless some built-in support might be nice. What do you think @dsyme?

[luithefirst]

I just did some more analysis. When measuring the first two benchmarks using a Stopwatch, there is no difference and both run at 28ns/Op. I also could not see any excessive overhead when using the performance profiler. By adding a *2 to the benchmark method, also the implementations with CancellationToken is suddenly measured with about 28ns:

member x.CValGetValue() =
        (cval |> AVal.force) * 2

Unfortunately, I could not print any disassembly with BDN to inspect what is going on. Either some optimization must fail or there is a bug.

When I manually measure the CValUpdate time, I get the same 25% overhead that is measured using BDN. The performance profiler does not directly reveal where the 25% is going to, the GetValue tree just increases in time and there are more samples in [External Code] and [Unwalkable]. The GetValue call tree has a depth of ~14 (containing GetValue 4 times) where the AdaptiveToken is passed recursively. I cannot tell if this kind of overhead can be expected when the argument size is 128bytes instead of 64, but it seems to be the case.

[krauthaufen]

FYI @dsyme

It may also be interesting to give more samples/demos with database and file system connections into this system, e.g. a sea of adaptives adapting to changes on disk. And in general more systems programming samples. Every time I build a project/file-watcher tool like fsdocs I think it should be using adaptive....

I just implemented AdaptiveFile and AdaptiveDirectory and a little example using them HERE

Hope that helps with future directory-watchers 😁
Cheers

[dsyme]

Lovely, thank you. I tweeted about this here: https://twitter.com/dsymetweets/status/1389545040582791176

Does the recursive directory structure watcher corretly take into account sub-directory creation and deletion? And does it prevent sub-directories from being deleted due to locking? Just wondering as I recall having that kind of problem in the past

[krauthaufen]

Cool 👍

Actually I didn't check nested deletions, so i guess that means it will have the locking problem. Semantically the nested removal should work fine via ASet.collect

We should certainly look into the locking things...

[TheAngryByrd]

For posterity, @krauthaufen gave me a prototype that we've been using in FsAutocomplete and has worked extremely well.