Granite

Generic backing storage framework for building arena-allocated data structures.

Overview

Unlike many other languages, Rust is not very friendly to naive implementations of data structures based on smart pointers. The most you can represent with Rc/Arc is a directed acyclic graph (DAG), and the second word in that somewhat cryptic abbreviation hints why: you'll be running into cycles between the pointers, which will prevent the whole structure from ever being dropped, leaking both the memory for the nodes and their user-defined contents. The only way you can solve this is by using garbage collection, or by dropping every single element manually, while keeping track of the collection's not-yet-dropped nodes, which would require an elaborate algorithm and runtime overhead to match.

Also, performing separate memory allocations for every single element is horribly slow and unfriendly to cache locality, not unlike the universally despised LinkedList. So much for the zero-cost abstraction that Rust strives to achieve.

Enter arena-allocated data structures: a way to have data structures backed by Vec, which provides excellent cache locality and performs bulk allocations.

Unlike smart pointer data structures, arena allocated data structures do not store any pointers. Instead, they store keys. A key is an identifier of an element within the backing storage, unique in the scope of one instance of the backing storage. Keys may overlap between multiple storages and between an element which existed at some point but has been removed, but they may not overlap among elements coexisting in one point of time in one collection.

Public dependencies

• tinyvec — ^1.2
• arrayvec — ^0.5
• smallvec — ^1.4
• slab — ^0.4
• slotmap — ^0.4

PRs are welcome from those interested in those version numbers being modified.

Feature flags

• alloc (enabled by default) — enables support for Vec and VecDeque from the standard library, while keeping the crate no_std. Requires a functional global allocator, though only at runtime and not at compile time.
• tinyvec — enables support for ArrayVec, SliceVec and TinyVec from the tinyvec crate, often preferred over arrayvec and smallvec.
• arrayvec — enables support for ArrayVec. You probably should use tinyvec instead.
• smallvec — enables support for SmallVec. You probably should use tinyvec instead.
• slab — enables support for Slab.
• slotmap — enables support for SlotMap, HopSlotMap and DenseSlotMap. Slab will likely be faster because it's not versioned; this feature is largely here for compatibility.
• union_optimizations — forwarded to Granite, adds some layout optimizations by using untagged unions, decreasing memory usage in SparseStorage. Requires a nightly compiler (see tracking issue for RFC 2514) and thus is disabled by default.