Parallel write to array with an indices array

Question

I'm having trouble understanding the concurrency model in Rust coming from C++.

My array is to be accessed concurrently using another array that defines the indices. For example (Pseudocode):

let indices = [1, 2, 3, 4, 1, 2, 3, 2, 1, 1, 3, 2, 2];
let mut arr = [1, 2, 3, 4, 5, 6, 7, 8, 10];

indices.iter_par().for_each(|x| {
    arr[x] += x;
});

In C++, I would protect each index in arr with a lock or use atomic access. How could I do the same in Rust?

EDIT

I have another related question.

How could I pass a normal array as mutable into the parallel iterator, where I'm sure that no race conditions can occur?

let indices = [1, 2, 3, 4, 5, 6, 7, 8];
let mut arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

indices.iter_par().for_each(|x| {
    arr[x] = some_function(x);
});

*"In C++ I would simply protect each index in arr with a lock or use atomic access. How could I do the same in rust?"* - you can do the same in Rust with an array of [`Mutex`](https://doc.rust-lang.org/std/sync/struct.Mutex.html)s or [`AtomicI32`](https://doc.rust-lang.org/std/sync/atomic/struct.AtomicI32.html)s if that's what's required — kmdreko, Oct 19 '20 at 08:10
The problem I have is the functionality of the mutex in rust. Unlike in C++, the rust mutex encapsulates the data it protects. I need seperate protection for arr for parallel access or something that emulates that. Making the entire array atomic is one possibility, but not the prefered one. — Adam, Oct 19 '20 at 08:23
@Adam no, mutex and atomics provide *interior mutability* so you don't need to protect the array itself at all: Rust's borrow checker will not let you simulatnously read the array (to access or update its items) and update it (to add new items), so it's acting as a "static" RWLock. Though if you need something more complicated you can of course wrap the array in an [RWLock](https://doc.rust-lang.org/std/sync/struct.RwLock.html) working at runtime. — Masklinn, Oct 19 '20 at 13:09
Though note that it would probably be a better idea to preprocess `indices` in order to count the number of increments at each index, then you could zip that to your array and use something like `par_iter_mut` in order to increment each index the correct number of times without needing any synchronisation in your own code. — Masklinn, Oct 19 '20 at 13:14

score 4 · Accepted Answer · edited Oct 19 '20 at 18:12

4

I don't know what the point of performing this operation in parallel is if you need lock for each item, but you can achieve this using a Mutex around the array to mutate:

use rayon::prelude::*;
use std::sync::Mutex;

fn main() {
    let indices = [1, 2, 3, 4, 1, 2, 3, 2, 1, 1, 3, 2, 2];
    let arr = Mutex::new([1, 2, 3, 4, 5, 6, 7, 8, 10]);

    indices.par_iter().for_each(|&x| {
        let mut arr = arr.lock().unwrap();
        arr[x] += x;
    });
}

playground

EDIT

Based on the comment, you can have each element be atomic:

use rayon::prelude::*;
use std::sync::atomic::{AtomicUsize, Ordering};

fn main() {
    let indices = [1, 2, 3, 4, 1, 2, 3, 2, 1, 1, 3, 2, 2];
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 10]
        .iter()
        .map(|&n| AtomicUsize::new(n))
        .collect::<Vec<_>>();

    indices.par_iter().for_each(|&x| {
        arr[x].fetch_add(x, Ordering::SeqCst);
    });
}

edited Oct 19 '20 at 18:12

Shepmaster

388,571
95
1,107
1,366

answered Oct 19 '20 at 07:56

Gurwinder Singh

38,557
6
51
76

Thanks!, That is one possible solution. Is there another way using something like an array of locks? – Adam Oct 19 '20 at 08:38
1

Yes, like I mapped each array element to AtomicUsize, you can do the same for `Mutex` and then inside the loop you can take the lock on individual elements: `*arr[x].lock().unwrap() += x` – Gurwinder Singh Oct 19 '20 at 08:48
2

If you like living dangerously, you can [type-pun that array with a slice](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e65ff6d809edb21ec102330db9fb9a10) to save the `map`+`collect`. This is **not sound** on platforms where `AtomicUsize` has stricter alignment than `usize` (I'm not aware of any such platform, but they may exist). It's also easy to screw up because the pointer casts won't tell you if the types are inferred wrong (you get UB if you remove the `: [usize; 9]`, for example). On the whole this is a bad idea and I'm not sure why I am suggesting it. – trent Oct 19 '20 at 09:02
2

(However, given [`Atomic*::from_mut` just got merged (again)](https://github.com/rust-lang/rust/pull/76965), maybe we can hope for a future where there is an `AtomicUsize::from_mut_slice` that avoids these pitfalls and lets you do the zero-copy version in entirely safe code.) – trent Oct 19 '20 at 09:06

Parallel write to array with an indices array

EDIT

1 Answers1

EDIT

Linked