Small Collections

High-performance collections optimized with Small Object Optimization (SOO).

small-collections provides a comprehensive suite of data structures—including Map, Set, Vec, Deque, String, LRU Cache, and more—that live entirely on the stack for small capacities and automatically "spill" to the heap when they grow larger. This drastically reduces memory allocator pressure (malloc/free) and improves cache locality.

🚀 Features

• Wide Collection Support: 12+ optimized collections including sequences, maps, sets, priority queues, and caches.
• Stack Allocation: Zero heap allocation while the collection size is ≤ N.
• Automatic Spilling: Seamlessly transitions to standard heap-allocated equivalents (HashMap, Vec, String, etc.) when capacity N is exceeded.
• Zero-Cost Move: Spilling moves data directly; no cloning required.
• Compile-Time Safety: Enforces strict size limits during the build process to prevent accidental stack overflows.
• Standard API: Implements standard traits (Debug, Display, FromIterator, Extend, Clone, Default, PartialEq, Hash) where applicable.

📦 Installation

Add this to your Cargo.toml:

[dependencies]
small-collections = "0.6.0"

Then in your code:

use small_collections::SmallMap;

⚙️ Optional Features

small-collections is modular. You can enable or disable groups of collections to minimize dependency overhead:

Heapless LRU Variants

For SmallLruCache, there are three heapless backends optimized for different capacity ranges:

Benchmarks: Which LRU to use?

Basic collections (SmallVec, SmallDeque, SmallMap, SmallBTreeMap, SmallString) are always available as they depend only on heapless and fnv.

📦 Dependencies & Acknowledgments

small-collections is built on the shoulders of giants. We use best-in-class crates for our storage and hashing backends:

• heapless: Provides the foundational fixed-capacity stack storage.
• hashbrown: Our primary heap-allocated map backend, utilizing the Raw Entry API for efficient spills.
• bitvec: Powers SmallBitVec with efficient bit-level manipulation.
• lru: Provides the LRU eviction logic for SmallLruCache.
• ordermap: Powers SmallOrderedMap for insertion-order preservation.
• fnv: A fast, non-cryptographic hasher used to ensure consistent state and performance between stack and heap transitions.

🛠 Usage

🏗️ Project Structure

The library is organized into specialized modules by collection type:

• maps/: Hash, BTree, and Ordered Maps.
• sets/: Hash, BTree, and Ordered Sets.
• vecs/: Vec, Deque, and BitVec.
• cache/: All LRU cache implementations and backends.
• utils/: Shared utilities like IndexType.

All collections are conveniently re-exported at the crate root.

📦 Collections Catalog

small-collections covers almost all standard library collection types, optimized for stack-first storage.

1. Sequences

use small_collections::{SmallVec, SmallDeque};

// SmallVec: Optimized branchless stack-based list
let mut v: SmallVec<i32, 4> = SmallVec::new();
v.push(10); // Stack access is neck-and-neck with std::vec::Vec

// SmallDeque: Efficient stack-based ring buffer
let mut d: SmallDeque<i32, 4> = SmallDeque::new();
d.push_front(1);
d.push_back(2);

2. Maps & Sets

We provide three varieties of associative collections depending on your ordering requirements:

use small_collections::{SmallMap, SmallBTreeMap, SmallOrderedMap};

// Hash-based (Fastest)
let mut hm: SmallMap<String, i32, 4> = SmallMap::new();

// B-Tree based (Sorted)
let mut bm: SmallBTreeMap<i32, &str, 4> = SmallBTreeMap::new();
bm.insert(2, "World");
bm.insert(1, "Hello"); // Will be sorted as [1, 2]

// Ordered (Insertion Order)
let mut om: SmallOrderedMap<i32, &str, 4> = SmallOrderedMap::new();
om.insert(2, "World");
om.insert(1, "Hello"); // Preserves order as [2, 1]

3. Specialized Collections

use small_collections::{SmallBinaryHeap, SmallLruCache, SmallBitVec};
use std::num::NonZeroUsize;

// Priority Queue
let mut heap: SmallBinaryHeap<i32, 4> = SmallBinaryHeap::new();
heap.push(10);
heap.push(20);
assert_eq!(heap.pop(), Some(20)); // Highest priority first

// LRU Cache (Defaults to BTree backend)
let mut cache: SmallLruCache<i32, i32, 8> = SmallLruCache::new(NonZeroUsize::new(2).unwrap());
cache.put(1, 10);
cache.put(2, 20);
cache.put(3, 30); // Evicts (1, 10) if capacity is reached on heap or stack limit N

// Compact Booleans
let mut bv: SmallBitVec<64> = SmallBitVec::new();
bv.push(true);
bv.push(false);

4. Utilities

use small_collections::SmallString;

let mut s: SmallString<16> = SmallString::new();
s.push_str("Hello");
assert!(s.is_on_stack());

⚠️ Safety & Constraints

To ensure high performance and prevent application crashes, this library enforces constraints at Compile Time.

1. Capacity Rules (heapless)

The generic constant N (stack capacity) must adhere to the underlying storage rules:

• For SmallMap / SmallSet:
  • N must be a power of two (e.g., 2, 4, 8, 16...).
  • N must be greater than 1.
• For SmallString:
  • N can be any non-zero size (e.g., 20, 80, 100).
  • Powers of two are recommended for alignment, but not required.

2. Stack Size Guard

Since these collections store data inline, a large N (or large Value type in Maps) can easily exceed the thread stack size (causing a Segmentation Fault).

To prevent this, new() includes a Compile-Time Assertion.

• Limit: The total size of the struct must not exceed 16 KB.
• Behavior: If your collection is too large, cargo build will fail.

