nexus-collections

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

Why This Crate?

Node-based data structures (linked lists, heaps, trees) 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);

RbTree — Red-Black Tree Sorted Map

Deterministic O(log n) sorted map with at most 2 rotations per insert, 3 per delete. Best for entry-heavy and pop-heavy workloads (order books, timer wheels).

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

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

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

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

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

BTree — B-Tree Sorted Map

Cache-friendly sorted map with tunable branching factor. Best for read-heavy lookups, existence checking, high-churn streaming data, and range scans.

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

// Custom branching factor: btree_allocator!(u64, String, bounded, 12)

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

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

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

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. Sorted map benchmarks use batched seq! unrolled timing (100 ops per rdtsc pair) to amortize serialization overhead. Same PRNG seed across all benchmarks. See BENCHMARKS.md for individual tables with all percentiles.

List (p50 cycles)

Heap (p50 cycles)

Sorted Maps — p50 (cycles, @10k population)

Sorted Maps — p999 Tail Latency (cycles, @10k population)

Both nexus trees beat std::collections::BTreeMap across the board. The slab allocator eliminates global allocator contention and gives predictable cache behavior. The advantage is most visible in tail latency — std's p999 on growing insert is 3736 cycles (global allocator on node splits) vs nexus BTree's 758.

When to Choose Which

RbTree: Entry-heavy workloads (order books), pop-heavy workloads (timer wheels), anything where the pattern is check-then-insert via the entry API.

BTree: Read-heavy lookups, existence checking (contains_key), high-churn streaming data, range scans. Tunable branching factor via const generic B.

License

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