我正在实施Conway的生活游戏,自学Rust . 我们的想法是首先实现单线程版本,尽可能地优化它,然后对多线程版本执行相同的操作 .
我想实现一种替代数据布局,我认为它可能更适合缓存 . 我们的想法是在一个向量中将每个点上的每个点的两个单元的状态存储在存储器中,一个单元用于读取当前代的状态,一个单元用于写入下一代的状态,交替访问模式为每一代的计算(可以在编译时确定) .
基本数据结构如下:
#[repr(u8)]
pub enum CellStatus {
DEAD,
ALIVE,
}
/** 2 bytes */
pub struct CellRW(CellStatus, CellStatus);
pub struct TupleBoard {
width: usize,
height: usize,
cells: Vec<CellRW>,
}
/** used to keep track of current pos with iterator e.g. */
pub struct BoardPos {
x_pos: usize,
y_pos: usize,
offset: usize,
}
pub struct BoardEvo {
board: TupleBoard,
}
导致我麻烦的功能:
impl BoardEvo {
fn evolve_step<T: RWSelector>(&mut self) {
for (pos, cell) in self.board.iter_mut() {
//pos: BoardPos, cell: &mut CellRW
let read: &CellStatus = T::read(cell); //chooses the right tuple half for the current evolution step
let write: &mut CellStatus = T::write(cell);
let alive_count = pos.neighbours::<T>(&self.board).iter() //<- can't borrow self.board again!
.filter(|&&status| status == CellStatus::ALIVE)
.count();
*write = CellStatus::evolve(*read, alive_count);
}
}
}
impl BoardPos {
/* ... */
pub fn neighbours<T: RWSelector>(&self, board: &BoardTuple) -> [CellStatus; 8] {
/* ... */
}
}
特征 RWSelector
具有用于读取和写入单元格元组的静态函数( CellRW
) . 它是为两个零大小的类型 L
和 R
实现的,主要是避免为不同的访问模式编写不同方法的一种方法 .
iter_mut()
方法返回一个 BoardIter
结构,它是一个包含单元格向量的可变切片迭代器的包装器,因此具有 &mut CellRW
作为 Item
类型 . 它也知道当前的 BoardPos
(x和y坐标,偏移量) .
我以为我会迭代所有单元格元组,跟踪坐标,计算每个(读取)单元格的活动邻居数量(我需要知道这个的坐标/偏移),计算下一代的单元格状态和写给元组的另一半 .
当然,最后,编译器向我展示了我的设计中的致命缺陷,因为我在 iter_mut()
方法中可变地借用 self.board
然后尝试再次借用它来获取读取单元的所有邻居 .
到目前为止,我还没能为这个问题找到一个好的解决方案 . 我确实设法通过使所有引用不可变,然后使用 UnsafeCell
将写入单元格的不可变引用转换为可变引用来实现它 . 然后,我通过 UnsafeCell
写入对元组写作部分的名义上不可变的引用 . 然而,这并没有让我觉得这是一个合理的设计,我怀疑在尝试并行化时,我可能会遇到这个问题 .
有没有办法实现我在安全/惯用Rust中提出的数据布局,或者这实际上是你实际上必须使用技巧来规避Rust的别名/借用限制的情况?
此外,作为一个更广泛的问题,是否有一个可识别的问题模式需要你规避Rust的借款限制?
1 回答
在以下情况下需要:
借用检查器不够先进,无法确定您的使用是否安全
您不希望(或不能)以不同的模式编写代码
作为具体案例,编译器无法判断这是否安全:
编译器不知道切片的
IndexMut
的实现在此编译时是做什么的(这是一个深思熟虑的设计选择) . 尽管如此,无论index参数如何,数组总是返回完全相同的引用 . 我们可以告诉这个代码是安全的,但是编译器不允许它 .您可以用对编译器显然安全的方式重写它:
这是怎么做到的? split_at_mut performs a runtime check以确保它实际上是安全的:
有关借用检查程序尚未进展的示例,请参阅What are non-lexical lifetimes? .
如果您知道引用不重叠,那么您可以选择使用不安全的代码来表达它 . 但是,这意味着您还要选择承担维护Rust的所有不变量并避免undefined behavior的责任 .
好消息是,这个沉重的负担是每个C和C程序员必须(或至少应该)拥有的东西 . 至少在Rust中,你可以让编译器处理99%的情况 .
在许多情况下,有像Cell和RefCell这样的工具允许内部变异 . 在其他情况下,您可以重写算法以利用值为
Copy
类型的值 . 在其他情况下,您可以在较短的时间段内将索引用于切片 . 在其他情况下,您可以使用多阶段算法 .如果您确实需要使用
unsafe
代码,那么请尽量将其隐藏在一个小区域中并公开安全接口 .最重要的是,之前(很多次)已经提出了许多常见问题:
How to iterate over mutable elements inside another mutable iteration over the same elements?
Mutating an item inside of nested loops
How can a nested loop with mutations on a HashMap be achieved in Rust?
What's the Rust way to modify a structure within nested loops?
Nesting an iterator's loops