Support 1:1 Scheduling

[alexcrichton]

Rust currently supports M:N scheduling through the runtime's Scheduler type. The standard library should also support 1:1 scheduling. This is obviously a lofty goal, and not quite as easy as just changing a few lines of code here and there.

In my opinion, this ticket can be closed when this code runs:

use std::comm::stream;

#[start]
fn main(_: int, _: **u8) -> int {
  let (port1, chan1) = stream();
  let (port2, chan2) = stream();
  do spawn {
    println!("{}", port1.recv());
    chan2.send(0);
  }
  chan1.send(2);
  port2.recv()
}

The main point of this code is that we have lots of basic runtime services working without "booting the runtime."

I believe that the best way to achieve this goal is to sort out what exactly needs to be changed and start moving everything in the right direction. At its core, a 1:1 scheduling mode means that there is no Scheduler interface. Once we remove this, there are a few implications for runtime:

• All libuv-based I/O does not work
• No comm can be used without the scheduler
• Task spawning is very closely tied to the scheduler

For each of these items, however, there are clear correspondences in a 1:1 world:

• Thread-blocking I/O (just use the normal posix apis)
• communication pthreads cvar/mutex for blocking
• Task spawning corresponds to thread spawning

In addition to having differences, I believe that the to scheduling modes share a core idea which is that of a local Task. This task encapsulates information such as garbage collection, its name, stdio/logger handles, etc.

Here are my personal thoughts about going about doing this.

I/O

This story is actually pretty much set as-is. You can use println! without booting the runtime today, and everything works just fine. The reason for this is that I/O is multiplexed over libuv/native implementation via the EventLoop and IoFactory traits. The major workhorse is the IoFactory trait, but the idea is that by default all rust code uses the "native I/O" factory which issues thread-blocking posix-like calls by default.

I believe that this component of 1:1 scheduling can be considered done. The reason for this is that the std::io primitives all "just work" in both a libuv-backed and native-backed environment (assuming they both have filled-out implementations). I'm sure that there are remaining rough edges around the IoFactory and such, but the ideas are all there and running today.

Communication

Currently all of the std::comm primitives, implemented in std::rt::comm, are very tightly integrated to the Scheduler. This does not allow them to be used at all when the runtime is not present.

Most of their implementation would be the same between a 1:1 and M:N model, except for the two concepts of "I would like to block" and "wake up this task". One could imagine code along the lines of:

if have_local_scheduler() {
  scheduler.block_on(&mutex);
} else {
  cond_wait(&my_cond, &mutex);
}

This would work, but I believe that there is a better solution. In the solution for I/O, there is one "central dispatch" point which has the "if local_scheduler" check, and I like how that has turned out, so it seems like something could also be used for communication primitives.

I believe that the only way to do this today would be to use trait objects. The Chan and Port types would have an underlying ~RtioChan and ~RtioPort object (stealing names from I/O). There are two downsides to this approach:

1. This forces an allocation. I don't think that this is really that much of a problem b/c you're already allocating other things for the channel/port, I don't think that they're ever going to be 0-allocations except for this trait object boundary.
2. This forces virtual dispatch. I'm comfortable saying that this is perfectly reasonable for I/O because I/O is the bottleneck, not a jmp to a register. For communication primitives, however, this may not be the case. My gut tells me that one virtual jmp is nothing compared to the number of atomic instructions which need to happen, but I do not have numbers to back up that claim.

Regardless, let's say that we're not going to litter all methods with if in_scheduler() { ... }. There is then the question of where does this decision go? For I/O, this is currently solved at Scheduler-creation time. The I/O implementation is selected by a factory located in the crate map. This may also be a good place for a CommunicationFactory and it's related set of functions? I would be wary of putting too many "factories" all over the place, however. To me, though, this seems to be a sufficiently configurable location for where to place the channel/port factory type.

Tasks

Task spawning is a similar problem to the communication types. There is currently a nice interface defined by the std::task module for spawning new tasks. I'm not intimately familiar with the interface, but I believe that it's mostly building up configuration, then hitting the go button. This means that the abstraction's api is basically firing off some configuration along with a proc and letting it run.

