Asynchronous programming and Discrete Event Simulation

[multun]

In order to run a multi-train simulation, we need to run a number of asynchronous,
concurrent jobs. We previously did it using a timeline of events, where each events
had a list of callbacks to run.

We had no abstractions whatsoever over events and callbacks, and it caused
a major issue: components were very tightly integrated, with no clear API boundaries.
It made the whole system very hard to understand.

Interestingly, it didn't have to be this way, as any asynchronous computation model
works, as long as there is the ability to implement delays based on a virtual clock.

Finding out what model fits discrete event simulation and java the best turns out to
be a very hard issue.

Requirements

• requirement Ability to have clear async API layers:

  interface ReservationState {
      async ReservationResult reserveRoute(Route route);
      void occupyTVDSection(TVDSection tvdSection);
      void releaseTVDSection(TVDSection tvdSection);
  }

• nice to have async exception propagation

• requirement ability to audit exchanged messages

• requirement ability to implement a virtual clock, which involves hooking into the task / message scheduler

Design choices

There are a number of design choices that could be made:

• are objects actors communicating with messages, or tasks waiting on awaitables?
• in case of an actor system, is there an asynchronous state machine framework for handling messages?
• in case of a task system, do async function calls inside tasks create tasks?

Existing DES libraries

• SimPy is pretty much the only good quality asynchronous discrete event simulation library.
  It has a C# port called SimSharp. SimPy implements an event loop with a single priority
  queue of events, sorted by time and priority. Each events has callbacks, which are things like
  "continue the execution of this process". Contrary to asyncio and rust, awaiting subroutines
  is implemented as a separate task, just like with CSharp. Just like asyncio, processes are
  implemented on top of event callbacks.

• Trainspotting, an experimental train simulator, also implements asynchronous discrete
  event simulation in rust.
  It has two simple concepts: Events, and processes. There are no callbacks involved,
  processes wait directly on a list of events to occur.

• https://github.com/Olivier-Boudeville-EDF/Sim-Diasca

Existing event loop models

These systems do not directly provide discrete event simulation features, but could
be used to implement some:

• Rust has a task based model. Each task corresponds to an asynchronous "thread",
  has an associated future, which will eventually yields a value.
  Tasks only run when woken up, typically by one of its dependencies.
  When a task runs, the executor calls poll on the task's future. poll gets a wakeup()
  callback, which can be given to dependencies so they can awaken the task later on.

• Python's asyncio, just like Rust, has a concept of task analogous to threads.
  The asyncio event loop is different in that it does not maintain a queue of scheduled
  tasks but only schedules and invokes callbacks. It maintains three collections of callbacks:
  The ready to be called callbacks, the callbacks that become ready at a future time, and
  the callbacks waiting on file descriptors. Callbacks are wrapped inside handles to enable cancellation.

  A somewhat elegant aspect of this design is that tasks are implemented using callbacks: when
  a task is created, its step function is added as a ready callback so it runs a first time.
  The generator progresses, yielding a Future to wait on. When this future completes,
  the step method of the task is called again.

  Task subclasses Future so they can be awaited on.
  (see this blog post for reference)

• Javascript has a mixed task and callback system baked into the language, similar to asyncio

• CSharp also has a notion of task, albeit different from rust's: a csharp task is more like an
  asynchronous computation, not an asynchronous thread. In CSharp, every async function
  of the call stack is a Task. Async and await are syntax sugars which generate a state machine,
  awaiting is done using callbacks which re-schedule the task.
  You can implement your own task scheduler (see this blog post for reference)

• Kotlin works pretty much like csharp: coroutines are compiled to state machines, which all get
  an implicit continuation callback (called a continuation), which must be called asynchronously
  to resume the caller if the call cannot complete immediately.
  Interestingly, kotlin also enables intercepting these callbacks, which makes implementing
  cooperative multitasking unusually easy.
  Coroutine interceptors which dispatch coroutines must be CoroutineDispatchers for the debugger to work properly.
  Custom time handling can be implemented by using a custom CoroutineDispatcher which implements kotlinx.coroutine.Delay.

  Its interoperability with java makes kotlin the best contender so far.

  Each coroutine lives in a scope, and need to take a CoroutineScope implicit argument in order to start new coroutines.
  The scope

  (see the specification)

Useful links:

• some thoughts on asynchronous API design

Actor models

Interestingly, actor models (as implemented in erlang or akka) could be the right tool for the job.

Associating context to async tasks

https://docs.google.com/document/d/1tlQ0R6wQFGqCS5KeIw0ddoLbaSYx6aU7vyXOkv-wvlM/edit

Java libraries

• https://activej.io/async-io/eventloop

[hammer498]

First of all, this is a really really helpful writeup, thank you

I saw the issue you opened with Kotlin here
Kotlin/kotlinx.coroutines#3229
Asking to make more of their api public and your proof of concept here
https://github.com/osrd-project/kotlin-async-des

I'm curious if you have any updates on this topic. Did you end up using kotlin coroutines with a custom scheduler in your project? If so what has your experience with them been? I am considering doing something extremely similar.

[multun]

Did you end up using kotlin coroutines with a custom scheduler in your project?

It never saw much use, as it was decided to delay implementing the multi-train simulation. We started though, you can still see parts of it in the kt-osrd-sim-interlocking module.

We also have some tests which simulate multiple trains moving on a virtual clock.

I still think it's the best way to go if you really have to. I later found out that you can run async rust on a virtual clock too.

[galenseilis]

Thank you for sharing these resources.

I'm not (yet) convinced of the following:

In order to run a multi-train simulation, we need to run a number of asynchronous, concurrent jobs.

Why would we need our program to have concurrency in order to simulate a system that has concurrency? Could you elaborate?

[hammer498]

My impression is you don't "need" to in a strong sense it is just a nicer programming model. Callbacks are a harder model to use than coroutines which is why coroutines are gaining popularity. Coroutines let you write code that looks concurrent even if it is ultimately backed by a single thread. This is what @multun was getting at when he said

We had no abstractions whatsoever over events and callbacks, and it caused
a major issue: components were very tightly integrated, with no clear API boundaries.
It made the whole system very hard to understand.

I've found the same to be true and used asyncio in python and custom dispatchers in kotlin to get around the problem.

[galenseilis]

@hammer498 Thanks for sharing that! Definitely food for thought.

FYI, since SimPy was mentioned above: I have rewritten some of the examples in SimPy docs using a synchronous approach (based on events I guess?). A tradeoff I've found is that SimPy (which uses classic coroutines) appears to have better LoB as a readability criterion, but it is also slower than the synchronous code that I have written for the same examples. These tradeoffs seem to be stable across examples, but I am curious if this is just a Python thing or if the tradeoff would occur in other programming languages like Rust.

[hammer498]

That makes sense to me, abstractions are rarely truly zero cost. In kotlin I found simulation coroutines are ~15%-20% slower in benchmarks that just schedule events as fast as possible. In simulations that are actually doing simulation work though the difference isn't measurable. Time spent pushing/popping events is often negligible compared to the time spent running model code