How do I write to a mutable slice from multiple threads at arbitrary indexes without using mutexes?

Question

I have two slices that are passed from another method:

fn example<T>(a1: &[T], a2: &mut [T]) {}

I want to process a1 with multiple threads and then write to a2 using completely arbitrary indices that are only known when each thread is executed. The indices are guaranteed by my algorithm to be mutually exclusive, so there is no data race.

The borrow checker doesn't like sharing mutable references among threads since it doesn't know of the guarantee our algorithm makes. I also get a lifetime 'static required rustc (E0621) error.

So how to do this in Rust?

Answers to

• How can I pass a reference to a stack variable to a thread?
• Simultaneous mutable access to arbitrary indices of a large vector that are guaranteed to be disjoint
• How do I pass disjoint slices from a vector to different threads?
• How do I run parallel threads of computation on a partitioned array?
• How to get mutable references to two array elements at the same time?

Do not answer my question.

The answer to the first question addresses the scoping problem, but not the problem of accessing arbitrary mutually disjoint indexes. The answer to the second question suggests as_slice_of_cells but that doesn't work here because of the aforementioned reason, namely the arbitrary access. The answer to the third question similarly suggests as_slice_of_cells but again, the assumption that the array can be split into disjoint parts cannot be fulfilled here. The fourth question again asks about partitioning the array, which we cannot do here. And the same applies to the fifth question.

One answer to the scoping problem (https://stackoverflow.com/a/64502824/10056727) actually attempts to address this problem, but it doesn't suggest to use crossbeam and the alternative suggested is more unsafe than the top answer here.

Answer 1

You are running into two distinct issues when trying to implement your algorithm:

1. Sharing non-'static references across threads is not possible with std::thread::spawn.
2. Writing to mutually disjoint indexes in a slice without synchronization can only be done safely if you can do so by splitting the slice into multiple smaller slices and giving each split slice exclusively to each of the threads.

The first problem is easily avoided by using crossbeam::scope to spawn the threads rather than std::thread::spawn. However the latter issue requires an unsafe solution. However since you know that the indexes are mutually disjoint, there is no data-race in practice, and you can use UnsafeCell to assert to the compiler that there are no data-races. To do this for a slice, you can use the following utility:

use std::cell::UnsafeCell;

#[derive(Copy, Clone)]
pub struct UnsafeSlice<'a, T> {
    slice: &'a [UnsafeCell<T>],
}
unsafe impl<'a, T: Send + Sync> Send for UnsafeSlice<'a, T> {}
unsafe impl<'a, T: Send + Sync> Sync for UnsafeSlice<'a, T> {}

impl<'a, T> UnsafeSlice<'a, T> {
    pub fn new(slice: &'a mut [T]) -> Self {
        let ptr = slice as *mut [T] as *const [UnsafeCell<T>];
        Self {
            slice: unsafe { &*ptr },
        }
    }
    
    /// SAFETY: It is UB if two threads write to the same index without
    /// synchronization.
    pub unsafe fn write(&self, i: usize, value: T) {
        let ptr = self.slice[i].get();
        *ptr = value;
    }
}

This utility allows you to convert an exclusive slice &mut [T] into a slice that can be shared, but still used for mutation. Of course, this means that writing to it can result in a data race, if multiple threads write to the same index without synchronization. Thus the write method is unsafe and will cause UB if this assumption is violated

The UnsafeSlice utility will still guarantee that you have no use-after-free or out-of-bounds errors when using it. Only verification of race conditions is turned off with UnsafeSlice.

To see that the conversion in the constructor is sound, please see the safety comments inside the Cell::from_mut and Cell::as_slice_of_cells methods.