RFCs [RFC] Better Future

(Part of RFC series #5728)

I'd like to propose changes to Future type. I have two intents: to make it more efficient and easier to use. After these changes, Future will be really similar to reactor.nim Future and mostly backward compatible.

[ ] make Future fat-pointer, so non-blocking case can return Futures without allocations. E.g:
```
type Future[T] = object
   hasValue: bool
   of true: val: T
   of false: reference: FutureVar[T]
```
(optional: make it fat pointer only for small types like int or ref)
[ ] deprecate Future.complete, as it prevents some optimizations and anyway is rarely needed. FutureVar will need to be used to complete Futures.
[x] store callbacks in linked list, so multiple parties can wait for future completion (this doesn't affect performance, first item of the linked list can be inlined into struct). callback= will still clear that list.
[ ] add then proc (aka fmap from monadic perspective), which prevents callback hell without using {.async.} - this is especially useful with point 3
[ ] introduce Result[T] type, which represents either T or an error. Move error handling from Future to Result (by replacing value: T, isError: bool, stacktrace: string with result: Result[T] field in FutureVar[T]).
[ ] [probably later] copy stack trace generation for Result[T] from reactor.nim. Currently, only place where error is generated is saved, reactor.nim generates full stacktrace across {.async.} procs.
[x] move Future to its own module e.g. asyncbase.nim (that will allow reactor.nim and other potential async libraries to use it)

Apr 19 '17 13:04 zielmicha

store callbacks in linked list, so multiple parties can wait for future completion (this doesn't affect performance, first item of the linked list can be inlined into struct). callback= will still clear that list.

From my tests storing callbacks in linked lists affect performance heavily, and not the best way.

Apr 20 '17 06:04 cheatfate

Regarding 3. and 4., I agree that supporting multiple callbacks and a then operator would be quite useful. There are several ways to implement this efficiently:

a) callbacks stored in a sequence b) callbacks stored in a linked list, where the nodes are allocated from a small arena c) optimize the case where a single callback is present by handling multiple callbacks with double indirection - the first callback is written to a normal closure pointer and when a second callback is added, this closure gets replaced by another one, now calling the multiple callbacks.

Apr 20 '17 08:04 zah

As @zielmicha mentioned, the first node of a linked list can be inlined into the Future itself - this way, the case where a single callback is present will have the same performance as today. Multiple callbacks may suffer a little in performance, but they are not supported today anyway, so it is a strict improvement

Apr 20 '17 14:04 andreaferretti

@andreaferretti if we are talking about asynchttpserver (for example), most of the time there at least 2 callbacks registered.

It looks like

recv(1) sets callback(1).
In frame context of callback(1), recv(2) is called and callback(2) stored inside of queue.

At this stage there is 2 callbacks registered.

After exiting callback(1), it is removed from queue.

At this stage there is 1 callback registered.

So if you want to improve speed you need to store at least 2 callbacks, then you will be not affected by linked-list performance issue.

Apr 20 '17 15:04 cheatfate

I am a little confused. Futures currently only support a single callback. How is it that most of the time there are 2 registered?

Apr 20 '17 15:04 andreaferretti

Ok, maybe its my mistake i have talked about callbacks inside of dispatcher, not about callbacks inside of Future.

Apr 20 '17 15:04 cheatfate

Thank you for making this list. I am happy with most of your proposed changes although I do have some reservations/questions:

deprecate Future.complete, as it prevents some optimizations and anyway is rarely needed. FutureVar will need to be used to complete Futures.

This proc is used everywhere so I'm not comfortable with your plans for deprecating it.

make Future fat-pointer, so non-blocking case can return Futures without allocations. E.g:

This is a nice optimisation but how often are futures used for the "non-blocking case?" Changing this will again require many changes (newFuture vs. initFuture).

introduce Result[T] type, which represents either T or an error. Move error handling from Future to Result (by replacing value: T, isError: bool, stacktrace: string with result: Result[T] field in FutureVar[T]).

