Scoped threads in the nursery (maybe with rayon?)

[stjepang]

Submitted a RFC for scoped threads in the standard library:

Add scoped threads to the standard library

[ckaran]

I appreciate the RFC that @stjepang has written, but I personally prefer rayon’s approach of task parallelism as it frees me from having to think about the number of threads I need to spin up. Getting the load balancing right can be difficult, but rayon does a pretty good job of that via work stealing. I also think that a rayon-like API would be easier to adapt to GPGPU programming, where the number of cores I can use seems to increase every 5 seconds.

[stjepang]

We can have both! I don’t think they’re competing nor even that they have many overlapping uses.

[ckaran]

Re-reading, and quoting lots of quotable people:

So perhaps another way to put it is that I view rayon-like interfaces (e.g., join, scope+spawn) are really kind of a primitive in the language in much the same way as an allocator.

IMO both problems look too much alike, and I’ve also had the need of switching a global “logger” as well (on an MPI application with 100k processes you don’t want 100k log files, but that all or some processes write to a single file), so this might be a more general pattern than just something special to allocators.

I think a much more promising approach is moving knowledge of fork-join out of a library and into the compiler itself. This is where projects like Tapir come in. Hopefully we can build on that work (or that style of work).

We can have both! I don’t think they’re competing nor even that they have many overlapping uses.

All of these posts got me thinking about the log crate, and how it explicitly states that it is a ‘lightweight logging facade’. Instead of pulling something into the standard library, can we create a facade for scoped threads, and also provide one (or more) submodules/subcrates (forgive me, I’m still learning rust’s terminology) that provide default implementations of the facade? The advantage of this is that if in the future rust starts targeting stuff like Vulkan/SPIR-V, then people can provide crates that implement the facade, and users can use it as a drop-in replacement (my assumption is that even if rust gains the ability to compile code to SPIR-V, someone will still need to write a crate that understands the Vulkan compute APIs to move the compiled code onto the GPU. Same for CUDA, OpenCL, some kind of distributed architecture across a compute farm, or even combinations of all three).

I would also like to see an architecture where we can compose different concrete implementations together to handle bigger problems. For example, rust could have the equivalent of python’s SCOOP at a high level, then on each machine there may be scheduler that understands how to feed jobs to the CPU & GPU (or GPUs), and even lower-level schedulers for each CPU or GPU core.

OK, I’ve come up with the big idea, now someone go make it happen! (please take that as a tongue-in-cheek joke, and not as an insult…)

[stjepang]

I’m a contributor to Crossbeam, Tokio, and Rayon and am currently researching how to make all those concurrent programming models work together really well. This is a very interesting topic and will only become increasingly important in the near future. We should indeed explore it into more depth.

However, I still believe the reasoning behind the original post in this thread is flawed. While it would be amazing to have a unified concurrency model that abstract Crossbeam/Tokio/Rayon away as a purely low-level detail for parallel/asynchronous tasks, I think it’s a pipe dream and will never happen.

More specifically, this is what I disagree with: “Rayon-like interfaces are a primitive in the language in much the same way as an allocator”. I wish that was true, but strongly doubt it. Those Rayon-like interfaces are alike only in the sense that they vaguely resemble each other, but are fundamentally different at their core:

• Crossbeam works with native OS threads that may be non-cooperatively preempted at any time. Blocking is okay as long as we use thread::park(), Condvars, or similar primitives.

• Rayon works with tasks that are cooperatively preempted in rayon::join() and at the end of rayon::scope(). Note that tasks technically have a stack, but preemption puts one tasks’s stack on top of another. Blocking in tasks is forbidden.

• Tokio (Futures) works with tasks that are cooperatively preempted in await. They are truly stackless and in order to preempt a task we have to fully “undo” its whole stack and return Poll::Pending from it. Blocking is forbidden (although tokio::blocking() can be used when blocking is absolutely necessary), but await can be used to simulate it.

There is one more concurrency model:

• Stackful coroutines like in the may crate. They work with userspace threads that are cooperatively preempted. Blocking is forbidden unless custom APIs are used. Each spawned task gets its full dedicated stack and it’s possible to preempt at any time.

Those models cannot be unified because they all have completely incompatible rules around preemption, stacks, and blocking.

However, not all is lost. Instead of trying to find a common interface for them, I think we should pursue a slightly different goal: try to find primitives that will make them all work together.

For example, how does one spawn a CPU-intensive task from Tokio onto Rayon and await it? We don’t have good answers for basic questions like that but we should! In my opinion, this is the real problem we should be solving, not building a common facade.

