slicedvec

This is a rust crate that provides a type SlicedVec<T> that emulates aspects of Vec<Vec<T>> using a single Vec<T> for storage. The main purpose is to support the swap-remove idiom. When repeatedly creating and dropping many objects, the swap-remove idiom can be used to eliminate most allocations. This does not work however if the stored objects themselves allocate, as happens with Vec<Vec<T>>.

lib.rs:

Two structs are provided: SlicedVec and SlicedSlab. The target use-case is a need to repeatedly construct and drop short, run-time sized sequences of floats. Using a Vec<Vec<T>> may cause allocator thrashing, unless a pool or some other mechanism is used. SlicedVec stores a collection of run-time sized slices in a single vector. It emulates a Vec<&[T]> but owns and manages its own storage. Methods are available for constant-time, non-order-preserving insertion and deletion. Repeated generations of push and swap_remove (or swap_truncate) will not allocate because the capacity of the storage will grow as needed.

SlicedSlab is built on SlicedVec and returns stable keys to allocated sequences of values. When a sequence is inserted into the slab, it returns a key. The sequence can be retrieved or removed from the slab using the key. Removal simply marks the slot as unoccupied and it will be overwritten by subsequent inserts without allocation. Note that dropping elements of the removed sequence is deferred until an insert into that location. Methods are provided for re-keying and compacting the slab if it becomes too sparse. Open slots are stored in a BTreeSet, so most operations have complexity in the logarithm of the number of open slots. In most cases, the open slot set will be very small and entirely sit in cache. If it grows excessively large, compaction is needed to improve performance. The advantage of always inserting into the lowest-rank available slot outweighs the small cost of the BTreeSet as it reduces fragmentation.

Example

use rand::{rngs::SmallRng, Rng, SeedableRng};
use slicedvec::SlicedVec;
let mut rng = SmallRng::from_entropy();
let mut x1 = SlicedVec::with_capacity(1000, 20);
x1.push_vec(
    std::iter::repeat_with(|| rng.gen())
    .take(20 * 1000)
    .collect::<Vec<_>>(),
);
let x1_insert: Vec<Vec<usize>> =
    std::iter::repeat_with(|| std::iter::repeat_with(|| rng.gen()).take(20).collect())
        .take(500)
        .collect();
for i in 0..500 { x1.swap_truncate(i) }
for i in 0..500 { x1.push(&x1_insert[i]) }