Perhaps we should implement an Either[A, B] type (ala Haskell's Data.Either)? We already have an Option[T] type in the stdlib.

What is the aim of this? Object structure organisation?

[probably later] copy stack trace generation for Result[T] from reactor.nim. Currently, only place where error is generated is saved, reactor.nim generates full stacktrace across {.async.} procs.

What do these look like? I am very unhappy with async's current stack traces but didn't see any (easy) way to make them better.

Apr 23 '17 22:04 dom96

Future.complete deprecation - it's not a problem to not deprecate it. I just think it's a bad idea to have both sides of Future in a single type (e.g. like in Javascript, but not like in C++ or Dart). I withdraw my opinion that it prevents optimizations.
How many calls are "non-blocking" depends on the use case. For example, in best case of read(4) (e.g. reading integer) on buffered socket with 64k buffer, 99.993% calls will be "non-blocking". Note that buffered sockets are not currently implemented in stdlib, but are in reactor.nim. This optimization is really important, because it turns "non-blocking case" of readInt to only few assembly instructions - jg to check if there is data, mov to copy the integer and add to move pointer (of course GCC has to be sufficiently smart, but when I've inspected assembly, it seems it is in many cases).

I think we can keep newFuture, because Future[T] will still morally be a pointer.
We could do Result[T] = Either[T, ErrorDescription], but I don't see any benefits except mathematical purity. (note that we can't do Result[T] = Either[T, ref Exception] without changing Exception, because ErrorDescription also has to keep async stack trace).

The aim of separating Result[T] from Future[T] is code clarity and ease of implementation. When I performed this separation in reactor.nim, a lot of duplicated code could suddenly be removed.
The stack trace is collected when await encounters error in Future that was awaited. See awaitInIterator asyncmacro.

Apr 24 '17 13:04 zielmicha

Is it a good time to consider future cancellation feature?

Apr 27 '17 16:04 yglukhov

I think that the Future type (or perhaps it is FutureVar or Result) can have an optional user-defined OperationState type parameter (defaults to void) that can be used to implement async operations with cancellation or progress reporting.

Apr 27 '17 18:04 zah

I don't know any way to cleanly integrate cancellation with Future. Future is an abstraction for a value that will be available in future, it doesn't know what work is needed. I would love to be proven wrong.

As far as I know there is no better method to implement cancellation then using explicit cancellation tokens (like in C#).

It's possible to do it automatically, akin to @zah suggestion, by registering Futures to cancellations tokens when they are awaited. Equivalent description of the same idea: result of then(f: Future[T], p: proc) has the same cancellation token as f.

The biggest drawback of this approach is that some futures may be cancelled by accident, especially when then is called multiple times on one Future or it's awaited multiple times.

Apr 27 '17 19:04 zielmicha

I once thought that exceptions could be used for future cancellation, but I no longer think that is possible. So yeah, I haven't come up with any other ideas for this feature, but I haven't thought about it at length yet.

Future.complete deprecation - it's not a problem to not deprecate it. I just think it's a bad idea to have both sides of Future in a single type (e.g. like in Javascript, but not like in C++ or Dart). I withdraw my opinion that it prevents optimizations.

If it doesn't prevent optimisations then I would prefer to keep it. Why do you think it's a bad idea?

Note that buffered sockets are not currently implemented in stdlib, but are in reactor.nim.

Buffered sockets are implemented in the stdlib. (The newSocket proc takes a buffered param).

And yes, you're right, when considering buffered sockets this optimisation should be really good. So I'm all for it. It would be nice to see some benchmarks as well, even if it is just wrk vs. asynchttpserver before and after this change. Question is, can we implement this without breaking anything? Even if the answer is no it might be worth it, but it depends how much change is required.

The aim of separating Result[T] from Future[T] is code clarity and ease of implementation. When I performed this separation in reactor.nim, a lot of duplicated code could suddenly be removed.

Can you identify code which you think could be simplified by going ahead with this separation?

The stack trace is collected when await encounters error in Future that was awaited. See awaitInIterator asyncmacro.

That doesn't really show me what the stack traces look like. Do you have any examples?

May 01 '17 16:05 dom96

If it doesn't prevent optimisations then I would prefer to keep it. Why do you think it's a bad idea?

Future should represent value that may be available in future. In this view it doesn't make sense to 'complete' it. Of course, it's just aesthetic opinion.

And yes, you're right, when considering buffered sockets this optimisation should be really good. So I'm all for it. It would be nice to see some benchmarks as well, even if it is just wrk vs. asynchttpserver before and after this change. Question is, can we implement this without breaking anything? Even if the answer is no it might be worth it, but it depends how much change is required.

I might try this, it shouldn't require too many changes. I doubt I'd get good speedup, asynchttpserver already uses client.recvLineInto. And recvLineInto already optimized in a way that's not available for 'normal' code (it peeks into socket internals).

Can you identify code which you think could be simplified by going ahead with this separation?

In current asyncfuture, no. It's already simple. But if I were to implement some features that are in reactor.nim, but not in stdlib yet, it makes sense:

stack trace generation (no need to clutter loop code with it) and error handling in general
multithreading (it makes sense for procs executed in thread pool to return Result[T], but not Future[T])
tryAwait that works like await, but returns Result[T] instead of T and never throws exceptions (similar to bare yield in asyncdispatch.async macro)

That doesn't really show me what the stack traces look like. Do you have any examples?

I don't have good example right now, so I made a synthetic one:

import reactor

proc foo(i: int) {.async.}

proc bar(i: int) {.async.} =
  if i == 0:
    asyncRaise "my error!"
  await foo(i)

proc foo(i: int) {.async.} =
  await bar(i-1)

when isMainModule:
  foo(5).runMain

Traceback (most recent call last)
a.nim(14)                a
future.nim(350)          runMain
future.nim(345)          runLoop
future.nim(140)          get
result.nim(104)          get

Asynchronous trace:
a.nim(11)                foo
a.nim(8)                 bar
a.nim(11)                foo
a.nim(8)                 bar
a.nim(11)                foo
a.nim(8)                 bar
a.nim(11)                foo
a.nim(8)                 bar
a.nim(11)                foo
a.nim(7)                 bar

Error: my error! [Exception]

May 01 '17 17:05 zielmicha

Future should represent value that may be available in future. In this view it doesn't make sense to 'complete' it. Of course, it's just aesthetic opinion.

Perhaps I misunderstood, but that is precisely what Future represents. And it makes perfect sense to complete it.

I might try this, it shouldn't require too many changes. I doubt I'd get good speedup, asynchttpserver already uses client.recvLineInto. And recvLineInto already optimized in a way that's not available for 'normal' code (it peeks into socket internals).

Go for it. Would be interesting to see nonetheless.

We also have recvInto. I think that covers the required optimisations pretty well.

multithreading (it makes sense for procs executed in thread pool to return Result[T], but not Future[T])

I don't think that's true. Spawn already returns a FlowVar[T] which is a lot like the Future[T] type.

tryAwait that works like await, but returns Result[T] instead of T and never throws exceptions (similar to bare yield in asyncdispatch.async macro)

Why implement this when it is already covered by yield?

stack trace generation (no need to clutter loop code with it) and error handling in general

This point might be true, but stack trace generation is already done to some extent and I don't consider the code to be cluttered.

I don't have good example right now, so I made a synthetic one:

That looks nice and I do think asyncdispatch's trace backs need to be improved. I'm afraid I disagree that this separation into Result[T] should be done though.

For reference, here is how the traceback currently looks like for a similar asyncdispatch program. (btw, why asyncRaise and not just raise?)

import asyncdispatch

proc foo(i: int) {.async.}

proc bar(i: int) {.async.} =
  if i == 0:
    raise newException(Exception, "my error!")
  await foo(i)

proc foo(i: int) {.async.} =
  await bar(i-1)

when isMainModule:
  waitFor foo(5)

Traceback

Traceback (most recent call last)
a12.nim(14)              a12
asyncdispatch.nim(1461)  waitFor
asyncfutures.nim(220)    read
Error: unhandled exception: my error!
  bar's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncmacro.nim(385)      foo
    asyncmacro.nim(34)       cb
    a12.nim(11)              fooIter
    asyncmacro.nim(385)      bar
    asyncmacro.nim(34)       cb
    a12.nim(8)               barIter
    asyncmacro.nim(385)      foo
    asyncmacro.nim(34)       cb
    a12.nim(11)              fooIter
    asyncmacro.nim(385)      bar
    asyncmacro.nim(34)       cb
    a12.nim(8)               barIter
    asyncmacro.nim(385)      foo
    asyncmacro.nim(34)       cb
    a12.nim(11)              fooIter
    asyncmacro.nim(385)      bar
    asyncmacro.nim(34)       cb
    a12.nim(8)               barIter
    asyncmacro.nim(385)      foo
    asyncmacro.nim(34)       cb
    a12.nim(11)              fooIter
    asyncmacro.nim(385)      bar
    asyncmacro.nim(34)       cb
    a12.nim(8)               barIter
    asyncmacro.nim(385)      foo
    asyncmacro.nim(34)       cb
    a12.nim(11)              fooIter
    asyncmacro.nim(385)      bar
    asyncmacro.nim(34)       cb
    a12.nim(7)               barIter
  foo's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(34)       cb
    asyncmacro.nim           fooIter
    asyncfutures.nim(220)    read
  bar's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           barIter
    asyncfutures.nim(220)    read
  foo's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           fooIter
    asyncfutures.nim(220)    read
  bar's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           barIter
    asyncfutures.nim(220)    read
  foo's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           fooIter
    asyncfutures.nim(220)    read
  bar's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           barIter
    asyncfutures.nim(220)    read
  foo's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           fooIter
    asyncfutures.nim(220)    read
  bar's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           barIter
    asyncfutures.nim(220)    read
  foo's lead up to read of failed Future:
    Traceback (most recent call last)
    a12.nim(14)              a12
    asyncdispatch.nim(1081)  waitFor
    asyncdispatch.nim(1116)  poll
    asyncdispatch.nim(180)   processPendingCallbacks
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(50)       cb
    asyncfutures.nim(156)    fail
    asyncmacro.nim(34)       cb
    asyncmacro.nim           fooIter
    asyncfutures.nim(220)    read [Exception]

May 02 '17 09:05 dom96

Future should represent value that may be available in future. In this view it doesn't make sense to 'complete' it. Of course, it's just aesthetic opinion.

In fact most future systems (e.g. Scala, Java, Javascript) split the thing in two: a mutable value that needs to be completed and is often kept private, and a read only view of the value which represents the "value available at a later time", which is conceptually an immutable piece of data

May 02 '17 09:05 andreaferretti

@dom96 Again, separation of Result from Future boils down to aesthetic preference. Personally I can't imagine how not splitting it may be preferred, but I'm afraid you have the casting vote here.

I'll implement everything within Future in stdlib and maybe just add wrapping procs working on Result in reactor.nim.

May 02 '17 12:05 zielmicha

Python asyncio cancellation is interesting: https://docs.python.org/3/library/asyncio-task.html

Jun 01 '17 12:06 zielmicha

Regarding cancellation, I quite like .net's concept of a CancellationToken. A simple cancel() method on a future would be good, but would it also cancel any chid futures (eg: I have a future that continuously reads from a socket - will cancelling this future cancel the currend future to read from the socket?)?

Jun 27 '17 15:06 euantorano

In go there is a similar concept in contexts

May 12 '22 13:05 mildred