Runtime-agnostic cooperative task scheduling budget

libs
1

(NOT A CONTRIBUTION)

tokio has a concept of a cooperative task scheduling budget, by which its futures keep track of how much work they've done, and cooperatively yield if they've done too much work. This way, a single task which has a lot of work to do can't hog the thread, blocking other tasks from also completing work. This improves tail latencies. Read more here: Reducing tail latencies with automatic cooperative task yielding | Tokio - An asynchronous Rust runtime

It would be interesting if Rust's task system could support this natively, so different libraries could use the same cooperative scheduling system without depending on a specific third party runtime that sets a thread local. To do this, the budget would need to be communicated via the task Context.

The tokio system only has two APIs that are used by the various synchronization and IO primitives:

  1. poll_proceeding, which attempts to consume some budget and returns Pending if we're out of budget, or an object called RestoreOnPending if we aren't not.
  2. RestoreOnPending::made_progress which indicates that this task has made progress.

(Note: the importance of tracking if we've made progress is that RestoreOnPending gives budget back if this future didn't make progress, so that tasks that are not actually making progress don't run out of budget while trying to complete.)

There are other APIs in tokio relating to budget, but they are all essentially internal to tokio's executor. To write a new concurrency or IO primitive, these are the only two you need.

I'm imagining a new submodule of task, called coop. In the coop module, there is a type called Cooperation, which represents an attempt to cooperatively share the task budget. This type is similar to Waker - it has a word size data component and vtable. The vtable for now would have only two methods: make_progress, to indicate that this future has made progress, and drop, for when it drops. In the future, this vtable could gain other optional methods. There would also be a default constructor for Cooperation, which does nothing. Cooperation does not implement Send or Sync.

mod coop {
    pub struct Cooperation {
        data: *mut (),
        vtable: &'static CooperationVTable,
    }
    
    impl Cooperation {
        // a cooperation in an executor with no budget constraints
        pub fn unconstrained() -> Cooperation { ... }

        pub fn made_progress(&mut self) { ... }
    }

    impl Drop for Cooperation {
        fn drop(&mut self) { ... }
    }

    impl !Send for Cooperation { }
    impl !Sync for Cooperation { }

    pub struct CooperationVTable {
        made_progress: fn(*mut ()),
        drop: fn(*mut ()),
    }

    // plus a bunch of constructors similar to Waker's
}

Context would gain a constructor that also takes a virtual function that constructs the Cooperation. Because Context is not Send or Sync, you can be sure that this function will only be called on the same thread (so e.g. it could access a thread local). This function would return a Poll<Cooperation>. Context would gain a method which calls this if it is set, and returns the null cooperation if it is not (indicating a runtime that doesn't have a notion of task scheduling budgets):

impl Context<'_> {
    pub fn poll_cooperate(&mut self) -> Poll<Cooperation> { ... }
}

// hypothetical API also used in LocalWaker proposals
impl ContextBuilder {
    fn set_poll_cooperate(
        &mut self,
        poll_cooperate: fn() -> Poll<Cooperation>,
    ) { ... }
}

Objects that want to participate in a cooperative yielding system like tokios would, when they are polled, first call ready!(cx.poll_cooperate()) to get a Cooperation. When the poll method makes progress, they would note made_progress on the Cooperation, and when it returns they would drop the Cooperation.

Thoughts appreciated.

8 Likes
2

I like the concept of standardizing a mechanism like this.

This seems, ideally, like something that should use the "capabilities" mechanism once we have it, so that if using a runtime without this mechanism all the calls compile to nothing, and if using a runtime with this mechanism all the calls directly call into the runtime without indirection. I'd love to make sure that we have a path to that in the future without having to use function pointers unconditionally. (It'd be acceptable, if not ideal, if old code using a new executor had an indirection, as long as new code could avoid it.)

What's the rationale for returning a Poll<Cooperation> rather than a Cooperation? Under what circumstances would a runtime need to yield at that point?

Also, it would be nice if we could define "progress" more precisely so that people have a better idea of when to call made_progress. Even better if we can put that into some standard interfaces so that most futures rarely need to do so manually.

3

(NOT A CONTRIBUTION)

I don't think the capabilities proposal has much bearing here.

The choice is simply: either monomorphize this somehow or make it a virtual call. To monomorphize it you could add some new means of abstraction or you could add a defaulted type parameter to Future and Context. But I think you shouldn't monomorphize it anyway, for the same reason Waker is not a monomorphized type. Build times are already terrible for async code, maybe you want the ability to specify the functionality at runtime, not compile time, the Future interface is gnarly enough, and frankly there just isn't any good motivation for it. Remember that all the code that would be rewritten is already using a virtual call to get the "cooperation," because they're all using thread locals.

