Lock-free parallel write to array and ownership

I am new to rust. And I read about ownership and borrowing, for trying to figure out how to create lock-free parallel write to array. In general it is posible write in this way without data races, if we take for each thread non-overlaping slices from this array, and each thread would work only with his own slice (but as I understand in rust slices are immutable).

But I can't see any way to do this with ownersip rules that I was read in rust book. And as I understand unsafe context doesn't turn of this rules.

To be honest I never wrote this in any languages, but I saw this pattern a lot, so maybe my understanding of this patern is incorrect.

Any suggestions?

First, you probably want to have a look at rayon that is able to do it for you.

But if you want to do it yourself:

  • No, rust slices are not necessarily immutable. &mut [T] can mutate the content (not the length).
  • You can use split_at to split a mutable slice into two non-overlapping mutable slices (there's unsafe code behind the scenes and you can have a look how it's done).
  • You can use scoped threads (for example in crossbeam-utils) to solve lifetime problems with the references.
5 Likes

Here is an example:

use ::std::{
    iter::FromIterator,
    thread,
};

/// Maximum number of threads
const N: usize  = 8;

fn main ()
{
    let slice: &mut [i32] =
        &mut Vec::from_iter(0 .. 128)[..]
    ;
    ::crossbeam::scope(|scope| {
        slice
            .chunks_mut(
                // At most N threads
                (slice.len() as f64 / (N as f64))
                    .ceil()
                    as usize
            )
            .for_each(|sub_slice: &mut [i32]| {
                scope.spawn(move |_| {
                    println!(
                        "{:?} doubling {:3?}",
                        thread::current().id(),
                        sub_slice,
                    );
                    sub_slice
                        .iter_mut()
                        .for_each(|at_elem: &mut i32|
                            *at_elem *= 2
                        )
                });
            })
        ;
    }).expect("Some thread panicked");
    println!("slice = {:?}", slice);
}

Printing:

ThreadId(1) doubling [  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15]
ThreadId(2) doubling [ 16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31]
ThreadId(5) doubling [ 64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79]
ThreadId(4) doubling [ 48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63]
ThreadId(3) doubling [ 32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47]
ThreadId(6) doubling [ 80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95]
ThreadId(7) doubling [ 96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111]
ThreadId(8) doubling [112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127]
slice = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46 ...
3 Likes

You mean split_at_mut, of course.

2 Likes

But regarding the initial question, it was indeed justified: if you see a problem with concurrently mutating a slice in Rust, then congratulations, you've got a grasp of the language mechanics :stuck_out_tongue:

The invariants may sometimes be too restrictive given the granularity of ownership/borrowing. By default that granularity is at the array/whole slice level.
However, since mutating disjoint subslices is known to be sound, by using unsafe (where it is possible to forge &mut (and &) references "at will" (hence the potential dangerosity of unsafe)), Rust exposes its usage with a safe API around it:

There are then other nice abstractions built on top of that, such as:

6 Likes

Thanks for answers and example. So it is possible. I will try to dig deeper than in concurrent Rust :slight_smile: