Rayon alternatives

[davidlattimore]

Rayon serves us pretty well. We do have some problems though. For example, it runs the init closure passed to try_for_each_init once for each work item instead of once for each thread. This is pretty wasteful, since each call allocates a new arena, so for 32 threads we end up with about ~1000 arenas instead of 32. It's also hard to be sure what the overhead of rayon is unless we try other things.

Unfortunately, we make so much use of rayon that switching to anything else is pretty hard. In addition to the usual par_iter, we also use par_bridge, join, scopes, spawn, scoped spawning and spawn_broadcast.

I've just had a look at orx-parallel which looks interesting. The two main issues that I've observed, without actually trying to do any conversion, so there may be more are:

• I can't see how to do graph algorithms. Currently we have two graph traversal algorithms. We use scoped spawning for one and spawn_broadcast for the other. Ideally, we'd have some kind of WorkQueue<T> where some initial work could be added to the queue, then more work could be added to the queue in response to processing other items from the queue.
• It looks like it doesn't use a thread pool, but instead spawns new threads for each bit of work that gets done. This might be OK for us to experiment, but I wouldn't want that longer term. We do a lot of separate parallel processing steps, so we'd end up with heaps and heaps of threads being spawned. Even if the overhead of spawning a thread was really low, it'd make it hard to look at CPU profiles.

Another possibility is chili. This is lower level and only provides join. We'd probably need some abstractions built on top of this before using it would be practical.

There's a fork of rayon that uses chili. I'm not sure how actively this is being worked on. It doesn't have its own repository, but lives in a repository with other stuff. It also doesn't appear to support scopes or anything else that we could use to implement our graph algorithms.

[mati865]

Looks like the thread pool, at least, is on the orx-parallel roadmap: orxfun/orx-parallel#82

Maybe it'd be worth asking the author about Wild's graph algorithms via discussion?

Regarding try_for_each_init, I doubt such an API would be feasible. I'm wondering whether thread_local could somehow help to reduce the number of allocations, but I'll think more about it when I return from kayaking.

[davidlattimore]

I filed an issue on the orx-parallel repo to ask about scopes.

The situation with per-thread init functions looks better with orx-parallel than it is with rayon's try_for_each_init. orx-parallel has a method using that can be called on a parallel iterator to provide a per-thread initialiser. It looks like it guarantees that it'll only get run once per thread.

[mati865]

Oh, that looks neat. Maybe it'd be feasible to add to Rayon after all?

[davidlattimore]

Maybe. My guess is that the current architecture of rayon probably makes it hard. The issue has been open for 5 years.

[NthTensor]

Hello all! I'm a contributor to bevy (a rust game engine) and someone pointed me to this thread because we've been having similar issues with our multi-threading solution. Rayon is almost exactly what we need, but it's not quite right. Partially the issue is overhead: rayon is throughput oriented, Game engines are highly latency sensitive.

So I've been working on a new thread pool called forte which is based on the rayon architecture and api, but uses lazy scheduling techniques (borrowing from things like chili and Tzannes et al) instead of the more classical work stealing approach.

It supports spawn (for both futures and closures), join, scopes, and scoped spawns (also for both futures and closures). There's no broadcast or parallel iterators yet, but I am working on them (and these will eventually include something basically identical to par_bridge). It's still highly experimental, the internals are very unstable, and performance in some cases is still being worked on. But I thought you might be interested in evaluating it.

It's very likely you won't be able to use it in it's current state. But if yall are interested in the general direction and are able to provide a list of blockers, I'd be happy to work on resolving them so that you can evaluate it properly.

[davidlattimore]

Great to see more options in this area. Once it supports par_iter and par_bridge, I'll definitely give it a try!

[davidlattimore]

Another alternative that was suggested on Reddit is spindle. It seems to be built on top of rayon, but is optimised for small tasks. The README is still pretty minimal, so I'm guessing it's still early days yet, but worth keeping an eye on.

[SkiFire13]

For example, it runs the init closure passed to try_for_each_init once for each work item instead of once for each thread.

Random idea: could you create a thread_local::ThreadLocal and get it in the init closure? That way you would be guaranteed to have only one instance per thread.

On top of that you might want to set a minimum chunk length in rayon to force at least that many items to be processed at once in a thread, which should guaranteed the init closure to be run only once for all of them.

[davidlattimore]

Thanks. Yep, nicoburns on reddit suggested thread_local too. I tried it this morning and it seems to work. Unfortunately I think I overestimated how much of a problem creating lots of arenas actually was, since it doesn't make much difference to the runtime. I may still submit the change, since it's pretty simple and I think marginally better. There may be some other places where we might be able to take advantage of thread_local where we currently create a whole Vec per object group, however it makes deterministic behaviour a little harder.

We do set minimum chunk length in one place where we have some very fine-grained parallelism. Most of our parallel iteration is over groups of multiple objects and we control the number of objects in each group, so the chunk size usually is pretty reasonable.

[chrisheib]

Just throwing this in here: https://docs.rs/tokio-par-util/latest/tokio_par_util
Might be worth a try to just use tokio, but there are some caveats and most likely quite some overhead, as tokio is more specialised for async IO and less for async compute. Still interesting here IMO due to all of the known tokio convenience functions and macros being available this way.

My uninformed guess would be that there is some static overhead with setting up the tokio scheduler, which will probably have diminishing impact the more compute is actually used for linking. So likely overall slower then Rayon for small projects, but similarly fast in bigger projects, and that of course with better ecosystem integration and the likes.

[mati865]

From my experience, Tokio is a bad fit for Wild use case, for the same reasons why rustc doesn't use Tokio.

[gendx]

I've missed that discussion was happening here, so apologies for the copy-paste from #1127.

---

