multithreading - 如何在不使用互斥锁的情况下从任意索引处的多个线程写入可变切片？

Question

我有两个从另一个方法传递过来的切片:

fn example<T>(a1: &[T], a2: &mut [T]) {}

我要处理 a1多线程，然后写入 a2使用 完全任意仅在每个线程执行时才知道的索引。我的算法保证索引为 互斥 ，所以没有数据竞争。
借用检查器不喜欢在线程之间共享可变引用，因为它不知道我们的算法所做的保证。我也收到了 lifetime 'static required rustc (E0621)错误。
那么如何在 Rust 中做到这一点呢？
回答

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?

不要回答我的问题。
第一个问题的答案解决了范围问题，但没有解决访问 的问题。任意互不相交的索引。第二个问题的答案提示 as_slice_of_cells但这在这里不起作用，因为上述原因，即 任意使用权。第三个问题的答案同样暗示 as_slice_of_cells但同样，这里不能满足数组可以分成不相交部分的假设。第四个问题再次询问对数组进行分区，我们在这里不能这样做。这同样适用于第五个问题。
范围界定问题( https://stackoverflow.com/a/64502824/10056727 )的一个答案实际上试图解决这个问题，但它不建议使用横梁，并且建议的替代方案比此处的最佳答案更不安全。

Answer 1

在尝试实现算法时，您遇到了两个不同的问题:

共享非 'static std::thread::spawn 不能跨线程引用.

如果您可以通过将切片拆分为多个较小的切片并将每个拆分的切片专门分配给每个线程，则可以安全地在没有同步的情况下写入切片中互不相交的索引。

使用 crossbeam::scope 可以轻松避免第一个问题。生成线程而不是 std::thread::spawn .然而，后一个问题需要一个不安全的解决方案。但是，由于您知道索引是相互不相交的，因此在实践中没有数据竞争，您可以使用 UnsafeCell 向编译器断言不存在数据竞争。要对切片执行此操作，您可以使用以下实用程序:

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

此实用程序允许您转换独家切片 &mut [T]成一个可以共享但仍用于突变的切片。当然，这意味着写入它可能会导致数据竞争，如果多个线程在没有同步的情况下写入同一个索引。因此 write方法是不安全的，如果违反此假设将导致 UB UnsafeSlice实用程序仍将保证您在使用它时没有释放后使用或越界错误。仅使用 UnsafeSlice 关闭对竞争条件的验证.
要查看构造函数中的转换是否合理，请参阅 Cell::from_mut 中的安全注释。和 Cell::as_slice_of_cells方法。