Completing the Nim async/await implementation

[dom96]

The Nim async/await implementation has been successfully used in production for many years now, both in real-world use cases (NimForum, among others) as well as in benchmarks (TechEmpower benchmarks via Jester/HttpBeast). It has also been adapted into the Chronos implementation used by Status for their Ethereum client implementation.

All of these projects have established it as a reliable and easy way to write highly concurrent applications in Nim.

As far as I know, there are three things missing, some more important than others. This RFC aims to document what those are and hopefully drum up some support for their implementation. I strongly believe that the effort needed to implement these is in general low, with the impact being high.

But I would also like to open this RFC to others, if not already covered by the list below, what do you feel is missing? Can we implement a solution within the existing async/await implementation?

Concurrency + Parallelism

A big pain point with Nim's concurrency is that it does not integrate well with Nim's parallelism. I think that a simple fix here would be to make it possible for spawned threads (FlowVars) and channels to be awaitable.

I believe that there isn't a need to head towards the Golang Goroutines which mix concurrency and parallelism. For a systems programming language, having these as separate systems is wise and ultimately gives more control. This is particularly important for something that is in the standard library.

Software such as httpbeast have proven that scaling async/await across threads can be done and that it works well. For other non-server use cases an awaitable threads implementation will be a great stand-in, until we can figure out the disadvantages of this approach (if any).

Future Cancellation

Right now, the only way to cancel a pending operation is to close the FD it is working on. This works in certain circumstances, but is somewhat hacky and not flexible enough. A formal way to cancel futures would be ideal.

Chronos already implements this so it can be used as a source of inspiration for how this should be implemented.

Future Streams

The existing implementation has its issues (just search around the Nim repo for issues relating to future streams) and needs a rework. This is an important component to enable streaming large pieces of data to clients.

A nice practical solution here could be to rely on sendfile.

Useful Resources

• https://tomaka.medium.com/a-look-back-at-asynchronous-rust-d54d63934a1c - cancellation and challenges in the actor model

[disruptek]

Can you speak to the obstacles preventing Nim from adopting Chronos and the advantages of two parties maintaing separate and unequal implementations?

[dom96]

The only obstacles I foresee are related to breaking backwards compatibility. I'm not sure to what extent the two have diverged, if it's just as simple as replacing Nim's current async/await with Chronos then that would be nice. But I'm not sure that is the case.

Looking at https://github.com/status-im/nim-chronos/wiki/AsyncDispatch-comparison, the following seems to be the biggest divergence:

Removed all IO primitives (recv(), recvFrom(), connect(), accept(), send(), and sendTo()) from the public API, and moved all their functionality into Transports.

At the end of the day I would defer the question to Status, they are the ones that hard forked async/await after all and they know how the two have diverged since then.

[mratsim]

Looking more into CPS and async, it seems to me like CPS are actually lower levels than async/await.

In particular they replace closure iterators (and potentially inline iterators). This means that a deprecation path would be to reimplement closure iterators in terms of CPS so that current async/await applications can still work as is while we figure out the path forward.

Then the questions become:

• What are the issues from an user and a maintainer perspectives regarding closure iterators
• What does asynchronous IO looks like:
  • with CPS?
  • with async/await + closure iterators
  • with other approaches in particular the newer ones which benefits from hindsights from C#
    • Rust readiness-based/poll-based futures:
      • https://aturon.github.io/blog/2016/08/11/futures
      • https://aturon.github.io/blog/2016/09/07/futures-design
      • https://jblog.andbit.net/2019/11/10/rust-async-execution
      • https://tmandry.gitlab.io/blog/posts/optimizing-await-1
      • (limitation: cancellation for IOCP) https://gist.github.com/Matthias247/ffc0f189742abf6aa41a226fe07398a8
      • (limitation: syntax) https://gist.github.com/Matthias247/5e5e7430149bbb04eebf18cf31747fe0
    • Kotlin CPS-based coroutines: https://github.com/Kotlin/KEEP/blob/master/proposals/coroutines.md
    • Swift coroutines: https://gist.github.com/lattner/429b9070918248274f25b714dcfc7619
    • Greenlet: https://greenlet.readthedocs.io/en/latest/index.html

Regarding the issues, as a user I see:

