Problem 652712 · hard · Level 06 Heuristics & Optimization

An Event Loop of Your Own

py-async · coroutines · event loop · scheduling · coroutine.send

asyncio hides its event loop, but the idea is small enough to write yourself, and that is the best way to understand what await really does. A coroutine object is a paused computation: coro.send(value) runs it until its next await has to wait, and the awaited object tells the loop why by yielding a request. Write run_all(coros), a loop with a virtual clock that starts at tick 0 and runs all the coroutines in coros, and every task they start, to the end.

The setup defines three awaitables. Each yields a request tuple to your loop, and the value your loop sends back becomes the result of the await:

  • await Sleep(k) yields ("sleep", k): resume this task at tick now + k, sending it that tick.
  • await Spawn(coro) yields ("spawn", coro): start coro as a new task and resume the spawning task at once (without giving way), sending the new task's number. The coroutines in coros are tasks 0, 1, ... in order, and new tasks get the next numbers.
  • await Join(n) yields ("join", n): resume this task when task n has finished, sending its return value; if task n raised, throw that exception into this task with coro.throw(exc). If task n has already finished, resume at once.

Scheduling rules: tasks that can run wait in a first-in first-out ready queue, initially the coroutines of coros in order; a new task joins the back of it. Start a task with send(None) and run it until it yields a request that makes it wait. A Sleep(0) puts the task at the back of the ready queue. When a task finishes, the tasks joining it join the back of the ready queue, in the order they started waiting. When the ready queue is empty, the clock moves to the earliest tick at which a task wakes up, and every task waking at that tick joins the ready queue in the order in which it went to sleep. If no task can ever run again but some have not finished, raise RuntimeError.

run_all returns (results, end): the return value of each coroutine of coros in order (or the exception object, for one that raised), and the tick at which the last task finished (0 if none waited).

The tests run coroutines written in setup helpers you can call with Run: countdowns(), same_tick(), family(), no_waiting(), deadlock() and swarm(n, seed). plain(results) shows exceptions by name and outcome(call) returns a result or an exception's name.

Examples

Input:  countdowns()
Output: (["a", "b", "c"], 3, [(0, "a", 3), (0, "b", 2), (1, "c", 2), (1, "a", 2), (1, "b", 1), (2, "c", 1), (2, "a", 1)])

Input:  deadlock()
Output: "RuntimeError"

Constraints

  • Up to 6,000 tasks and 50,000 steps per test.
  • Do not use asyncio: this loop is the event loop.

Goals

  • See what an event loop does by writing one: step coroutines with `send` and act on what they yield
  • Keep a ready queue and a clock-ordered queue of sleepers, with first-in first-out order for ties
  • Pass results and exceptions between tasks with `send` and `throw`
Starting Python…