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.