pub struct AppendVec<T> { /* private fields */ }Expand description
A concurrent append-only Vec-like container.
Unlike Vec, this collection provides the following features.
- Reads return stable references, i.e. a reference to an item stays valid even when more values are appended to the collection.
- Lock-free reads can happen while a write operation (append) is on-going.
- However, multiple writes don’t happen concurrently: under the hood a write
lock is held during each
push()operation.
This makes this collection useful for scenarios such as a caching system,
where a large number of readers are continuously reading items while new
items are occasionally added to the collection. In this cases, wrapping a
regular Vec inside a RwLock would be less
efficient, as readers and writers would block each other every time a value
is added to the collection.
The drawbacks are that this collection offers only a simple API (only
appends and indexing are supported), it takes a bit more space in memory
than Vec (a few hundred bytes of fixed overhead), and each operation
uses atomics (which involves some hardware synchronization).
Under the hood, this is implemented as a series of buckets with power-of-two
sizes. Each bucket is allocated only when needed (i.e. when all the previous
buckets are full). This ensures that the memory overhead of this collection
remains bounded by a factor two, similarly to a regular Vec.
Because the values are spread over multiple buckets in memory, it’s not possible to obtain a slice to a sequence of items.
This container is Send and Sync if and only if T is both Send
and Sync. Indeed, sharing or sending an AppendVec allows retrieving
const references to T and moving values of type T across threads (where
the value is pushed vs. where it is dropped).
Implementations§
Source§impl<T> AppendVec<T>
impl<T> AppendVec<T>
Sourcepub fn new() -> Self
pub fn new() -> Self
Creates a new, empty collection.
use appendvec::AppendVec;
let mut container = AppendVec::new();
let index = container.push_mut(42);
assert_eq!(container[index], 42);Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Creates a new, empty collection, pre-allocating space for at least
capacity items.
§Panics
This function panics if the capacity exceeds the maximum allocation size
for a collection of items of type T.
use appendvec::AppendVec;
let mut container = AppendVec::with_capacity(42);
for i in 0..42 {
let index = container.push_mut(i);
assert_eq!(container[index], i);
}Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the length of this collection.
Given that writes can happen concurrently, beware of TOCTOU bugs! The value returned here is only a lower-bound of the collection size.
To know the index of an added item, use the return value of the
push() function.
use appendvec::AppendVec;
use std::thread;
let container = AppendVec::with_capacity(42);
thread::scope(|s| {
s.spawn(|| {
for i in 0..42 {
let index = container.push(i);
// There is only one writer thread.
assert_eq!(index, i);
}
});
s.spawn(|| {
loop {
let l = container.len();
if l != 0 {
// The unique writer thread pushes values in order.
assert_eq!(container[l - 1], l - 1);
}
if l == 42 {
break;
}
}
});
});Sourcepub unsafe fn len_unsynchronized(&self) -> usize
pub unsafe fn len_unsynchronized(&self) -> usize
Returns an estimate of the length of this collection, without performing
any synchronization (i.e. using Relaxed
ordering).
§Safety
Passing the result of this function (minus one) to
get_unchecked() without any other form of
synchronization is unsound, as the write(s) of the appended value(s)
cannot be assumed to have happened before the increment of the length
observed here.
If you don’t know what “happens
before” entails,
you should probably not use this function, and use the regular
len() function instead.
use appendvec::AppendVec;
use std::sync::Barrier;
use std::thread;
let container = AppendVec::with_capacity(42);
let barrier = Barrier::new(2);
thread::scope(|s| {
s.spawn(|| {
for i in 0..42 {
let index = container.push(i);
}
// Synchronizes all the writes with the reader thread.
barrier.wait();
});
s.spawn(|| {
// Wait for all values to be appended to the container, and synchronize.
barrier.wait();
// SAFETY: After the synchronization barrier, no more values are appended in the
// writer thread.
let len = unsafe { container.len_unsynchronized() };
for i in 0..len {
// SAFETY: The writer thread wrote until the container length before the
// synchronization barrier.
let value = unsafe { container.get_unchecked(i) };
assert_eq!(*value, i);
}
});
});Sourcepub fn push(&self, t: T) -> usize
pub fn push(&self, t: T) -> usize
Adds the given item to this collection and returns the index at which it was added.
Internally, a write lock is held during this function call, i.e. other writers must wait for this function to complete. However, readers are free to read items in the meantime.
Note that while this internally appends the item at the end of the
collection, and while a writer lock is internally held during the
operation, there is no guarantee that the returned index will remain
the last one (i.e. equal to self.len() - 1), as a concurrent write
may happen immediately afterwards. Beware of
TOCTOU
bugs!
See also push_mut(), which is more efficient if
you hold a mutable reference to this collection.
§Panics
This function panics if this collection has reached the maximum
allocation size for items of type T.
use appendvec::AppendVec;
// The container isn't mutable, we'll use concurrent interior mutability via the push()
// function.
let container = AppendVec::with_capacity(42);
for i in 0..42 {
let index = container.push(i);
assert_eq!(container[index], i);
}Sourcepub fn push_mut(&mut self, t: T) -> usize
pub fn push_mut(&mut self, t: T) -> usize
Adds the given item to this collection and returns the index at which it was added.
Contrary to push(), no write lock is held internally
because this function already takes an exclusive mutable reference
to this collection.
§Panics
This function panics if this collection has reached the maximum
allocation size for items of type T.
use appendvec::AppendVec;
let mut container = AppendVec::with_capacity(42);
for i in 0..42 {
let index = container.push_mut(i);
assert_eq!(container[index], i);
}Sourcepub unsafe fn get_unchecked(&self, index: usize) -> &T
pub unsafe fn get_unchecked(&self, index: usize) -> &T
Obtain a reference to the item at the given index without performing bound checks.
§Safety
The passed index must be lower than the size of the collection, i.e. a
call to push() that returned index must have
happened before this function call.
If you don’t know what “happens before” entails, you should probably not use this function, and use the regular indexing syntax instead.
use appendvec::AppendVec;
use std::sync::Barrier;
use std::thread;
let container = AppendVec::with_capacity(42);
let barrier = Barrier::new(2);
thread::scope(|s| {
s.spawn(|| {
for i in 0..42 {
let index = container.push(i);
}
// Synchronizes all the writes with the reader thread.
barrier.wait();
});
s.spawn(|| {
// Wait for all values to be appended to the container, and synchronize.
barrier.wait();
// SAFETY: After the synchronization barrier, no more values are appended in the
// writer thread.
let len = unsafe { container.len_unsynchronized() };
for i in 0..len {
// SAFETY: The writer thread wrote until the container length before the
// synchronization barrier.
let value = unsafe { container.get_unchecked(i) };
assert_eq!(*value, i);
}
});
});Sourcepub fn iter(&self) -> AppendVecIter<'_, T> ⓘ
pub fn iter(&self) -> AppendVecIter<'_, T> ⓘ
Obtain an iterator over this collection.
Note that once this iterator has been created, it will not iterate over items added afterwards, even on the same thread. This is to minimize the number of atomic operations.
use appendvec::AppendVec;
use std::thread;
let container = AppendVec::with_capacity(42);
thread::scope(|s| {
s.spawn(|| {
for i in 0..42 {
let index = container.push(i);
assert_eq!(index, i);
}
});
s.spawn(|| {
loop {
let it = container.iter();
let len = it.len();
for (i, value) in it.enumerate() {
assert_eq!(*value, i);
}
if len == 42 {
break;
}
}
});
});