Scoped threads in the nursery (maybe with rayon?)

[nikomatsakis]

Not that C++'s solution can be applied 1:1 to Rust, but I think that the solution they have is very flexible, and makes a lot of sense.

Cool, I hadn’t seen that! I’ll take a look and let you know what I think. =) Always happy to pilfer good ideas from C++ (they have many…).

(To be clear, I don’t claim to be an expert when it comes to parallel runtimes – I’ve thought a fair amount about it, and done a modest amount of research, but I know there is lots of work out there I’m not aware of.)

[gnzlbg]

and if you don’t write with_scheduler, then you get the default (rayon-core).

Sounds good to me

Cool, I hadn’t seen that! I’ll take a look and let you know what I think.

Just keep in mind that this paper is more a specification than a rationale discussion, and also, that the problem it solves isn’t necessary what rayon aims to solve.

---

Bit of history: The design has evolved from the Networking WG which started standardizing Christopher Kohlhoff’s Boost.ASIO (~2012-2013). At the same time, Google wanted to standardize thread-pool-like things, and provide a dynamic API to abstract over those:

• N3747: A universal model for asynchronous operations (Kohlhoff, 2013, the original proposal of what we currently have).
• N4414: Executors and schedulers, revision 5 (Google, 2015, not very relevant).

It turned out that network people hated virtual calls (big surprise). Anyhow at the same time the Parallel STL technical specification was being approved (the parallel STL is C++'s rayon). It turned out that nvidia wanted the parallel STL to work on their 10.000 core GPUs, and Intel wanted to be able to implement it using Cilk+, and also, to be able to use SIMD, so here things start getting out of hands, now executors (schedulers) need to solve all these problems too. So they become a feature of their own:

• P0113R0: Executors and Asynchronous Operations, Revision 2 (Kohlhoff, 2015)

And everybody joins to the party complaining that executors don’t solve their problems:

• N4406: Parallel Algorithms Need Executors (nvidia, 2015, very rayon relevant: why should parallel algorithms be parametrized over a scheduler, superseded by P0058R1, read that instead).
• P0076R2: Vector and Wavefront Policies (Intel, 2016, kindish relevant)
• P0058R1: An Interface for Abstracting Execution (Nvidia, 2016, rayon relevant (in particular the task_block part))
• P0072R1: Light-Weight Execution Agents (Nvidia, 2016, rayon relevant).
• N4411: Task Block (formerly Task Region) R4 (Intel/Microsoft, 2015, rayon relevant, fork-join parallelism).
• … and many others, Intel with more Cilk+ stuff, AMD with the Heterogeneous Systems Architecture stuff, IBM with OpenMP, and the SIMD proposals…

At the same time, ~2015-2016, Microsoft wrote a full specification for C++ co-routines, implemented those in MSVC and Clang (the LLVM coroutines), and wanted to get this into C++17, so now executors needed to solve co-routine problems as well, particularly, in the context of networking:

• P0286R0 A networking library extension to support co_await-based coroutines (Kohlhoff, 2016)
• N4482: Some notes on executors and the Networking Library Proposal (Kohlhoff, 2015).

And the specification we currently have, is the result of executors going full circle, from networking and thread pools, to data parallelism in its 1000 flavors, and finally through coroutines back to networking. I don’t think this design makes everybody happy (in particular, Google), but it doesn’t make anybody specially unhappy, which is what ISO standardization is all about. Rust can definitely do better.

EDIT: I’ve added the Intel paper on fork-join parallelism, since that is only tangentially addressed by the executors proposals for algorithms.

[stjepang]

How does everyone feel about this today?

I think we should really consider moving scoped threads into the standard library. They have become a fundamental synchronization primitive in Rust and it’s a shame we still need crates for them. After all, scope() is just a small extension of thread::spawn(), that’s all there is to it. Crossbeam’s API surface is pretty small and has matured through years of experience so I’d be willing to write a RFC for inclusion into the standard library.

Another reason why I think scoped threads are important is because they teach a key lesson in understanding how borrowing interacts with threads. Having a simple primitive that allows one to spawn a thread that borrows stuff would be beneficial to teaching Rust. People learning Rust keep asking for scoped threads on IRC and social media all the time. It’s a very common stumbling block.

Note that I’m not proposing to include any kinds of thread pools - in my opinion, that belongs outside the standard library, at least for the foreseeable future until Rayon or futures executors mature enough. All I want today is a thread::spawn() variant that doesn’t require F: 'static.

[stjepang]

Just to elaborate on the previous comment…

The API for scoped threads we’d add to std::thread is:

struct Scope<'env> {}
struct ScopedJoinHandle<'scope, T> {}

fn scope<'env, F, R>(f: F) -> Result<R>
where
    F: FnOnce(&Scope<'env>) -> R;

impl<'env> Scope<'env> {
    fn spawn<'scope, F, T>(&'scope self, f: F) -> ScopedJoinHandle<'scope, T>
    where
        F: FnOnce(&Scope<'env>) -> T + Send + 'env,
        T: Send + 'env;
}

impl<'scope, T> ScopedJoinHandle<'scope, T> {
    fn join(self) -> Result<T>;
    fn thread(&self) -> &Thread;
}

impl Builder {
    fn spawn_scoped<'scope, 'env, F, T>(
        self,
        &'scope Scope<'env>,
        f: F,
    ) -> io::Result<ScopedJoinHandle<'scope, T>>
    where
        F: FnOnce(&Scope<'env>) -> T + Send + 'env,
        T: Send + 'env;
}

[ckaran]

P0058R1: An Interface for Abstracting Execution (Nvidia, 2016, rayon relevant (in particular the task_block part) )

I want to signal boost this type of application; when I first heard about rust, my first thought was ‘thank God I don’t have to learn GPGPU programming, rust will eventually be able to handle it!’ This was in part due to my knowledge of projects like RLSL, and in part because I knew that safe rust has an incredible amount of information available to the compiler, which means that it might be possible to make SPIR-V a backend for rustc. I don’t know what the final API that is pulled into the library will be, but I’m hoping that whatever is chosen will make it easy to use GPUs (and any other object that is effectively a coprocessor) from within the language/standard library.

[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.