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.

Answer 2

How to do this in Rust? Resorting to unsafe is okay.

If you need two threads to mutate the same data, without locks, then you must use unsafe. It is Undefined Behaviour for two mutable references (&mut) to the same data to even exist, so you would need to access the data via *mut raw pointers, while being extremely careful to avoid data races.

However, depending on your algorithm, you may be able to avoid unsafe by creating non-overlapping &mut references with split_at_mut.

Answer 3

Here is a code using a Vector or AtomicI32 put into an Arc for doing what you need:

use std::sync::Arc;
use std::thread;

use std::sync::atomic::AtomicI32;
use std::sync::atomic::Ordering;

// ==================================================================
// ==================================================================
const SIZE: usize = 4;

// ==================================================================
// ==================================================================
fn new_worker( id: i32, // id for the thread
               a_data: Arc::<Vec<AtomicI32>> // Vec of i32 inside an arc-ptr
             ) -> thread::JoinHandle<()> {

    // create new thread
    // a_data is moved into the thread
    let hand = thread::spawn(move || {

        // a_data[id] <- 2 * id * a_data[id]
        // use load() for readng and store() for writing
        a_data[id as usize].store( 
            2 * id *
            a_data[id as usize].load( Ordering::Relaxed ),
            Ordering::Relaxed );
    });

    return hand;
} // ()

// ==================================================================
// ==================================================================
fn main() {
    let mut data : Vec<AtomicI32> = Vec::new(); //  vector of i32

    // populate the vector
    for _i in 0..SIZE {
        data.push( AtomicI32::new( 1 ) );
    } // for

    // put the array into an arc-ptr: move to the heap, share arc-ptr
    let data_arc = Arc::new(data);

    // share the data through the arc-ptr
    let hand1 = new_worker(1, data_arc.clone());
    let hand2 = new_worker(3, data_arc.clone());

    // wait for the threads to end
    hand1.join().unwrap();
    hand2.join().unwrap();

    // print their work
    println!( "2 == {:?}", data_arc[1].load( Ordering::Relaxed ) );
    println!( "6 == {:?}", data_arc[3].load( Ordering::Relaxed ) );
} // ()

Answer 4

Updated answer, previous produced UB (as Chayim Friedman noted). People say that compiler doesn't make optimization assumptions based on aliasing when dealing with raw pointers. If so then following approach shouldn't cause UB, however I'm not 100% sure:

unsafe fn example<T>(a1: *const T, a1_len: usize, a2: *const T, a2_len: usize) {
    let a2 = std::slice::from_raw_parts_mut(a2 as *mut T, a2_len);
    let a1 = std::slice::from_raw_parts(a1, a1_len);
    ...
}