nexus-collections

High-performance, slab-backed collections for latency-critical systems.

Why This Crate?

Node-based data structures (linked lists, heaps, skip lists) offer operations that contiguous structures can't — O(1) unlink/re-link, stable handles to interior elements, and movement between collections without copying. The trade-off is normally heap fragmentation and allocator overhead on every node allocation.

This crate eliminates that trade-off by using nexus-slab — a SLUB-style slab allocator — as dedicated backing storage for all nodes. Nodes live in contiguous, type-homogeneous slabs rather than scattered across the global heap, giving you:

• Global allocator isolation — your hot path doesn't compete with logging, serialization, or background tasks for allocator resources
• LIFO cache locality — recently freed nodes are reused first, staying hot in L1
• Zero fragmentation — every slot is the same size, freed slots are immediately reusable
• Stable handles — RcSlot-based references that survive unlink, re-link, and movement between collections
• Bounded — fixed capacity, zero allocation after init, returns Full at capacity
• Unbounded — grows via chunks without copying

Collections

List — Doubly-Linked List

O(1) push/pop/unlink anywhere. RcSlot handles enable O(1) access by identity. Elements can move between lists without deallocation.

mod orders {
    nexus_collections::list_allocator!(Order, bounded);
}

orders::Allocator::builder().capacity(1000).build().unwrap();

let mut list = orders::List::new(orders::Allocator);
let handle = list.try_push_back(Order { id: 1, price: 100.0 }).unwrap();

// Access via handle
assert_eq!(handle.exclusive().price, 100.0);

// O(1) unlink and re-link
list.unlink(&handle);
list.link_back(&handle);

Heap — Pairing Heap

O(1) push, O(log n) pop, O(1) peek. RcSlot handles enable O(log n) removal of arbitrary elements by handle.

mod timers {
    nexus_collections::heap_allocator!(Timer, bounded);
}

timers::Allocator::builder().capacity(1000).build().unwrap();

let mut heap = timers::Heap::new(timers::Allocator);
let handle = heap.try_push(Timer { deadline: 42 }).unwrap();

// O(1) peek
assert_eq!(heap.peek().unwrap().data().deadline, 42);

// O(log n) unlink by handle
heap.unlink(&handle);

SkipList — Sorted Map

Probabilistic sorted map with O(log n) insert/lookup/remove. Internal allocation — user sees only keys and values.

mod levels {
    nexus_collections::skip_allocator!(u64, String, bounded);
}

levels::Allocator::builder().capacity(1000).build().unwrap();

let mut map = levels::SkipList::new(levels::Allocator);
map.try_insert(100, "hello".into()).unwrap();

assert_eq!(map.get(&100), Some(&"hello".into()));

// Sorted iteration
for (k, v) in map.iter() {
    println!("{k}: {v}");
}

// Entry API
map.entry(200).or_try_insert("world".into()).unwrap();

Allocator Macros

Each collection has a macro that generates a typed thread-local slab allocator. Invoke inside a module:

Bounded allocators have a fixed capacity. Insert operations return Result<_, Full<T>> when full.

Unbounded allocators grow as needed via chunk allocation.

Initialization

Allocators must be initialized before use:

// Bounded — set capacity
orders::Allocator::builder().capacity(1000).build().unwrap();

// Unbounded — optionally set chunk size (default 4096)
orders::Allocator::builder().chunk_size(512).build().unwrap();

Performance

Cycle-accurate latency, Intel Core Ultra 7 155H, pinned to physical core, turbo boost disabled. See BENCHMARKS.md for full results.

List (p50 cycles)

Heap (p50 cycles)

SkipList (p50 cycles, @10k population)

License

Licensed under either of Apache License, Version 2.0 or MIT License at your option.