In the case where the code is running on an executor which doesn't have a notion of a cooperative scheduling budget, this can be written so that instead of a virtual jump there's just a null check (it just depends on how the Cooperation type and its Cooperation::unconstrained constructor are defined). Remember that right now, the primitives using this system (i.e. all of tokio's) would panic in that case. If you don't want this feature in your code at all, so that even a null check is prohibitive for you, you should use primitives which ignore this feature.

That's how futures cooperatively stop running - the context returns Pending when the task has run out of budget.

I've intentionally avoided overspecifying things so that different executors can work differently (for example, tokio has a budget of 128 polls which make progress, but there's no counter specified anywhere in this proposal).

Only manually implemented IO and synchronization primitives need to worry about this, anything composed out of those will naturally "make progress" as they perform IO or get notified about synchronization events.

2 Likes
4

For what it's worth, I think it's a great idea to standardize this mechanism, and it's something I intended as a long-term goal since the very first iteration of the PR. Thanks for picking that up!

One thing I want to highlight around the concept of "progress" is this warning from the original PR. It's important that made_progress is actually called only when progress has truly been made, as calling it incorrectly will cause programs to essentially hang forever. And placing them in the "right" way is tricky. Which I suspect is part of the reason so much of tokio's coop API is still private (and even consume_budget is unstable. I don't have a great definition for what progress means, but the informal definition I've used myself is "the future did some work that it won't need to do again next time". So, for example, if a future polls another future, that's not progress in and of itself. If that other future finished though, it could be. Doing a read from a socket is only progress if the socket yielded non-zero bytes or if the socket reached EOF (or erred).

The other bit from coop that I think is worth highlighting (but that may not need to be standardized) is the need for a way to opt out of cooperative scheduling. It turns out that for some workloads, the cooperative aspect is just too cumbersome (often due to factors outside of the developer's control). The original ticket requesting the feature has a bunch more details for anyone who's curious.

3 Likes
5

(NOT A CONTRIBUTION)

Thinking of futures as state machines makes it clearer I think: any time a future transitions state, it can record that it has made progress (it can also choose not to do so, this is after all an entirely optional feature). A future polling a sub future is not transitioning state (except insofar as that sub future changes state, which then makes it that sub future's responsibility to record).

Yea, the way to do this with this API would be to define a new Context which changes poll_cooperate back to the no-cooperation default, so any futures called with that context will be treated as if they're running on an executor which doesn't have this feature. A future combinator could be written that does this. It all falls out naturally.

3 Likes
6

If you have a monomorphic interface, you can always use a dyn to choose at runtime. And one of the notable ongoing discussion points about capabilities is whether that should be the default for reasons of build time.

But I would like to have the option of being fully monomorphic.

I would expect capabilities to be simpler than raw vtables...

I'm talking about monomorphizing that call, too. Capabilities could allow for that. I agree that if we don't then we get less value out of monomorphization.

1 Like
7

(NOT A CONTRIBUTION)

I just want to walk through what you're talking about. This is my reference point for the hypothetical feature you're discussing: Contexts and capabilities in Rust - Tyler Mandry

First, let me reiterate our goals here. I'm going to refer to IO, timers, and synchronization primitives as "reactor primitives," and the task executor as the "executor":

  1. People should be able to write new reactor primitives that participate in an executor's cooperation system without depending on custom APIs of that executor.
  2. Reactor primitives which use the cooperation APIs should be able to run on any executor (whether that executor actually uses it or not).

All of tokio's reactor primitives currently depend on tokio's internal "coop" API. I've proposed an API which they could be ported to. Let's see how capabilities would actually change this.

First, all of tokio's primitives would have a with clause on all of their poll methods, for example (using the oneshot receiver as one of the simplest examples):

use std::task::coop::CooperationProvider;

impl<T> Future for oneshot::Receiver<T>
    with coop: CooperationProvider
{
    ...
}

Note that we need to call poll_cooperate in every poll method, so it's not enough to just have with coop: Cooperation, we need something which provides the constructor as well, to check if the budget is done.

This has not improved anything at all. Everything is still dynamic, because you need an implementation to provide the specific methods and there's no where to introduce the new type parameter.

So let's add a type parameter to allow that:

use std::task::coop::ProvideCooperation;

impl<T, C: ProvideCooperation> Future<C> for Receiver<T>
     with coop: C
{
    ...
}

Okay, now what does using that look like?

You don't get the benefit of not specifying the with clause that Tyler Mandry cites in that blog post, because any time you use a reactor primitive in your code, you have the concrete type. Therefore, you would need to write your functions like this:

async handle_message(rx: Receiver<MyMessage>)
    with coop: impl ProvideCooperation // without this, can't await rx!
{
    match rx.await {
        ...
    }
}

Every async function would be infected with this.

This is strictly worse than just using it via the context argument, because the context argument can hide everything from async functions. Capabilities provide absolutely nothing here.

The future API and the task API are not the same. I'm talking about adding new type parameters to Future. People writing futures do not need to construct Cooperations. But the raw vtable is just to support representation optimizations in the Cooperation type, there could also just be a Cooperate trait and a constructor from Box<dyn Cooperate>, analogous to the Wake trait that exists for `Waker.

8

That's one of the posts talking about the idea of a capability system, but that post was a year and a half ago, and there's been a fair bit of additional discussion since then. Among other things, we've been talking about ways to avoid the need to specify with, in part because it introduces so much additional verbosity across the whole program. (Your post provides a good example of that.) Some of those approaches would look more like a named/scoped global that's an instance of the trait (similar to a generic version of GlobalAlloc).

The implementation would get provided either by a global "provide" ("here's the default instance for my whole program") or a scoped one ("call this function with a non-default instance"). (Note that the design for the scoped approach is still more larval-stage at this point, but neither have these have made it out of discussion into a pre-RFC quite yet. That needs fixing; please pardon the current handwaving.)

I wasn't proposing doing that; I agree that we shouldn't complicate Future any more than it already is.

9

(NOT A CONTRIBUTION)

II can't really analyze the impact of a feature idea that isn't documented anywhere. I am more sympathetic to the idea of letting users define items that behave like global_allocator than I am to the idea of these with clauses. However, I'm also skeptical that you can have implicit scoped replacements for globals without virtual calls. On the other hand, the Context type already exists.

On that note: I'm posting this because it's a real problem affecting me as a production user. My collaborators and I would like to experiment with runtimes other than tokio in some of our systems, but have a lot of shared libraries that currently use tokio reactor primitives, which only run on tokio's runtime. This is a common problem and I know it's one the project cares a lot about.

Investigations showed that it would be pretty manageable to abstract these libraries over IO types (using either tokio or futures' async IO traits) and timers (usually just taking a sleep or interval future as arguments). In fact, we often already do to mock these things in testing. But the real problem is the synchronization primitives. Internally, these libraries use channels and locks to handle complex multiplexing scenarios, and abstracting over everything was not seen as realistic (especially without async traits, though obviously that's coming in the near term).

Tokio's concurrency and synchronization primitives except for Watch and select (which both depend on an RNG in a thread local) all only depend on tokio's runtime to access this feature. Our only choice if we want our libraries to run on other runtimes is to give up this feature of tokio by using primitives that don't do that (such as those from smol). This would mean that when we are running on tokio, we lose the benefit of this feature. If tokio's concurrency primitives instead used a standard interface, they would be compatible with other runtimes, we could use them and keep this feature, while also running on other runtimes.

Similarly, if we want to write our own concurrency primitives that fit a specific pattern (which sometimes we do want to do), currently they can't participate in tokio's cooperation system because it isn't publicly exposed.

To summarize my point: making IO reactors and timers compatible across runtimes is a hard problem, and one I don't think will be solved soon. But that's not actually the problem for writing runtime-agnostic libraries, because IO and time is in some sense "external" to the library, whereas synchronization is not. Synchronization primitives are for the most part much easier to make runtime-agnostic, and this API is the only thing keeping tokio's from being such. Getting this into std, and then getting tokio to use it, would unlock runtime-agnostic libraries in a big way.

7 Likes
10

I don't think that's the case; fundamentally, you still have to pick an I/O trait, and furthermore if you use tokio's primitives you have to have a tokio runtime running. If a library depends on tokio, or smol, or async-std, it isn't runtime-agnostic, even if it'll run on another runtime as it would in the latter two cases.

11

(NOT A CONTRIBUTION)

The entire point of my post is that with this feature tokio's synchronization primitives don't depend on the tokio runtime.

tokio with only the sync and io-util features turned on is a library with some async IO adapters and traits and async synchronization primitives. It doesn't even have a reactor or an executor in it. It's perfectly reasonable to use as a library in this way without turning on the rt feature. Just because tokio shows up in a crate's dependency graph doesn't mean the crate is not runtime agnostic.

And of course with this feature, someone could fork the tokio sync modules, or write their own with different trade offs, but still participate in tokio's cooperation system. Or write an executor with other differences that also uses a cooperation system. Right now, this is privilege afforded only to tokio.

1 Like
12

Couple of thoughts (subjective confidence is low, this isn't my area of expertise at all):

It seems that there are two somewhat orthogonal things going one here:

  • design of specific budgeting API (eg, what's the signature&semantics of made_progress and such)
  • exposing this API via std::task::Context argument

It seems plausible that we can solve 1) separately by exposing it as a library (eg, there can be tokio-coop crate which tokio and other rutnimes can depend on, which abstracts threadlocals, maybe using extern "C" trick for link-time-binding). Without looking into details it seems surprising that we want to bring API into std which even isn't stable in tokio.

For 2), one surprising bit is that we bless Context with a specific API. It feels like maybe context wants to be somewhat more general, such that downstream libraries can inject stuff into it without coordinating with std. This feels very similar to the provider API which I think we want to use for errors?

Without considering this too carefully, at a glance it seems obvious that, if we add Provider-shaped API somewhere, then std::task::Context should be providerified as well.

Finally, wrt to monomorphisation and such, I think the desired behavior here should be the same as it is for the global allocator:

  • crates are not monomorphised and are separately compiled
  • but by the time we get to lto, we know which functions will be actually used and can inline at that stage.
6 Likes
13

(NOT A CONTRIBUTION)

There's no controversy about the design of the cooperation API. Jon Hoo was making a comment about how the API must be used correctly (a future must not record that it has made progress if a subsequent poll would find the future in the same state, or it may never complete). There's no alternative API being proposed.

Adding a fully general provider API moves in the opposite direction of runtime-agnosticism, because now reactor primitives can depend on arbitrary types being present in the Context, which different runtimes won't provide. Similarly, not stabilizing a cooperation API but just giving the ability to access any type, and having a third party library define it, would mean these libraries would not be compatible with runtimes not depending on that library.

Frankly I don't think the provider API is a particularly good idea at all for this reason: being better at this pattern than Any downcasting isn't really compelling when this pattern should be a last resort. Instead, std should identify widely used patterns (like errors carrying backtraces or this feature) and bless them with a standard API once they've proved out in the ecosystem. I don't want this feature to be used as an excuse for std not to do that.

What Josh mentions is that they want to allow scoped replacement of these values. This isn't possible without adding type parameters to the types depending on these APIs or using virtual calls, and its only possible with virtual calls when calls between them are generally fungible (for example, it would absolutely not work to have the definition of alloc and free change in between scopes).

More broadly, I find that this impulse to generalize, to block on other unstable features, to refuse a small actionable change in favor of a grand new project is one of the worst aspects of the Rust project culture and one of the ways the project fails to align with the interest of its users. If there's a tone of frustration in my comments in this thread is from being confronted with this tendency.

8 Likes
14

On the broad topic, I think there are two forces:

One is push forward to generalize things. Here I think we are in the same boat: I personally find it alarming how Rust seemingly becomes less and less complete due to scope expansion of the language. In particular, yeah, provider API feels overly general to me.

A different force is a push back against just adding stuff to the language/stdlib incrementally, without considering the big picture, and far future of Rust. Here, I am very willing to say "let's maybe keep this outside of std", as crates.io is almost always an adequate (if not perfect) way to relive the pressure.

The Context API is actually a good case study here. IIRC, originally we wanted to not have Context at all, just waker. Then we added it, but with Send + Sync bound because "single threaded executors can use array and indexes". Recently we relaxed that via a technically breaking change. What's the end story for the Context API? How do we not end up in a situation where:

  • some stuff is threaded via explicit support in Context,
  • some stuff is handled by Context provider's API or some such,
  • and tokio is still using a thread local for something else?

Maybe this particular case with cooperative scheduling is different, and there's indeed just one obvious way to do this and we should just go and implement it.

4 Likes
15

(NOT A CONTRIBUTION)

Yea, these are clearly two forces in tension in any project. But I feel very comfortable saying which of these forces the Rust project is too biased towards.

This isn't quite a correct recounting.

We got rid of LocalWaker and just went with Waker on the basis that single threaded executors can use arrays and indexes. At the time our narrative around single threaded executors was that they were strictly for embedded systems that wouldn't want to use an Rc waker anyway. Of course, the renewed interest in thread-per-core has shown this is wrong.

But this all happened before Context was added. Adding Context was fully driven by the tokio project, as future proofing to support exactly the kind API I'm proposing now. Frankly, within the async WG we didn't think it was necessary, and really forfeited this discussion in order to get buy in on shipping. So the reason Context wasn't Send + Sync was a total oversight, probably in large part because we thought it was unnecessary in the first place.

And we were totally wrong! Context, correctly defined, enables us to add these APIs to the task system to support different kinds of runtimes, both LocalWaker and this thing. Adding Context, and fixing our mistake in defining it, was the right call and now is enabling different use cases. Like I'm not that enthusiastic about thread-per-core and I think work stealing is the right default, but I think its very important that Rust support either model because Rust is supposed to give end users total control over their systems.

So I think the end story for the context API is exactly what I'm proposing here and what has been proposed with the LocalWaker extension: bringing functionality into std that's got clear motivation and API consensus from the ecosystem to support different kinds of async task systems. Ideally, we'd eventually get rid of runtimes using thread locals at all, but that's a long journey.

10 Likes
16

I would also be happy to see this being moved into the context.

In the meantime, exposing the rest of the coop API under --cfg tokio_unstable would be easy to justify. Moving it into another crate could also be a possibility, but that has the unfortunate side-effect of creating a new thread-local. Thread local variables are a very limited resource on some systems, e.g., on Android each process can have no more than 128 thread locals.

2 Likes
17

To be clear, this would allow using the coop API without any of the runtime?

One of the challenges of Rust's breadth is that it becomes very hard to know when you're privileging one class of use cases over another (and to make a value judgment on it if you are). Async is one of the features that spans many divergent domains and as a result, it's easy to get caught up in these questions, and conservatism is an easy fallback.

As an example, let's say this feature is more useful in the web services domain than the embedded one. That doesn't mean we shouldn't have it, but we should consider the tradeoffs in other domains and ideally give embedded users an easy out of "don't pay for what you don't use."

Speaking more concretely, next steps I would suggest:

  1. In the immediate term, throwing the APIs behind tokio_unstable seems like a promising idea.
  2. Any RFC for this API would ideally come with "user profiles" of people who want and who don't want this feature, and how it will affect them.
  3. (For us) In the slightly longer term, the async working group needs to start including reps from each of these user groups, including runtime maintainers, so we can discuss proposals like this on equal footing. Also, it should begin building up these user profiles in a public place so that future proposals don't have to start from scratch each time. (We've made some isolated moves in this direction, but I think we need to do better.)
3 Likes
18

Yes. A coop system needs to know when the start and end of polling a task is, so whatever runtime you're using would need to call a method defined in Tokio to use it (or in some other crate if we split the thread-local). But it doesn't otherwise require any use of Tokio's runtime.

1 Like
19

This feels to me like a domain-specific instance of a more general problem: Executors need the ability to provide custom data to futures while they're running, and the futures need to be able to reject running on executors that can't provide the data they need to run. (Maybe this is what the Provider API is all about; I haven't looked at it closely.) This specific example may have a large enough user base to be added before that general API is ready, but we should at least consider how it might interact with such a facility.

To give another example: Back when async was in beta, I tried to write a custom executor to drive the display thread of an SDL program, but I had trouble figuring out how to give the futures access to the SDL system: The executor needed access to the system when the futures were paused to do things like flip the screen buffers and set up the next frame for drawing, but the futures also needed access to it in order to actually draw things. It felt like the Context was intended for this sort of thing, based on the name and where it fit into the API, but at the time there was no way to either attach my domain-specific data to it or access it from a normal async block.

I can think of a way to modify the API to accomplish this, but I don't know if it can be done in a backwards-compatible way: Add the Context as a parameter to the Future trait instead of being a specific concrete type, possibly with a default.

trait Future<Context> {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> where Context:GetWaker<'_>;
}

trait GetWaker<'a> {
    fn waker(&self)->&'a Waker;
}

// implementation template for async blocks
impl<Ctx> Future<Ctx> for AsyncBlock42 
where for<'a> Ctx: GetWaker<'a>,
    AwaitedFuture1: Future<Ctx, Output=...>,
    AwaitedFuture2: Future<Ctx, Output=...>,
    ...
{
    ...
}

(There's probably something fundamentally wrong with this plan, as I haven't studied async in detail)

20

If this does happen, it should happen at compile time; it's very frustrating to deal with systems with arbitrary restrictions at runtime.

Is that why you added a parameter toFuture?

4 Likes