How to fix a build failure:

If you see an error like "SmallMap is too large", you have two options:

1. Reduce N: If you don't need that many items on the stack, reduce the capacity.
2. Box the Value: For SmallMap, wrap the value in a Box<V>. This keeps the map structure small on the stack.

Size Recommendation

⚡ Performance Benchmarks

small-collections is designed to be neck-and-neck with pure stack-allocated collections while providing the safety net of a heap spill.

1. Standard Comparison (Small N=8)

Measured using Criterion on very small workloads to show the base gain over heap-allocated defaults.

2. Heapless vs Small vs Std Comparison (N=16)

Benchmarked to measure the overhead of the "Small" tagged-union dispatch vs pure "Heapless" stack storage.

3. LRU Backend Comparison (Linear vs BTree vs Map)

For smaller capacities, the choice of backend significantly impacts performance.

Benchmarks measured using Criterion. Small collections incur a negligible dispatch overhead but offer a seamless transition to the heap once capacity is reached.

🏗️ Design Rationale: Custom Stack Backends

While we leverage the heapless crate for foundational storage, small-collections includes several custom-built stack-allocated engines. This was necessary to fill gaps in the ecosystem and support our spill-to-heap protocol:

1. HeaplessBTreeMap: Upstream heapless primarily provides LinearMap (O(N)) and IndexMap. We required a true B-Tree implementation to support sorted associative storage with $O(\log N)$ performance.
2. HeaplessLruCache: Map-based LRU optimized for larger stack capacities. It uses a Struct-of-Arrays (SoA) layout for cache efficiency and a singly-linked free-list embedded within the next-pointer array to achieve O(1) allocation with zero extra memory overhead.
3. HeaplessBitVec: Standard stack bit-arrays (like those in bitvec::BitArray) often have fixed lengths or lack the specific ownership-transfer APIs needed to "spill" bit-data into a heap-allocated bitvec::BitVec without cloning.
4. HeaplessOrderedMap: Necessary to maintain strict insertion-order preservation while providing the "take ownership" hooks used by SmallOrderedMap during migration.
5. HeaplessLinearLruCache: Optimized for tiny working sets ($N < 16$). Highly efficient linear scanning that eliminates hashing latency and minimizes stack metadata.
6. HeaplessBTreeLruCache: The default backend for SmallLruCache. Bridges the gap with $O(\log N)$ binary search on a sorted index of physical slot IDs, providing stable performance without data shifting.
7. SmallDeque: While heapless provides a Deque, ours uses a custom ring-buffer implementation to allow index management (head/len) to exist outside the storage union. This ensures backend independence and enables order-preserving, zero-copy spills to the heap.

Why use small-collections?

For bimodal workloads—where most collections are small but some grow large—the elimination of heap allocation and deallocation provides a significant speedup (up to 5.4x). While SmallVec and SmallDeque incur a minor overhead for safety/state management, the associative collections deliver massive wins.

🏮 Design Philosophy

small-collections adheres to three core principles:

1. Hybrid Storage: We don't reinvent the wheel. We combine the safety of heapless stack arrays with the battle-tested performance of hashbrown, std, and ordermap for the heap path.
2. Transparent Interoperability: Through the Any* traits (e.g., AnyMap, AnyString), you can write generic code that handles both Small* and standard library types without performance penalties.
3. Fail-Fast Safety: We use compile-time constants and assertions to ensure that stack usage is explicit and guarded against overflows.

⚡ Performance Architecture

This library is designed for scenarios with a bimodal distribution of sizes—where most collections are small, but some can grow large.

1. The Stack State

• Storage:
• Sequence: Branchless SmallVec, SmallDeque
• Map/Set: heapless::IndexMap
• String: heapless::String
• Allocator: None. Uses inline stack memory.
• Hashing: FNV (Fowler–Noll–Vo). Non-cryptographic but extremely fast for small keys, avoiding the startup overhead of SipHash.

2. The Heap State

• Storage:
  • Map/Set: hashbrown::HashMap
  • String: std::string::String
• Allocator: Standard System Allocator.
• Hashing: FNV (maintained for consistency in Maps/Sets).

3. The Spill Mechanism

When a collection transitions from Stack to Heap, it performs a bitwise copy of the stack memory to "steal" ownership of the items. It then moves them into the heap structure. This avoids:

1. Cloning keys/values (Standard moves).
2. Double-hashing (Hashes are calculated once during migration).

✅ Testing & Code Coverage

small-collections places a strong emphasis on reliability. The entire crate is backed by a comprehensive test suite that achieves over 90% code coverage.

Testing covers all critical paths, including:

• Stack-to-Heap Transitions: Rigorously verified to ensure data integrity during spills (zero-cost moves) across all collections.
• LRU Cache Parity: Extensive tests ensure our heapless cache variants provide identical behavior and trait interoperability (AnyLruCache) to the standard lru crate.
• Object-Safe Traits: Custom traits like AnyMap, AnyVec, and AnyString are heavily tested for seamless dispatch between stack-allocated arrays and heap-allocated structs.
• Edge Cases: Out-of-bounds access, hash collisions, dynamic capacity reservations, and compile-time panic branches (#[should_panic]) are all thoroughly exercised.
• Memory Safety: Extensively checked for memory leaks and undefined behavior via Valgrind and Miri pipelines natively included in the Makefile.

You can verify the test suite and coverage locally using cargo tarpaulin:

cargo test
cargo tarpaulin --out Stdout --skip-clean --engine ptrace

🤝 Contributing

Contributions are welcome! Please ensure that any PRs include tests covering both the "Stack" state and the "Heap" state to ensure the spill logic is exercised correctly.

📄 License

MIT License