同时可变地访问保证向量不相交的大向量的任意索引

Question

语境

我遇到多个线程必须更新存储在共享向量中的对象的情况。但是，向量非常大，并且要更新的元素数量相对较少。

问题

在最小示例中，可以通过包含要更新的元素的索引的（哈希）集来标识要更新的元素集。因此，代码如下所示：

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()?;
}

Rust显然不允许这样做：big_vector_of_elements不能同时在多个线程中可变地借用。但是，将每个元素包装在例如Mutex锁中似乎是不必要的：如果没有明确的同步，这种特定情况将是安全的。由于索引来自一组，因此可以保证它们是不同的。par_iter在向量的相同元素上没有两次迭代。

重提我的问题

编写一个并行修改向量中元素的程序的最佳方法是什么，在这种情况下，同步已经通过选择索引来解决，但是编译器不理解后者呢？

接近最佳的解决方案是将所有元素包装big_vector_of_elements在某种假设的UncontendedMutex锁中，这是其变体，Mutex在无竞争的情况下非常快，并且在发生争用（甚至发生恐慌）时可能会花费任意长时间。理想情况下，an UncontendedMutex<T>的大小和对齐方式也应与Tany相同T。

相关但不同的问题：

可以使用“使用人造丝的并行迭代器”，“使用chunks_mut”或“使用split_at_mut” 来回答多个问题：

• 如何在分区数组上运行并行计算线程？
• 并行处理vec：如何安全地进行操作，或不使用不稳定的功能？
• 如何将不相交的切片从矢量传递到不同的线程？
• 不同的线程可以写入同一Vec的不同部分吗？
• 如何赋予每个CPU内核对Vec的一部分的可变访问权限？

这些答案在这里似乎无关紧要，因为这些解决方案意味着迭代整个big_vector_of_elements，然后针对每个元素弄清楚是否需要更改任何内容。从本质上讲，这意味着这样的解决方案如下所示：

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()?;
        }
    }
}

此解决方案花费的时间与的大小成正比big_vector_of_elements，而第一个解决方案仅在与的大小成比例的多个元素上循环indices_to_update。

Answer 1

您可以indices_to_update通过调用对可变引用进行排序和提取split_*_mut。

let len = big_vector_of_elements.len();

while has_things_to_do() {
    let mut tail = big_vector_of_elements.as_mut_slice();

    let mut indices_to_update = compute_indices();
    // I assumed compute_indices() returns unsorted vector
    // to highlight the importance of sorted order
    indices_to_update.sort();

    let mut elems = Vec::new();

    for idx in indices_to_update {
        // cut prefix, so big_vector[idx] will be tail[0]
        tail = tail.split_at_mut(idx - (len - tail.len())).1;

        // extract tail[0]
        let (elem, new_tail) = tail.split_first_mut().unwrap();
        elems.push(elem);

        tail = new_tail;
    }
}

仔细检查此代码中的所有内容；我没有测试它。然后你可以打电话elems.par_iter(...)或其他什么。

Answer 2

当编译器不能强制对切片元素的可变引用不是独占时，Cell这很好。

您可以将 a&mut [T]转换为&Cell<[T]>using Cell::from_mut，然后将 a&Cell<[T]>转换为&[Cell<T>]using Cell::as_slice_of_cells。所有这一切都是零成本的：它只是在那里指导类型系统。

A&[Cell<T>]就像 a &[mut T]，如果可以这样写： 对可变元素切片的共享引用。您可以使用Cells执行的操作仅限于读取或替换 — 您无法获得对包装元素本身的引用，无论是否可变。Rust 也知道这Cell不是线程安全的（它没有实现Sync）。这保证了一切都是安全的，没有动态成本。

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);
}