Questioning the design of the "Future" trait, and the cost implied by it

language design
13

This test is useful because it allows us to separate the allocation of the future from the running, to see which is the cost. What does the graph look like in that case?

async fn run_test(n: isize) {
    let fut = chain_many(n);
    let start = Instant::now();
    fut.await;
    println!("{}", (Instant::now() - start).as_micros());
}

And no, no work is done until .await is called. Rust futures are "lazy" in that they don't do any work until you start polling (.await) them, unlike JS's (which act like threads; start running when created, and awaiting is just waiting for it to finish).

I suspect that this is the actual cause of the discrepancy. tokio::task::yield_now().await will always jump back to the tokio event loop for a turn. You say that then causes a yield to the event loop in JS, but I don't know that for sure, and it's quite possible that the JIT sees through your shenanigans and is making (parts of) your test straightline and not yield.

Calling and immediately awaiting a no-await async function in JS is (allowed to be) implemented as straightline code that doesn't yield to the executor. My gut says the JS runtime is "cheating" in a similar way here. But even if it isn't, do note that JS executors have been heavily tuned to JS promises' semantics, and tokio is still quite young in comparison. The quadratic blowup could be a tokio issue, not a Rust issue. I'm not sure -- it sure seems like this should be linear -- but I'm more willing to blame Tokio or the allocator than that this is a fundamental limitation to Rust's Future semantics.

Actually, no, you're fully right. Because of the boxed indirection at every step, the optimizer can't strip out the calls to each subfuture's Future::poll method.

In the common case, you aren't boxing each future, so the step of recursing down the poll tree is optimized to just be a jump table. But every indirection point inhibits this.

A more fair comparison is to actually do what the JS runtime is doing (before JIT shenanigans). Instead of encapsulating another boxed future, spawn it on the executor directly -- Rust gives you the choice!

Going back to the original recursion:

async fn recurse(n: isize) -> isize {
    tokio::task::yield_now().await;
    if n > 0 {
        1 + tokio::spawn(recurse(n - 1)).await;
    } else {
         0
    }
}

It's quite unfortunate that this footgun exists, and that there's no exexutor-agnostic way of not stumbling into the footgun, but this should be linear instead of quadratic.

This is exactly due to the eager/lazy semantics. The solution is to be eager and spawn the recursion onto the executor rather than encapsulating it as a BoxFuture member.

EDIT: ew that's an ugly error as written. You should get my semantic point, though: use tokio::spawn for deeply nested boxed futures.

Execution
Close
Standard Error
   Compiling playground v0.0.1 (/playground)
warning: unused import: `BoxFuture`
 --> src/main.rs:1:23
  |
1 | use futures::future::{BoxFuture, FutureExt};
  |                       ^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

error[E0391]: cycle detected when computing type of `recurse::{opaque#0}`
 --> src/main.rs:4:31
  |
4 | async fn recurse(n: isize) -> isize {
  |                               ^^^^^
  |
note: ...which requires borrow-checking `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires processing `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires processing MIR for `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires unsafety-checking `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires building MIR for `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires type-checking `recurse`...
 --> src/main.rs:4:1
  |
4 | async fn recurse(n: isize) -> isize {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  = note: ...which requires evaluating trait selection obligation `impl futures::Future: std::marker::Send`...
  = note: ...which again requires computing type of `recurse::{opaque#0}`, completing the cycle
note: cycle used when checking item types in top-level module

Here's a version that works:

fn recurse(n: isize) -> BoxFuture<'static, isize> {
    async move {
        tokio::task::yield_now().await;
        if n > 0 {
            1 + tokio::spawn(recurse(n - 1)).await.unwrap()
        } else {
            0
        }
    }
    .boxed()
}
4 Likes