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 |
0.0.0 |
|
#770 in Data structures
Used in charcoal
105KB
2K
SLoC
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 forVec
andVecDeque
from the standard library, while keeping the crateno_std
. Requires a functional global allocator, though only at runtime and not at compile time.tinyvec
— enables support forArrayVec
,SliceVec
andTinyVec
from thetinyvec
crate, often preferred overarrayvec
andsmallvec
.arrayvec
— enables support forArrayVec
. You probably should usetinyvec
instead.smallvec
— enables support forSmallVec
. You probably should usetinyvec
instead.slab
— enables support forSlab
.slotmap
— enables support forSlotMap
,HopSlotMap
andDenseSlotMap
.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 inSparseStorage
. Requires a nightly compiler (see tracking issue for RFC 2514) and thus is disabled by default.
Dependencies
~180KB