Scheduling should be topology/NUMA aware

[nagisa]

Currently rayon spawns as many threads as there are logical PUs on the machine and does nothing more as far as I can tell. This is subpar. Instead it should look at the hardware topology and make an informed decision on how many threads to spawn and where to schedule them. Even more so now, that the rayon-core will share the same pool of workers across all the different users of rayon.

[cuviper]

I agree we should have something, but it's a hard problem in general. To really be NUMA-optimized, programs ought to use a NUMA-aware allocator and/or migrate pages between nodes as needed, both of which are really outside of the scope of rayon. We don't have any idea of what data might be access by a job, let alone where it lives, except for perhaps the immediate collection being iterated.

As a first step, I think we could do better just by offering a node-restricted threadpool. You can already accomplish this manually, by setting num_threads and using a start_handler to set the scheduling affinity to the appropriate CPU mask. I think wrapping this in a nice API would get us an "80%" solution, where experts can use other means to allocate their memory on a specific node, then launch rayon into that node.

For deeper integration, I think the job stealing would need to be aware of the NUMA hierarchy, which can span multiple levels. Start by only trying to steal jobs from your own node, then look one level out, etc. But this is still a fairly crude way to attempt to keep memory locality, as again we don't really know the way data is allocated.

We should also research what other threading libraries in other languages do for NUMA.

[cuviper]

Even more so now, that the rayon-core will share the same pool of workers across all the different users of rayon.

FWIW, the workers were also shared before rayon-core, except when your project resolved to multiple distinct rayon versions. The point of rayon-core is to make sure we have that common pool even when there are multiple rayon versions.

There's ThreadPool::new() if you really want your own private pool, and I'm imagining that setting affinity to a NUMA node could be just another part of the Configuration.

[nikomatsakis]

I basically agree with @cuviper =) -- solid goal, difficult to achieve well. Giving people the ability to configure things would be an obvious starting point.

[farnoy]

Another thing to consider would be a split-LLC topology, I think all of this can be detected using hwloc, there seem to be Rust bindings available.

This issue affects me greatly, so I would like to help with implementation. I have a NUMA and split-LLC (two L3 caches per NUMA node) CPU, so I can test it myself.

I am no expert on the matter and have not researched work-stealing queues and algorithms, but my naive idea would be as follows.

1. Keep a list of queues to steal from for each locality bucket (think NUMA node)
2. Have each worker update the location of its own queue in that data structure periodically, to reflect the latest scheduling information from the OS
3. Prioritize stealing work-items from the same bucket as the worker, going to other buckets if there is nothing to steal

As far as memory locality is concerned, I think that if work-stealing queues are allocated in unique pages of memory, the OS will migrate them automatically. We could always try to do things like that explicitly.

Would this solution introduce expensive locking to maintain these lists of queues? Is there a clever way to reduce contention? My intuition would be that in a loaded system, worker threads would eventually settle down on specific CPUs and this migration would be very rare, unless external pressure forces the OS to move rayon threads around. It seems to me that this initial cost seems similar to the one exerted by work-stealing operations that hammer that one queue where the work initiated in. Atomics and coherency can't be cheap at that level of contention.

Any feedback and guidance is appreciated.

[cuviper]

Here's a user's experience where OpenMP fared much better than Rayon:

https://www.reddit.com/r/rust/comments/bto10h/update_a_scaling_comparison_between_rustrayon_and/

In my own comments and experiments on 128-thread POWER9, I found that while we fared worse on all threads, Rayon and OpenMP actually perform pretty similarly when pinned to a single NUMA node. In fact Rayon showed higher throughput on 4/5 tests, overall 6.17s elapsed time vs. 6.62s.

[jack-pappas]

Intel's OpenMP library is implemented on top of their open-source, Apache2-licensed Thread Building Blocks (TBB) library; perhaps there are some ideas there that can be ported into Rayon to improve performance (on NUMA architectures or otherwise)?

https://github.com/intel/tbb

@cuviper to your comment above (from a couple years back): TBB includes a custom allocator, tbbmalloc, which is also part of their open-source repo (under the src/tbbmalloc folder). Maybe that could be used with Rust's custom allocator functionality? (If so, I'd guess linking+invoking tbbmalloc would be the easiest way at first; then maybe it could be ported later if it proves fruitful.)

[cuviper]

@jack-pappas My impression is that tbbmalloc is about scaling the allocator itself. That may be beneficial if you're allocating from different threads, but I know that glibc has made its own scalability improvements in recent years too.

Also, I don't see any mention of NUMA in the TBB source. From this forum post, it sounds like they also punt on this issue:

TBB task scheduler does not control threads distribution across available cores. This completely belongs to OS scheduler domain.

It might be an interesting data point to port that Babel Stream code to TBB though.

[cuviper]

My wild guess is that OpenMP just has more predictable memory access than Rayon's work-stealing pool, so memory that's first touched from a thread on one particular NUMA node will probably continue to be used only on that thread/node.

[wagnerf42]

are we sure the vectors are not reallocated in the motivating example ? got bit several times by that.

also, i'll be doing a bit of numa aware scheduling in rayon-adaptive but not right now.

[nagisa]

Re-titling the issue to be more general than just "NUMA" as nowadays even within a single NUMA node certain logical cores are a better choices than the others when deciding where to send work.