• domains that require no allocation like embedded
• domains that require careful allocation like multithreading
• weak ergonomics, especially for functional programming: https://github.com/mratsim/nim-project-euler/blob/09c6bf5/src/lib/functional.nim#L26-L46
  I can't comment on the maintenance burden of closure iterators.

[Vindaar]

My main criticism of async / await in Nim (I don't know whether it's a documentation issue, lack of understanding on my part or something technical):

If I have some proc that is blocking, how do I turn that into something that can be used with async/await? I understand that once the main thread is blocked "that's it". But I always though the "magic" of async/await is to wrap that blocking call in something that let's the main thread unblocked.

That's why I never use async/await, but rather simply create a second thread that I ask if it's done via a channel. Simply because for the things I needed async/await for there isn't an Async* version in the stdlib. And I don't understand how to write my own async version of something.

I might have more constructive criticism, if my async usage went beyond exactly two (almost identical) usages of AsyncHttpServer to communicate with a JS client via websocket.

[dom96]

If I have some proc that is blocking, how do I turn that into something that can be used with async/await? I understand that once the main thread is blocked "that's it". But I always though the "magic" of async/await is to wrap that blocking call in something that let's the main thread unblocked.

@Vindaar That is something I've also found to be a pain point. A classic example is even featured in my book: reading from stdin. I think that the proposal I've written about above would solve this pretty well, simply spawn the blocking proc in a new thread and await it. Job done :)

@rayman22201 even made a great start on it in nim-lang/Nim#12232 and nim-lang/Nim#12372. We could get pretty far in resurrecting this.

And I don't understand how to write my own async version of something.

That really depends on what you're doing. If you're writing a native Nim version of something then that should be fairly trivial. If you're wrapping a C library and want to use it in an async way then it gets trickier, and it would be nice to set up a tutorial series for this.

[zah]

Both AsyncDispatch and Chronos pay a hefty price for some fundamental inefficiencies in the current async approach:
status-im/nim-chronos#2

If backwards compatibility is to be broken, Nim can still try to aim higher than the minimal upgrades suggested above.

Otherwise, I happen to know that @alehander92 has implemented cancellation for AsyncDispatch in a private branch. His approach is different from Chronos - the inspiration was taken from the way C# implements cancellation. A very brief explanation is that the code relies on something called "cancellation token" which is passed as a hidden argument forward in the async calls. This avoids the "backwards" links that Chronos must maintain from nested futures to the parent that spawned them. The backwards links are somewhat more problematic because they must be stored in a dynamically allocated container and they introduce cycles that will create more difficulties in an ORC/ARC scheme.

[mratsim]

