Preamble: Philosophising about futures

Rust has added a pattern for concurrent programming using futures. But Rust being Rust it has not added a one-size-may-fit-you runtime to implement the actual concurrency behind these patterns; instead it allows programmers to choose their own runtime or even write one themselves. Doing the latter is my kind of fun so I've done just that. People seemed interested in the topic so if you want a random girl on the internet to tell you how to build your own in way too many posts with way too many words, strap in.

Preamble prefix

This is not an introduction into Futures or how to use them, far from it. In fact I assume a reasonable knowledge about how to use futures and a number of their pitfalls. Smarter people than me have spent more time explaining futures much better than I ever could, go look for their blogs and posts.

Futures as implemented in Rust

In a small number of big words: "futures are a pattern of cooperative scheduled concurrent programming using delayed execution and continuations".

Looking at that in a larger number of smaller words; cooperative scheduled means that, unlike preemptive scheduling, threads of execution give up control voluntarily.

Giving away control like that is usually referred to as "yielding" and the points where a thread (of execution) does so are called "yield point". In async blocks these yield points are marked with .await. In direct implementations of trait Future a yield point is returning from the poll method.

Delayed execution means exactly that; code defined now is run later. Chances are that you are rather well versed with that part, since closures are also a way to define code now that is run later. In fact futures and closures have a number of things in common, especially if we talk about futures defined using async blocks:

rustc is fancy: closures and async blocks

Closures are said to "capture" their environment. That's a fancy way of saying that the compiler will make sure that a closure has access to whatever variables it uses until it is executed, since Rust does try to be safe. To do this the compiler will generate a structure containing all the variables used, potentially taking ownership of them. If you are "moving" a closure you are in reality moving this structure around while the code part of the closure gets compiled to the same space as all the other code. async blocks behave very similarly as in they also result in a compiler-generated structure that happens to implement trait Future.

So, how do they work?

Futures are in a first approximation functions that can return mid-way through and be resumed later, picking up from the point where they returned last instead of starting again from the beginning. Of course to be able to do that they have to somehow store state; specifically the state of where they stopped the last time and the values of all local variables.

This makes them a state machine, being more precise; a finite state machines with one state per yield point. Since a future can only return in a resumable way from a yield point a future is never between those states when it has yielded. When executing, a future then evaluates up to a yield point, advances its internal state, and then checks if it should or has to yield. If yes it does so, if not the cycle repeats.

This is also the base principle of how fn poll from the Future trait works. Each call to poll is an execution. Returning Poll::Pending is yielding control on a yield point. Returning Poll::Ready is also a yield but additionally returning a value and indicating that the future is in a final state and can not advance further.

In fact this compiler-generated structure that an async block gets converted to can be reasonably approximated. An async block (capturing a bool y and a &str z) with code like this:

async {
    let x = 0;

    let f = SomeFuture::new(z);
    f.await;

    if y {
        x += 1;
    }

    let g = SomeOtherFuture::new(x);
    y = g.await;

    return y;
}

Will be turned into something similar to this:

enum SomeAsyncBlockFuture<'a> {
    UpToFirstAwait {
        x: u64, y: bool, z: &'a str, f: SomeFuture,
    },
    UpToSecondAwait {
        x: u64, y: bool, g: SomeOtherFuture,
    },
    AfterSecondAwait {
        y: bool,
    }
}

This structure would then implement the Future trait, behaving like the state machine described above. Also, note the lifetime in the enum's definition; async blocks like closures take values by reference a lot of the time. By itself that is not a problem, but spawning a future nearly always transfers ownership to the executor. This means they are (potentially) alive pretty much "forever". Knowing that explains why async blocks need to be made to move captured variables much more often than closures do.

The reality is of course always a touch more complicated and variables are usually stored depending on their scope and not where they are used, but still, this is an acceptable model. It also gives us an important information about the cost of async blocks; enums are always the size of their largest member. And all in-between futures do have to be stored. Imagine for example that when the variable f, a SomeFuture, is awaited it does not return a Ready; in that situation the outer future made from the async block would yield itself to wait on f being ready. And when it is resumed not only does f have to exist, it itself has to be in the exact same state as when it yielded last time.

Tasks, fibers, greens (threads) and I promise this section isn't about healthy eating!

So the compiler did its magic and now we have a future on our hands. And now? A future by itself isn't useful, we have to poll it, at some point. But to call Future::poll we have to have pass in a Context, a type we never talked about yet. And that one isn't even in the future module, it's in the task module.

What's a task now?!

Async rust doesn't actually operate in the unit of Futures. Instead it operates in the units of "tasks". Other languages call a similar concept a "fiber", a "goroutine", a "green thread" or, in the case of Erlang, a "process". Now, all of these are slightly different from tasks in Rust, and we may talk about the differences between async runtimes in different languages in a much later post. But for now; a task is our unit of async computation.

A task is a context of evaluation inside your async runtime and a (or, several) future(s) — each of which may of course in reality be an amalgamation of awaited futures in an async block or strung together using combinators such as then (which however just makes them one, significantly more complex, future).

But a task also has this aforementioned Context; a type that has little more than the rather obscure documentation sentence Currently, Context only serves to provide access to a &Waker which can be used to wake the current task. This documentation doesn't tell us much at all. Taking it and the API of Context and Waker apart, we can at least guess two things: For one that each Task has their own Context since it is passed to Future::poll by mutable borrow. Secondly — since Waker doesn't let us select a task to wake up — each task also has to have their own Waker.

What those types actually do and how we create them is best explained using examples, and will happen in the next post. This one is long and dense enough already. Take a break. Have a tea. Go on a short walk. This post isn't going to go away anytime soon.