[ckaran]

@stjepang Do you have any suggestions for what kinds of primitives would work well together?

[notriddle]

Grand Central Dispatch?

[ckaran]

@notriddle Do you have much experience with GCD? If you do, do you know if it is amenable to throwing tasks on the GPU, or having extensions that can do that?

I know I’m a broken record here, but I want to make sure that whatever is developed can easily be extended to non-traditional assets (e.g., GPUs, or clusters of machines). I do not expect that we’d support such platforms out of the box, or even if they would ever be supported directly, but having the option would be nice. Maybe a facade for GCD, with libdispatch being shipped with rust? Or would it be better to develop something new from scratch?

[stjepang]

I expect there will be three kinds of tasks programs will run:

• IO tasks driven by the futures executor.
• CPU-intensive tasks driven by Rayon.
• Blocking tasks (e.g. reading from stdin) driven by dedicated threads.

We will need a way of communicating between those three kinds of tasks. For example, an IO task might want to kick off a long computation onto Rayon and Rayon will need to notify the IO task when completed. There might even be a fourth kind for tasks on the GPU, I don’t know.

It’s worth looking into C#'s TaskScheduler class, which is like a hybrid of Tokio and Rayon. I suspect C# will be a huge source of inspiration for us (and it already is through async/await!). Structured concurrency is another keyword to keep in mind.

Anyways, I don’t have much to offer at this point. Will think about all this, experiment a little, try to prototype something, and share ideas - probably through blog posts. Stay tuned

[notriddle]

I know I’m a broken record here, but I want to make sure that whatever is developed can easily be extended to non-traditional assets (e.g., GPUs, or clusters of machines)

GPGPU (General-Purpose computation on a Graphics Processor Unit) and SMP (Symmetrical Multi-Processor, like your “four core server CPU”) are fundamentally different concurrency models. A GPU is basically a bunch of ALU’s all connected to the same CPU core, so that you can perform the same operation on millions of pixels simultaneously. It’s Single-Instruction-Multiple-Dispatch. This is awesome for some use cases, but it’s different from a multi-core application CPU, which runs completely different processes at the same time. That is, an SMP system is Multiple-Instruction-Multiple-Dispatch.

While I don’t have much experience with GCD, since I develop mostly on Linux and Windows, I can read its documentation enough to notice that it’s all built around queuing up closures to run (like Travis CI, but at the level of a single machine instead of a cluster). That’s doesn’t sound like a GPU-friendly way to do concurrency (a GPU-friendly model would be something like a “parallel for”), and the docs don’t mention support for GPU’s, so I assume the answer is “no”.

I also don’t see any problem with standard library providing a thread pool abstraction that only works on the CPU. OpenCL is nice, and I have no actual objection to bundling something like it in std, but OpenCL imposes a lot of restrictions on the application in order to achieve portability.

I would like to have std provide a thread pool library that only works on the CPU, and by placing this restriction, the thread pool library can be flexible enough that tokio, rayon, and crossbeam can all use it. Anything OpenCL-esque can then be layered on top of that, splitting work between the CPU (as provided by the GCD-esque thread pool library) and the GPU (as provided by whatever GPU-specific abstraction we’re using).

[ckaran]

GPGPU (General-Purpose computation on a Graphics Processor Unit) and SMP (Symmetrical Multi-Processor, like your “four core server CPU”) are fundamentally different concurrency models. A GPU is basically a bunch of ALU’s all connected to the same CPU core, so that you can perform the same operation on millions of pixels simultaneously. It’s Single-Instruction-Multiple-Dispatch. This is awesome for some use cases, but it’s different from a multi-core application CPU, which runs completely different processes at the same time. That is, an SMP system is Multiple-Instruction-Multiple-Dispatch.

Absolutely true, which is why I hated trying to figure out how to use it; I kept making mistakes in how I’d order things, resulting in sequential operations, instead of parallel operations. That was part of why I quoted @nikomatsakis comment about tapir; my suspicion is that rust is sufficiently strongly typed that it can extract the available parallelism on its own, figuring out how to deal with the differences between GPU architectures and CPU architectures. However, just having rustc --target=spirv isn’t sufficient; an end user needs to be able to say ‘this chunk of code should be parallelized because it will never block on io’, and ‘this chunk of code is listening to the game controller, and will be blocked for long periods’. This is where the crate’s design becomes important, and why we I think we should design a facade that permits these different use cases (more below).