This sounds to me a lot like another factory, and a lot like another slot in the crate map. I don't want to go too overboard with these factories, though. I believe that the scheduler is also very tightly coupled to the "task factory" because 1:1 would just call Thread::start while M:N would have to start dealing with the local scheduler. I'll talk a little more about booting the runtime later, but I want to control the explosion of "trait factories" that we have if we decide to pursue this change.

A local task

I believe that it's necessary to always in all rust code have the concept of a local task. This task contains common functionality to all scheduling systems which allows many other components of libstd to work. This includes things like std::local_data, efficient println, pretty failure, etc.

I think that this task will also always be stored in OS-level TLS, so I don't think that there's much to worry about here. This would just require a refactoring of the current Task type stored in TLS (perhaps).

Intermingling M:N and 1:1

I can imagine intermingling these two scheduling modes could become very interesting. For example, let's say that I create a (port, chan) pair. If the runtime were super smart, it would not block the thread when the port called recv() in an M:N situation, but it would block the thread in a 1:1 situation. Basically communication across boundaries would "do the right thing".

I don't like the sound of that, and I think it may be just too much of a burden to maintain. I think that the idea of a thread pool is still a useful thing to have, but perhaps you should be forced to resort to custom communication between yourself and the thread pool. I could be wrong about the utility of this mode, however, and we may want to design around it as well.

Booting the runtime

In 1:1 situations, there's no need to boot the runtime. Everything is always available to you at all times. In an M:N situation, however, we must boot the runtime because the threadpool has to be started at some point. I'm willing to chalk this up to "well, that's M:N for you" in the sense that we don't need to specially accommodate use cases beyond a nice mton::boot function (or something like that)

Conclusion

There's still not a whole lot that's concrete in this proposal, and that's partly intentional. I want to discuss this strategy and how things are working out, and then the concrete proposal can come next. I hope to have enough actionable content here to move forward to a proposal after some discussion, however.

[Aatch]

I like this proposal. My personal opinion was around the fact that many things were very tightly coupled to the scheduler/scheduler implementation, requiring anybody not using the standard runtime to re-implement all the io code.

This should also leave room for stuff like de-virtualising the factory calls in the case of LTO (when we eventually get it), which is good for high-performance, constrained environments like game development.

[thestinger]

Detached threads are not the normal pattern with OS threads and will make valgrind and helgrind unclean. If you use them, you have to put pthread_exit(NULL) at the bottom of main and the exit code will always be 0 if an exit function is not called directly. I'm convinced the best way to handle OS threads in Rust is to use RAII-based objects with pthread_join in the destructor and optionally a way to retrieve the thread's exit value.

Good library support for 1:1 threading includes fast and easy to use static thread-local data as offered by C11, C++11 and D. This just isn't going to work with the current task-local data scheme. Memory-mapped I/O is also going to have to be avoided, despite it being the ideal way to do it in the 64-bit future.

