I have a case where multiple threads must update objects stored in a shared vector. However, the vector is very large, and the number of elements to update is relatively small.
In a minimal example, the set of elements to update can be identified by a (hash-)set containing the indices of elements to update. The code could hence look as follows:
let mut big_vector_of_elements = generate_data_vector();
while has_things_to_do() {
let indices_to_update = compute_indices();
indices_to_update.par_iter() // Rayon parallel iteration
.map(|index| big_vector_of_elements[index].mutate())
.collect()?;
}
This is obviously disallowed in Rust: big_vector_of_elements cannot be borrowed mutably in multiple threads at the same time. However, wrapping each element in, e.g., a Mutex lock seems unnecessary: this specific case would be safe without explicit synchronization. Since the indices come from a set, they are guaranteed to be distinct. No two iterations in the par_iter touch the same element of the vector.
What would be the best way of writing a program that mutates elements in a vector in parallel, where the synchronization is already taken care of by the selection of indices, but where the compiler does not understand the latter?
A near-optimal solution would be to wrap all elements in big_vector_of_elements in some hypothetical UncontendedMutex lock, which would be a variant of Mutex which is ridiculously fast in the uncontended case, and which may take arbitrarily long when contention occurs (or even panics). Ideally, an UncontendedMutex<T> should also be of the same size and alignment as T, for any T.
Multiple questions can be answered with "use Rayon's parallel iterator", "use chunks_mut", or "use split_at_mut":
These answers do not seem relevant here, since those solutions imply iterating over the entire big_vector_of_elements, and then for each element figuring out whether anything needs to be changed. Essentially, this means that such a solution would look as follows:
let mut big_vector_of_elements = generate_data_vector();
while has_things_to_do() {
let indices_to_update = compute_indices();
for (index, mut element) in big_vector_of_elements.par_iter().enumerate() {
if indices_to_update.contains(index) {
element.mutate()?;
}
}
}
This solution takes time proportionate to the size of big_vector_of_elements, whereas the first solution loops only over a number of elements proportionate to the size of indices_to_update.
When the compiler can't enforce that mutable references to a slice elements aren't exclusive, Cell is pretty nice.
You can transform a &mut [T] into a &Cell<[T]> using Cell::from_mut, and then a &Cell<[T]> into a &[Cell<T>] using Cell::as_slice_of_cells. All of this is zero-cost: It's just there to guide the type-system.
A &[Cell<T>] is like a &[mut T], if that were possible to write: A shared reference to a slice of mutable elements. What you can do with Cells is limited to read or replace — you can't get a reference, mutable or not, to the wrapped elements themselves. Rust also knows that Cell isn't thread-safe (it does not implement Sync). This guarantees that everything is safe, at no dynamic cost.
fn main() {
use std::cell::Cell;
let slice: &mut [i32] = &mut [1, 2, 3];
let cell_slice: &Cell<[i32]> = Cell::from_mut(slice);
let slice_cell: &[Cell<i32>] = cell_slice.as_slice_of_cells();
let two = &slice_cell[1];
let another_two = &slice_cell[1];
println!("This is 2: {:?}", two);
println!("This is also 2: {:?}", another_two);
two.set(42);
println!("This is now 42!: {:?}", another_two);
}