id-slab 0.1.0

Dense Vec<Option<T>> storage for externally assigned integer ids.
docs.rs failed to build id-slab-0.1.0
Please check the build logs for more information.
See Builds for ideas on how to fix a failed build, or Metadata for how to configure docs.rs builds.
If you believe this is docs.rs' fault, open an issue.

id-slab

Stores values in Vec<Option<T>> and uses an external id as the slot index.

Use it when these conditions hold:

  • The key is a small Copy id.
  • The key maps to a mostly dense integer index.
  • The caller, not the collection, assigns ids.
  • Iteration must stay in ascending id order.

Do not use it as a general HashMap replacement. Sparse ids waste memory, and removed ids leave empty slots until you compact or rebuild the slab.

Example

use id_slab::{IdSlab, SlabKey};

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct VertexId(u32);

impl SlabKey for VertexId {
    fn index(self) -> usize {
        self.0 as usize
    }

    fn from_index(index: usize) -> Self {
        VertexId(index as u32)
    }
}

let mut vertices = IdSlab::new();
vertices.insert(VertexId(2), [1.0, 2.0, 3.0]);

assert_eq!(vertices.get(VertexId(2)), Some(&[1.0, 2.0, 3.0]));
assert_eq!(vertices.keys().collect::<Vec<_>>(), vec![VertexId(2)]);

Performance Shape

This crate targets one access pattern: externally assigned dense integer ids. Lookup is slots[id], so it avoids hashing, probing, and tree traversal.

The source benchmark used mesh-element-sized values and 1,000,000 elements. Lower is better.

storage build iterate random lookup lookup vs BTreeMap
id_slab::IdSlab 25 ms 2.8 ms 9.6 ms 29x
slotmap::DenseSlotMap 57 ms 2.6 ms 15.5 ms 18x
slotmap::SlotMap 62 ms 3.2 ms 14.8 ms 19x
ahash::HashMap 262 ms 7.7 ms 23 ms 12x
BTreeMap 80 ms 5.0 ms 278 ms 1x

Tradeoffs

id-slab stores no key beside the value. Iterators rebuild each key from the slot index, so iter() yields (K, &V), not (&K, &V).

Deletion leaves an empty slot. This behavior keeps existing ids stable, but memory use follows the highest inserted index. If a workload creates many holes, rebuild the slab with a remap table or use a collection with key reuse.

id-slab does not protect against stale keys. If stale-key detection matters, use a generational slot map.

Features

The crate has no default dependencies. Enable format support only when you need it.

  • serde: serializes the slab as a live id -> value map.
  • rkyv: archives the internal slot representation.
  • facet: derives Facet for runtime type reflection.

The crate supports no_std with alloc. It uses alloc::vec::Vec for storage. It does not support allocator-free operation, because insert() grows the slot storage when the key index is outside the current capacity.

License

Licensed under either of

at your option.