I would like to have std provide a thread pool library that only works on the CPU, and by placing this restriction, the thread pool library can be flexible enough that tokio , rayon , and crossbeam can all use it. Anything OpenCL-esque can then be layered on top of that, splitting work between the CPU (as provided by the GCD-esque thread pool library) and the GPU (as provided by whatever GPU-specific abstraction we’re using).

I understand where you’re coming from with this, but my hope is that we’ll be able to figure out something that would allow rust to expand outwards as needed. That was part of my interest in creating a facade, and an implementation of the facade in the standard library. If in the future someone figures out how to compile rust -> GPU (OpenCL, SPIR-V, magical pink unicorns, etc.), it would be nice if they could also implement the facade for what they’ve done, making it easy for everyone else to use their work. When I see rayon’s par_iter(), I see someone creating their own version of parallel for, and shoving work towards a GPU. I can also see a tree of concrete implementations, where higher nodes in the tree are shoveling work around to lower nodes (cluster -> computers -> CPU/GPU). I just want a facade that is open to all of this.

[FenrirWolf]

All I want today is a thread::spawn() variant that doesn’t require F: 'static .

There is an unsafe spawn_unchecked function in nightly if you haven’t seen that. Not sure why it hasn’t gone stable yet though.

[oliver-giersch]

But scoped threads can be safe, which is the point. I pushed for this addition stdlib in order to use this function in crossbeam::scoped, which allows to avoid some allocations and lifetime hacking. I just didn’t have the time to push things further due to being occupated with my masters thesis (which coincidentally is about cooperative and preemptive suspension in the context of work stealing )

[ckaran]

I expect there will be three kinds of tasks programs will run:

• IO tasks driven by the futures executor.
• CPU-intensive tasks driven by Rayon.
• Blocking tasks (e.g. reading from stdin) driven by dedicated threads.

We will need a way of communicating between those three kinds of tasks. For example, an IO task might want to kick off a long computation onto Rayon and Rayon will need to notify the IO task when completed. There might even be a fourth kind for tasks on the GPU, I don’t know.

OK, I think that there are two parts here.

First, I think that mimicing rayon’s plumbing (see plumbing docs and README) is the way to go. At a high level, you can have specialized consumers for IO, CPU, GPU, blocking tasks, etc. Each of these consumers are used for different purposes. For example, the IO consumer might really be looking to iterate over set of readers, and its parallel iterator has been optimized to be like a select() or poll() (rayon’s for_any() seems a lot like a good fit for this), while the CPU/GPU versions expect to never block, and are really optimized for parallel execution (they implement all of the ParallelIterator trait, they just aren’t optimized over some bits of it). Above that are schedulers which are both producers and consumers. They act as the interior nodes of a tree whose leaves are the consumers I just talked about before. The scheduler’s task is to keep all their children full of work, and to gather the results as they come in. Thus, you may have a CPU+GPU scheduler that knows how to distribute work over a set of CPUs + GPUs (child asks parent for work, parent steals work for child from other children, or asks its parent for more work). You could then layer another scheduler on top of the CPU+GPU scheduler that knows how to distribute work across a cluster of compute nodes. The depth of layering is up to the programmer. All of this handles moving work up and down the layers, but it doesn’t allow jumping between nodes, which brings up my next point.

std::sync::mpsc already defines both channel and sync_channel. In the example you gave above, the IO task could create a new channel, hand the send side over to rayon. On the IO side, it would create a vector of closures, one of which listens to the receive side of the channel, and the other of which does IO work. This vector is then executed using par_iter().for_each(|x| x()), which means that the task that is blocked waiting for rayon doesn’t prevent the IO task from executing (or vice-versa).

[ckaran]

an end user needs to be able to say ‘this chunk of code should be parallelized because it will never block on io’, and ‘this chunk of code is listening to the game controller, and will be blocked for long periods’.

• IO tasks driven by the futures executor.
• CPU-intensive tasks driven by Rayon.
• Blocking tasks (e.g. reading from stdin) driven by dedicated threads.

I was thinking about what both I and @stjepang said earlier, and I realized that we may already have most of the machinery we need in place to make a rayon-like library work with both blocking and non-blocking tasks. We already have the std::marker traits which allows the compiler to decide if something can cross thread-boundaries, etc. What would happen if we added the marker std::marker::Blocking? Anything that could be a blocking task would implement the trait; if you have some kind of executor that can’t correctly handle work that may block, it just has a bound of !Blocking for any work that is fed to it. The compiler can then decide if the bounds are met. All IO in the standard library could then be marked with Blocking, as well as anything else that could give headaches.

There may need to be some kind of dynamic check as well, but I haven’t thought far enough ahead yet to know if that is needed.