@Aatch: devirtualization won't really happen with or without LTO, LLVM isn't able to do it in most cases (it's likely not very important for this though)

[alexcrichton]

@olsonjeffery has pointed on on IRC that one way to avoid the trait/factory explosion is to have one true "Runtime" trait. This trait would encapsulate all of the functionality of running in various modes.

I like the idea of such a trait, but it's tough to critique without knowing exactly what it would look like.

[olsonjeffery]

tl;dr -- I want to agree with everyone! Your combined intelligence (and assumption of good faith) dwarfs my own. I think we can have 1:1 and M:N scheduling (or would like to pursue it as a noble goal, albeit possibly a-bridge-too-far) under one roof. I think we should try to get there with one abstraction and not via stdlib forks (at this time I will invoke the ghost Tango/Phobos, as others have in numerous venues, myself included).

Kinda/sorta copy/pasted from some comments I made on this reddit post:

I personally have never liked the magical/global nature of everything being in a task. I would be really interested in pursuing the idea of a Runtime as an RAII resource (this didn't really snap into focus until I read the above comment from @thestinger ) that just flat does not exist when we enter main(), but it might be a bit too freaky for some people.

It would, amongst other things, require a heavy audit/refactor of libstd code for all stuff that relies on the Runtime in-the-large (something @alexcrichton alludes to in a comment on the above-linked issue).

and FWIW: I'm talking about pushing lots of stuff that exists as langitems or similar (malloc, TLS, failure/unwinding, etc) into this Runtime trait so that we would be basically providing a swappable impl for any given platform scenario (embedded, async server, desktop app atop NSS, etc). I made a pitch for something like this, in the past, to @brson and I believe his response was that it was too drastic and not really neccesary (not trying to put words in his mouth, so I apologize if this characterization isn't correct). This idea undermines a lot of assumptions and decisions that were made a long time ago (and would appear to be out-of-reach for 1.0, lacking some serious all-hands-on-deck work).

Likely, immediate critiques that I'd like to hear people arguing both sides of:

• such a Runtime would be so broad, not taking into account the drastically different semantics different platform-scenarios present, as to be functionally useless or lopsided towards only a few specific scenarios. This is, from my reading, one of @thestinger 's beefs with the newsched IO traits.
• mumble mumble traits! virtual calls! (also: LTO? THERE IS NO LTO!!!)

[olsonjeffery]

It is also possible that my above-outlined proposal occupies some perilous position at the intersection of naivety and misinformation. By my own admission, almost all of my experience with rust is confined to the runtime as it pertains to IO. So if I'm out of my depth or just suggesting time-cube levels of rubbish, do let me know.

@alexcrichton is kind enough to humor me, though, so I persist.

[thestinger]

I happen to like this dead simple API a lot:

https://github.com/thestinger/rust-core/blob/master/test/thread.rs

For example, with a thread-pool:

let mut pool = Pool(os::cpu_count());
let a = pool.spawn(foo);
let b = pool.spawn(bar);
let result = (a.join(), b.join());

It's necessary to do 1:1 threads this way if you want helgrind to be happy and don't want to be storing them and managing them somewhere globally.

[olsonjeffery]

Some discussion in #rust-internals, between @thestinger and myself, here: https://botbot.me/mozilla/rust-internals/msg/7869942/

[alexcrichton]

Migrating this to a metabug to track 1:1 related issues.

[alexcrichton]

In my opinion, there are two core issues which need to be resolved to make progress on this issue, those are 10647 and 10459 (linked above). Once we have those out of the way, I believe that we're basically "all the way there" in terms of 1:1 scheduling. There will be lots of sharp edges to buff out, but those two issues are the core infrastructure for progressing forward. What they mean is that spawning/communication will work anywhere and everywhere, and there will always be a local task to rely on squirreling data into.

We may well turn up something else that I'm missing along the way, but those two issues are certainly a fantastic place to start progressing this issue forward.

My general idea of a "runtime trait" or having some sort of storage in the crate map I think is overthinking things too much. Right now I believe that in_green_task_context() is a good enough "off the runtime"/"on the runtime" check. We can abstract this even further later, but I don't think that we'll need to mature it much farther than the if statement.

[thestinger]

How will a mutex supporting both 1:1 and M:N scheduling work?

[alexcrichton]

There's not really an equivalent concept of a mutex in M:N threading right now, there are mutexes built on channels in extra, but in general we're trying to discourage sharing data among tasks. We could in theory write a non-blocking mutex for M:N threading, but I would prefer exploring synchronization solely through channels before we resort to other synchronization primitives.

[thestinger]

So we aren't going to have fast concurrent data structures (hash maps, chunked vectors, etc.)?

[alexcrichton]

I'd rather continue this conversation elsewhere as I think that it's straying off-topic from this bug. I did not say that we will not have concurrent data structures. Choosing to support 1:1 and M:N does not mean that "nothing will ever be fast" because both methods need to be supported. I'm rewriting channels right now to seamlessly support 1:1 and M:N at runtime, and we're already 30% faster than go with little-to-no optimizations.

Choosing whether to implement something for M:N and 1:1 may make an implementation more difficult, but it is not guaranteed to make an implementation much slower. Each implementation needs to be evaluated on a case-by-case basis to determine how to optimize for both use cases. We cannot seamlessly port external concurrent libraries to rust because we have different design constraints as well as an emphasis on safety.