Parallelize n-body, !Send problem

I'm trying to parallelize an n-body simulation with rayon, by chunks so that concurrent threads never mutate bodies accessed by others.

I have an iterator of rayon::ParallelIterator of iterators of iterators. (the first gives chunks of parallel iterators that can safely run concurrently, and each of them iterate on bodies)

There are two ways I've considered:

  • the safe way: each iterator contains slices of the data belonging to it. Con: that's a lot of references I don't strictly need for, and more pointer arithmetic overhead. (and performance is important for O(N²) simulation)
  • the unsafe way: each iterator contains a pointer to Layout (the main struct containing all the data), and safety is only ensured by the algorithm.

I've tried the second way, but my data are not Send, so even using std::ptr::NonNull (to avoid multiple mutable references errors) this won't compile.

Is there a way to do this without making it slower? and why not, to make it safer?

Finally I've just done this:

pub(crate) struct SendPtr<T>(pub std::ptr::NonNull<T>);

unsafe impl<T> Send for SendPtr<T> {}
unsafe impl<T> Sync for SendPtr<T> {}

I didn't know it was possible to cheat like that. It's not safer at all, but it compiles and it works.

Is your code published anywhere? It would be interesting if a similar performance can be achieved in a sound way.

2 Likes

I'd strongly advice you to use AtomicPtr, if you need to write and read a memory location from different threads. You may be getting away with what you're doing on x86, but weakly-ordered systems will not like your "thread-safe" smart pointer.

The iterators are defined here, created here and used here.

To clarify how they work:

image

  • for each color, from yellow to red, do
  • for each contiguous block of this color, do in parallel (i.e. one thread per block)
  • for each column of this block (n1), do
  • for each cell of this column (n2), do
  • compute force between n1 and n2

This is safe because we run concurrently only threads that work on blocks of the same color.

Ok, I will try that.