Motivation
Rust provides a type for shared mutable memory ranges: &[Cell<T>]
.
A &[Cell<T>]
can be constructed from a &mut [T]
via Cell::from_mut(x).as_slice_of_cells()
.
While slices of Cell
are !Sync
, they allow for infallible shared mutation at very low cost.
However, there's a gap in functionality in Rust for operations on slices of cells.
There's no copy_from_slice
that works with cells, and ptr::copy
is unsafe to use.
While dst.iter().zip(src).for_each(|(d, s)| d.set(s.get()))
can copy from one slice to another,
it optimizes poorly and has worse semantics than a safe ptr::copy
.
There's also an API hole in core::ptr
: there's no possibly-aliasing swap for dynamic sizes.
ptr::copy
accepts possibly-aliasing memory and a dynamic size.
ptr::copy_nonoverlapping
is its non-aliasing equivalent.
ptr::swap_nonoverlapping
takes two pointers and a dynamic size.
In contrast, ptr::swap
is more like mem::swap
, because it only takes x
and y
to swap, and no count: usize
.
As far as I can tell, this is because the ptr::swap
implementation has O(N) memory complexity, and so directly adapting it for a dynamic-size aliasing
swap would require dynamic allocation.
However, this can be resolved by using a O(1) space algorithm.
Proposal
Add these functions to the standard library:
// In core::ptr
// Same safety docs and semantics as ptr::swap
#[unstable(feature = "ptr_swap_many")]
pub unsafe fn swap_many<T>(x: *mut T, y: *mut T, count: usize);
// In core::slice
impl<T> [T] {
// Does a `ptr::copy_nonoverlapping` since the slices cannot alias.
#[unstable(feature = "copy_cells")]
pub fn copy_from_cells(&mut self, src: &[Cell<T>]) where T: Copy;
// Does a `ptr::swap_nonoverlapping` since the slices cannot alias.
#[unstable(feature = "swap_cells")]
pub fn swap_with_cells(&mut self, other: &[Cell<T>]);
}
// Note these methods all accept `&self`: they manipulate shared mutable memory.
impl<T> [Cell<T>] {
// Uses `ptr::copy_nonoverlapping`, but if Rust ever changes to allow
// `UnsafeCell` in `Copy` types, then this can adapt to use `ptr::copy`
// when `T` contains `UnsafeCell`.
#[unstable(feature = "copy_cells")]
pub fn copy_to_cells_from_slice(&self, src: &[T]) where T: Copy;
// Does a `ptr::copy` since the slices may alias.
#[unstable(feature = "copy_cells")]
pub fn copy_to_cells_from_cells(&self, src: &[Cell<T>]) where T: Copy;
// Does a `ptr::swap_many` since the slices may alias.
// OLD: If `self` aliases `other`, prioritize memory in `self`.
// NEW: If `self` aliases other, panic. This is the behavior of `Cell::swap`.
#[unstable(feature = "swap_cells")]
pub fn swap_cells_with_cells(&self, other: &[Cell<T>]);
// `fn swap_cells_with_slice(&self, other: &mut [T])` is unneeded:
// write `other.swap_with_cells(self)` instead. Argument order
// is irrelevant since the slices cannot alias.
}
Naming
The cell methods above aim to balance stdlib consistency and brevity in their naming.
They specify the destination in the function name before the source, since that is
the method argument order.
They replace the term "slice of cells" with just "cells" for brevity since the context
involves slices, unlike Cell::as_slice_of_cells
.
An alternative naming scheme could keep the term at the cost of frustratingly long names (and even these keep to_cells
):
fn copy_from_slice_of_cells(&mut self, src: &[Cell<T>])
fn copy_to_cells_from_slice(&self, src: &[T]) where T: Copy
fn copy_to_cells_from_slice_of_cells(&self, src: &[Cell<T>]) where T: Copy
fn swap_with_slice_of_cells(&mut self, other: &[Cell<T>])
fn swap_cells_with_slice_of_cells(&self, other: &[Cell<T>])