Sometimes I found myself need to modify a Vec from multiple places, where I find it would be best if I can pop elements from a &Cell<Vec<T>>, then I begin to wonder what kind of operations are safe for a &Cell<Vec<T>>. For example, are these push and pop operations safe?
use std::cell::Cell;
use std::ptr;
fn cell_vec_push<T>(vec: &Cell<Vec<T>>, value: T) {
// See <https://doc.rust-lang.org/1.80.1/src/alloc/vec/mod.rs.html#1993>.
unsafe {
let vec = &mut *vec.as_ptr();
let len = vec.len();
// This may panic and calls the destructor of `value`.
vec.reserve(1);
ptr::write(vec.as_mut_ptr().add(len), value);
vec.set_len(len + 1);
}
}
fn cell_vec_pop<T>(vec: &Cell<Vec<T>>) -> Option<T> {
unsafe { (*vec.as_ptr()).pop() }
}
Note that these functions can be implemented without unsafe codes by taking the Vec out of Cell, modify it, then put it back:
/// Ensures original `Vec` is restored even if operation panics.
struct RestoreOnDrop<'a, T>(&'a Cell<Vec<T>>, Vec<T>);
impl<T> Drop for RestoreOnDrop<'_, T> {
fn drop(&mut self) {
mem::forget(self.0.replace(mem::take(&mut self.1)));
}
}
fn cell_vec_push_safe<T>(vec: &Cell<Vec<T>>, value: T) {
RestoreOnDrop(vec, vec.take()).1.push(value);
}
fn cell_vec_pop_safe<T>(vec: &Cell<Vec<T>>) -> Option<T> {
RestoreOnDrop(vec, vec.take()).1.pop()
}
But I think in this specific case, taking the Vec of the Cell may be unnecessary, and the compiler is not able to optimize the move around operations away. So I wrote those unsafe implementations at the beginning.
Of course there is always RefCell, but accessing it requires runtime check which might not be optimal.
If my unsafe implementations are safe, do you think it is reasonable to add these functions to the standard library?
If any one is interested, my use case is writing a graph traversal algorithm, click here to see a simplified version of it.
The original version:
use std::hint;
struct Node1 {
value: u32,
neighbors: Vec<usize>,
}
fn dfs_1(graph: &mut [Node1], node: usize) {
let value = graph[node].value;
while let Some(child) = graph[node].neighbors.pop() {
let child_value = graph[child].value;
dfs_1(graph, child);
// Do something with `value` and `child_value`.
hint::black_box((value, child_value));
}
}
If I can pop a Cell<Vec<T>> directly, the code above can be simplified to:
struct Node2 {
value: u32,
neighbors: Cell<Vec<usize>>,
}
fn dfs_2(graph: &[Node2], node: &Node2) {
while let Some(child) = cell_vec_pop(&node.neighbors) {
let child = &graph[child];
dfs_2(graph, child);
// Do something with `node.value` and `child.value`.
hint::black_box((node.value, child.value));
}
}
Which could avoid some bound checking overhead. Here is the comparison of generated assembly: https://godbolt.org/z/ErjYaKTha.
Here is a playground link for all the code above: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=83c255923ca33ac343cb332c21f5eaa9.