CODEWITHSUNDEEP
multithreadingrustvectorrandom-accessrayon
Adam Olsson
Adam Olsson

Reputation: 32

Parallel random access of vector using indices that are guaranteed to not overlap

Context

I have implemented a broad phase collision detection algorithm that returns a nested vector (Vec<Vec<usize>>) of indices. I can guarantee that each index appears at most once within the nested vectors. I want to use these indices to index into a vector of bodies and perform narrow phase collision detection in parallel.

Problem

In a minimal example we would for each vector of indices, take a &mut reference to the element to form a vector of unique &mut references and perform narrow phase detection on this vector.

let bodies: Vec<u8> = vec![0,1,2,3,4,5,6];
let pass: Vec<Vec<usize>> = vec![vec![0,4],vec![2,3,5]];

pass.par_iter()
  .map(|indices| {
      let local_bodies: Vec<&mut u8> = 
          indices.iter().map(|i| &mut bodies[i]).collect();
      narrow_phase(&local_bodies)
});

But the errors I run into is 2-fold:

Question

What is the preferred way of doing this type of random access and mutating safely in rust? I would like to avoid the overhead of using Arc and Mutex. Additionally, I understand that the compiler can't guarantee safety by random access by itself but instead need some additional functionality (like Arcand Mutex).

Related Questions

Many go-to answers is to use build in chunks_mut and/or split_at_mut however I do not see them as applicable here as the indices are not sequential.

I found another question that seems to have the exact same problem, however the solution uses std::cell::Cell which does not implement the Sync trait.

Upvotes: 1

Views: 43

Answers (1)

Florian Brucker
Florian Brucker

Reputation: 10355

I haven't used it personally so far, but the paradis crate aims to provide

Parallel processing with disjoint indices.

It offers both a low-level unsafe API and a high-level API that "[allows] many parallel access patterns to be expressed in safe code, or with a minimum of unsafe code".

Upvotes: 0

Related Questions