P1) All non-ref input parameters to async procs must be copied is something that I also experience in Weave and may be a significant source of overhead in short lived tasks (which fortunately doesn't happen as often for CPU as for IO).

This was discussed with Araq and one solution I proposed is lent return value overloading: https://irclogs.nim-lang.org/17-12-2020.html#09:11:27

Basically you can have a return value be either

proc foo(a, b, c: Parameters): Future[RV] =
  result.obj = create(RV) # Allocation on heap

template foo(a, b, c: Parameters): lent Future[RV] =
  # template needed for alloca
  # do we want a typetrait `when escapeCallerScope(result)` instead?
  result.obj = alloca(RV) # Allocation on stack

Paper: Herlihy et al, Well-Structured Futures and Cache Locality, https://arxiv.org/pdf/1309.5301.pdf

Rust approach with readiness-based/poll-based future is another approach with other tradeoffs to ensure that futures can be allocated on the stack.

I think forcing futures to be evaluated in the caller or one of its child might be too restrictive hence I prefer a borrow-checker based optimization.

[Q-Master]

I think that for now is no need to completely switch to something which drops the compatibility with current version.
The asyncronous transports is a very good idea, but I think they can wait, because all of their functionality can be done right now using some more writing.
The main things which I wait myself are:

1. Futures cancellation (I think that Chronos variant is not that good). I am sure that not only cancel() should break the Future, but fail() and complete() should also do that.
2. Not stopping main loop if no callbacks running, but some futures are waiting like mentioned here

[al6x]

If I have some proc that is blocking, how do I turn that into something that can be used with async/await?

Exactly. This alone pretty much kills the appealing of async. Even without considering other problems.

The async programming is ok in JavaScript (I used it for many years in UI and Server). The concept itself is questionable, forcing human to do machine work (writing state machines-like code to handle control flow, sugared with async/await helpers). But, in JavaScript you have no other choice, that's the only thing you can have.

But adopting async concept in a language where you can choose other ways, not a good idea.

[mratsim]

I've been thinking about how to pass from the sync to async world and vice-versa and also how to allow 2 event loops to cooperate including asyncdispatch or Chronos but also event loops that we cannot ever hope to make compatible as a common primitive like CPS #295 cannot be built (for example Nim and JS/libuv).

At first I thought we could use AsyncChannel see:

• [WIP]: AsyncChannels[T]. status-im/nim-chronos#45
• @dom96 adding a file descriptor to Nim channels and Flowvar
• Mentioned by @rayman22201 in his "pseudo RFC for Async Channels and Flowvar"
• Related to @rayman22201 Virtual async event PR Virtual async events 2 Nim#12372

But instead I think we should build async condition variable or semaphores. Here's why:

Overview of the issues

Scenario 1. The async event loop is about to do a blocking operation or hands off heavy computation to another thread. It delegates work to a threadpool. It needs to subscribe to some "channel" that will hands the result back. In the sync world, this is a Flowvar. For async, that subscription should hand over control to the event loop until result is ready so ^ (sync/await) is not sufficient.

Scenario 2. Three services are cooperating, an UI thread, a networking thread and a worker thread. The UI thread cannot be blocked at all cost (see recent HN all-star post Speed is the Killer Feature), the networking thread can tolerate a couple second delays but more and timeouts kicks in unless you send keep-alive, the worker thread has no latency constraints. They establish one-to-one channels for each kind of processing requests and one-to-one channels for the result.

• UI <-> Networking requires 2 event loops to cooperate. One may even imagine that the UI stack is using asyncdispatch and the networking stack is using Chronos.
• UI <-> Worker requires event loop <-> plain thread to cooperate
• Networking <-> Worker requires event loop <-> plain thread to cooperate

Analysis

Making Flowvar and Channels awaitable

This adds too much baggage to Flowvar and Channels.

1. From an ergonomic point of view, we are creating complex types to try to handle both concurrency and parallelism, while they are separate concerns and we should have docs and tutorials for:

• concurrency
• parallelism
• mixing both

Forcing to use the same type for both will very likely bite us down the line.

2. From a performance point of view, adding a file descriptor to channels which means syscalls which means cache pollution and high context switch overhead makes them an automatic showstopper for most compute-bound tasks. This means that people who need high performance processing that is interleaved with IO, for example streaming video processing, will need to implement their own channel and will once again face the problem on "how to I make my custom channels compatible with async.

3. From an extensibility and composability point of view, for channels there is no one-size-fits all even if it's just serving the parallel world (and not concurrency). Here are the different flavors or channels

• whether it's buffered or unbuffered (rendez-vous, producer and consumer must be in the channel at the same time).
• whether it's single or multi producer and consumer.
  • A single-producer single-consumer channel is called SPSC
  • A multi-producer single-consumer channel is called MPSC
  • A single-producer multi-consumer channel is called SPMC
  • A multi-producer multi-consumer channel is called MPMC
    There are 2 kinds of SPMC queues:
  • a broadcast queue which duplicates all message enqueued to all consumers.
  • a "racing" queue that gives the message to the first consumer to request it.
• whether its bounded or unbounded
  • The behavior (errors, blocks or overwrites oldest) if bound is reached
• the progress guarantees
  • no guarantees
  • obstruction-free
  • lock-free
  • wait-free
• the item ordering guarantees:
  • no guarantees
  • serializability
  • linearizability
• whether the channel is intrusive (requires a next: Atomic[T] with T a ptr object) or not

Adding async synchronization primitives

Instead, we need the same synchronization primitives in Async as in the threaded world, so async locks and async condition variables (or async semaphores).

Then wrapper types can be

type
  AsyncFlowVar[T] = object
    fv: FlowVar[T]
    acv: AsyncConditionVariable
    alock: AsyncLock

  AsyncChannel[T] = object
    chan: Channel[T]
    acv: AsyncConditionVariable
    alock: AsyncLock

  AsyncRendezVousChannel[T] = object
    ## Unbuffered channel, both producer and consumer must wait for each other. Needed for CSP (Communicating Sequential Process)
    chan: T # Notice that we don't need a Channel[T] (assuming ARC/ORC or Boehm GC)
    acv_eventLoop0: AsyncConditionVariable
    alock_eventLoop0: AsyncLock
    acv_eventLoop1: AsyncConditionVariable
    alock_eventLoop1: AsyncLock

When the value is ready, the async condition variable of the consumer is signaled. This can be used with any channels and allow communication between any event loops and also any threadpool or multithreading runtimes.

This also does not pollute carefully tuned multithreaded primitives with kernel syscalls except at the interface between async and threads.

Implementation of async condition variable/event notifier

In all use cases where we need an async condition variable, there can be only one waiter, the event loop, but there can be multiple producers/signaler. This is unlike classic condition variables which can have multiple waiters/consumers.

I happen to have a high performance MPSC threadsafe event notifier in Weave for putting waiting threads to sleep that is formally verified:

https://github.com/mratsim/weave/blob/30bacedc841c5a4caf8424c5c342f352805ccf73/weave/cross_thread_com/event_notifiers.nim#L67-L148

proc park*(en: var EventNotifier) {.inline.} =
  ## Wait until we are signaled of an event
  ## Thread is parked and does not consume CPU resources
  ## This may wakeup spuriously.
  if not en.signaled.load(moRelaxed): # or `while not ...` if spurious wakeups are a problem
    if en.ticket == en.phase.load(moRelaxed):
      when supportsFutex:
        en.futex.wait(0)
      else:
        en.cond.wait(en.lock) # Spurious wakeup are not a problem
  en.signaled.store(false, moRelaxed)
  when supportsFutex:
    en.futex.initialize()

proc notify*(en: var EventNotifier) {.inline.} =
  ## Signal a thread that it can be unparked

  if en.signaled.load(moRelaxed):
    # Another producer is signaling
    return
  en.signaled.store(true, moRelease)
  discard en.phase.fetchXor(1, moRelaxed)
  when supportsFutex:
    en.futex.store(1, moRelease)
    en.futex.wake()
  else:
    en.cond.signal()

You just need to replace wait by wait on a FD and signal by signal on a FD and the event notifier becomes async friendly and can be used in association with channels and Flowvars to make them awaitable.

Note that in Weave this is also used in association with my internal channels.
If spurious wakeups are undesirable the line if not en.signaled.load(moRelaxed): can be replaced by while not en.signaled.load(moRelaxed):

[dumblob]

Sounds like a novel idea to me to align the async synchronization primitives API with concurrency primitives API in 1:1 fashion. Do you think it's doable to make the APIs not just aligned, but actually syntactically identical?

I mean, why to have both AsyncFlowVar[T] and ConcurrentFlowVar[T] (pardon the name - I didn't want to use FlowVar[T] to avoid confusion) and not just FlowVar[T] which would automatically in compile time decide whether an async or concurrent primitive is needed. The information should be already there from initialization.

[mratsim]

AsyncFlowvar[T] is actually Future[T] in Nim.

I think even though they are very similar at API level (to not say that they are the same), concurrent programming and parallel programming solve different problems. From a communication perspective because the underlying implementation is different, the problem domains are different and even the performance expectation (latency vs throughput) are different, it's best to color them differently for the language primitives.

Also from a maintenance and development perspective, the skill set for concurrent programming and parallel programming is very different. It might also be that new paradigm in either of those domains require evolving the Future or Flowvar and we don't want to be shackled by the other domain.

A library on top can then easily hide the differences for convenience or it can be lifted to an Awaitable[T] overarching concept.

[rayman22201]

@mratsim A few things. I stopped working on Virtual Async Event for several reasons, partially because I thought it was a dead end for some of the reasons you describe.
It was always a duct tape hack / temporary solution to the problem imo.
The big advantage was that would allow std lib Async to work with threads by only changing underlying implementation details, allowing the old API to work unchanged.

I like your idea of adding semaphores. They do have some of the same disadvantages as threaded semaphores though. You can get dead-locks and live-locks.

Even though it's not truly parallel if no threads are involved (no true race conditions), you can still get non-obvious orderings of async callbacks and run into trouble.

I still like the idea, but it's just something to be aware of.