6 stable releases
|1.1.1||Apr 26, 2021|
|1.1.0||Apr 25, 2021|
|1.0.3||Nov 5, 2020|
|1.0.1||Nov 4, 2020|
#1199 in Data structures
30 downloads per month
Used in charcoal
Generic backing storage framework for building arena-allocated data structures.
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
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.
PRs are welcome from those interested in those version numbers being modified.
alloc(enabled by default) — enables support for
VecDequefrom 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
tinyveccrate, often preferred over
arrayvec— enables support for
ArrayVec. You probably should use
smallvec— enables support for
SmallVec. You probably should use
slab— enables support for
slotmap— enables support for
Slabwill 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.