I'd like to pitch paralight that I've been working on, a lightweight parallelism built from scratch on a different architecture than Rayon. It's not complete yet (hence the alpha version 0.0.6) and won't support all the patterns that Rayon offers (Paralight targets parallelizing sequential objects such as slices), but as a trade-off it brings performance improvements on the supported cases.

In particular, Paralight indeed supports a try_for_each_init method that only initializes once per thread. From a quick look at your code, the input you're iterating on in parallel is a mutable slice, which is right in Paralight's design target and indeed well supported.

One caveat is that a thread pool must be explicitly passed on each call to create a parallel iterator, and that each parallel pipeline must have exclusive access to the thread pool (via a &mut reference), which prevents patterns like recursive parallel iteration (so graph algorithms may be challenging to parallelize with Paralight). Another current limitation is that inputs with more than u32::MAX elements are not yet supported.

[davidlattimore]

Hi Guillaume! Great to see more development in this space!

For thetry_for_each_init problem, a few people suggested that I try the thread_local crate. It worked well, but it turned out that creating lots of arenas wasn't as big a performance issue as I had thought. I may still merge the thread_local change, but haven't as yet.

Something more tuned to working with slices sounds like it could be a significant win though, so I'd be very interested to try that out. I guess the tricky bit would be if we could use paralight for just some parts that fit, while leaving the other parts using rayon. I don't suppose there's any way for them to share a thread pool? Although I guess for just experimenting with it, maybe I shouldn't worry and just have a second thread pool.

[gendx]

I don't suppose there's any way for them to share a thread pool? Although I guess for just experimenting with it, maybe I shouldn't worry and just have a second thread pool.

Short answer: I wouldn't worry too much about having several thread pools, as the overhead of having 8 (or whatever your parallelism is) additional idle threads waiting for the kernel to wake them up¹ shouldn't be significant, and Paralight thread pools can easily be destroyed when not needed². CPU-wise idle threads should cost nothing, and memory-wise they should cost the stack space (typically 8MB per thread on Linux nowadays?).

Long answer: Getting the same worker threads to work both for Rayon and Paralight would be tricky. Paralight's model assumes exclusive access to the thread pool, so some additional synchronization mechanism would be needed to ensure all worker threads are released from their Rayon duties before they can run a Paralight pipeline. If the implementation isn't carefully thought through, this could cause a Paralight pipeline to be blocked, or worse a deadlock.

Technically, all these worker threads are running a loop specifically crafted for their parallelism framework (Rayon, Paralight), and turning that into a more general kind of loop that can dispatch either type of work would be non-trivial if not ugly, and very likely increasing the unsafe surface (Paralight aims to keep the amount of unsafe code as tight as feasible).

Footnotes

1. Paralight worker threads ultimately wait for work using Condvar::wait_while(), which (on Linux) is implemented via the futex syscall. ↩

2. One option to avoid idle threads staying around for a while would be to have local thread pools that are created and destroyed on demand for each computation (whether that's beneficial is of course to be benchmarked). Given that Paralight thread pools are explicit, it's easy to destroy them by simply dropping them. It's much more difficult to switch off Rayon's global thread pool (https://github.com/rayon-rs/rayon/issues/688, https://github.com/rayon-rs/rayon/issues/544) precisely because it's implicit and global (e.g. some other thread might be submitting work while the current thread tries to kill the thread pool). ↩

[davidlattimore]

My main problem with multiple thread pools is that it messes up how the the CPU profiles look in the firefox profiler. It means there's lots of extra rows. Probably a silly reason, but it bothered me before when we used to have our own thread pool in addition to rayon's.

What about if there was an API for constructing a ThreadPool where the user of the API provided the threads and the ThreadPool just had temporary control of them. Something like this:

impl ExternalThreadPoolBuilder {
    fn new() -> Self {...}

    /// Build a thread pool. `spawner_cb` must call `run_thread_loop` from `num_threads` different threads.
    fn build(&self, num_threads: usize, spawner_cb: impl Fn()) -> ThreadPool {...}

    /// Do work on the current thread. Will return once the `ThreadPool` produced by `build` gets dropped.
    fn run_thread_loop(&self) {...}
}

That could then be used by the user to bridge between paralight and some other library that has a thread pool. e.g. rayon:

fn with_paralight_thread_pool(work: impl FnOnce(&mut ThreadPool)) {
    let pool_builder = ExternalThreadPoolBuilder::new();

    rayon::in_place_scope(|s| {
        let mut thread_pool = pool_builder.build(rayon::current_num_threads(), || {
            s.spawn_broadcast(|_, _| {
                pool_builder.run_thread_loop();
            });
        });

        work(&mut thread_pool);
    });
}

[gendx]

A little update: Paralight v0.0.8 is now released, with support for running on top of a Rayon thread pool (via the rayon feature).

The design, proposed by @DouglasDwyer in gendx/paralight#10, is slightly different than what we had discussed in this thread, and I think more elegant overall. It directly builds upon the existing .with_thread_pool() combinator, and for the Rayon backend only a const reference is needed, as exclusive access to the thread pool isn't required.

// Wrap the global Rayon thread pool.
let wrapper = RayonThreadPool::new_global(
    ThreadCount::try_from(rayon_core::current_num_threads())
        .expect("Paralight cannot operate with 0 threads"),
    RangeStrategy::WorkStealing,
);

// Use it by reference.
groups
    .par_iter_mut()
    .with_thread_pool(&wrapper)
    .try_for_each_init(...);

It's possible to use either the default global Rayon thread pool (RayonThreadPool::new_global), or a local (user defined) Rayon thread pool (RayonThreadPool::new), see the docs.

Lastly, the GenericThreadPool trait provides an extension point to support other thread pool backends.