HiSlab

A high-performance slab allocator using hierarchical bitmaps for O(1) slot allocation and deallocation. Backed by anonymous mmap with demand paging.

Features

• O(1) insert and remove — hierarchical bitmap finds a free slot in constant time regardless of fragmentation
• mmap-backed storage — virtual memory reserved upfront, physical pages committed on demand; pointer never moves
• Huge page support — initial capacity pre-faulted with MADV_POPULATE_WRITE | MADV_HUGEPAGE
• Stable u32 indices — inserted elements keep their index until removed
• SIMD optimized — bitmap operations use AVX-512, AVX2, NEON, or scalar at compile time
• Tagging — TaggedHiSlab maintains a second bitmap to track a subset of elements
• Buffer pool — BufferSlab<N> for fixed-size raw byte buffers with RAII guards
• Random sampling — uniform random selection over occupied/tagged slots (feature rand)

Crates

[dependencies]
hislab = "0.2"

# Optional: random sampling
hislab = { version = "0.2", features = ["rand"] }

HiSlab

use hislab::HiSlab;

// Reserve virtual space for 65 536 slots, pre-fault the first 1 024
let mut slab = HiSlab::<i32>::new(1024, 65536).unwrap();

// insert() returns a stable u32 index
let idx = slab.insert(42);
assert_eq!(slab[idx], 42);

// remove() returns the value
let val = slab.remove(idx);
assert_eq!(val, Some(42));
assert!(slab.get(idx).is_none());

// Freed slots are reused
let idx2 = slab.insert(99);
assert_eq!(idx2, idx);

new(initial_capacity, virtual_capacity)

Both are u32. initial_capacity must be <= virtual_capacity.

Core methods

Iteration

// Shared reference
for (idx, val) in &slab {
    println!("{idx}: {val}");
}

// Mutable reference
for (idx, val) in &mut slab {
    *val += 1;
}

// Consuming (moves values out)
for (idx, val) in slab {
    println!("{idx}: {val}");
}

// Callback — avoids iterator overhead
slab.for_each_occupied(|idx, val| {
    println!("{idx}: {val}");
});

Unsafe fast access

// Caller guarantees the slot is occupied
unsafe {
    let val = slab.get_unchecked(idx);
    let val_mut = slab.get_unchecked_mut(idx);
}

TaggedHiSlab

TaggedHiSlab<T> wraps a HiSlab and maintains a second bitmap to mark a subset of elements as tagged. All base slab operations are identical.

use hislab::TaggedHiSlab;

let mut slab = TaggedHiSlab::<u32>::new(0, 1024).unwrap();

let a = slab.insert(1);       // not tagged
let b = slab.insert_tagged(2); // inserted and tagged in one call

slab.tag(a);         // tag an existing element (returns false if already tagged)
slab.untag(b);       // remove tag
assert!(slab.is_tagged(a));
assert!(!slab.is_tagged(b));

Tagging methods

Iterating tagged elements

// Callback — fastest
slab.for_each_tagged(|idx, val| { /* … */ });

// Iterator
for (idx, val) in slab.iter_tagged() { /* … */ }
for (idx, val) in slab.iter_tagged_mut() { /* … */ }

Bulk operations on tagged elements

// Remove tagged elements that fail the predicate
slab.retain_tagged(|idx, val| val.ttl > 0);

// Untag (but keep in slab) elements that fail the predicate
slab.retain_tag(|idx, val| val.is_active());

BufferSlab

BufferSlab<N> is a pool of fixed-size raw byte buffers. Slots are managed through RAII AutoGuards that free automatically on drop.

use hislab::buffer_slab::BufferSlab;

// Pre-fault 4 slots, reserve space for 128
let pool = BufferSlab::<4096>::new(4, 128).unwrap();

let mut g0 = pool.allocate();          // panics if pool is full
let g1 = pool.try_allocate().unwrap(); // returns None if pool is full

g0.as_slice_mut().fill(0xAB);
assert_eq!(g0.index(), 0);
assert_eq!(g1.index(), 1);

// Drop releases the slot back to the pool
drop(g0);
drop(g1);

AutoGuard API

Multiple guards can coexist simultaneously. BufferSlab is !Send + !Sync.

Random sampling (feature rand)

Available on both HiSlab and TaggedHiSlab.

use hislab::HiSlab;
use rand::thread_rng;

let mut rng = thread_rng();

// Pick one random occupied element
if let Some((idx, val)) = slab.random_occupied(&mut rng) { /* … */ }
if let Some((idx, val)) = slab.random_occupied_mut(&mut rng) { /* … */ }

// Pick N elements with possible duplicates
let sample = slab.random_occupied_many(&mut rng, 10);

// Pick N unique elements
let unique = slab.random_occupied_unique(&mut rng, 5);

// Count occupied slots
let n = slab.count_occupied();

TaggedHiSlab adds the same methods for the tagged subset: random_tagged, random_tagged_mut, random_tagged_many, random_tagged_unique, count_tagged.

Architecture

HiSlab uses a 4-level hierarchical bitmap:

lvl4 (u8)       → 8 bits summarize lvl3
lvl3 (BitBlock) → 512 bits summarize lvl2
lvl2 (BitBlock) → 512 bits summarize lvl1
lvl1 (BitBlock) → 512 bits track actual data slots

Each BitBlock is 512 bits (8 × u64), aligned to 64 bytes. Insert descends the tree to find a free slot; fullness/emptiness propagates upward.

SIMD support

Bitmap operations select exactly one implementation path at compile time — no runtime dispatch overhead.

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE)
• MIT license (LICENSE-MIT)

at your option.