Expand description
Cache-friendly arena allocation for stack graph data.
A stack graph is composed of instances of many different data types, and to store the graph structure itself, we need cyclic or self-referential data types. The typical way to achieve this in Rust is to use arena allocation, where all of the instances of a particular type are stored in a single vector. You then use indexes into this vector to store references to a data instance. Because indexes are just numbers, you don’t run afoul of borrow checker. And because all instances live together in a continguous region of memory, your data access patterns are very cache-friendly.
This module implements a simple arena allocation scheme for stack graphs. An
Arena<T> is an arena that holds all of the instances of type T for a stack
graph. A Handle<T> holds the index of a particular instance of T in its arena.
All of our stack graph data types then use handles to refer to other parts of the stack graph.
Note that our arena implementation does not support deletion! Any content that you add to a
StackGraph will live as long as the stack graph itself does. The entire region of memory
for each arena will be freed in a single operation when the stack graph is dropped.
Structs§
- Arena
- Manages the life cycle of instances of type
T. You can allocate new instances ofTfrom the arena. All of the instances managed by this arena will be dropped as a single operation when the arena itself is dropped. - Deque
- An arena-allocated deque.
- Handle
- A handle to an instance of type
Tthat was allocated from anArena. - Handle
Set - Contains a set of handles, encoded efficiently using a bit set.
- List
- An arena-allocated singly-linked list.
- Reversible
List - An arena-allocated list that can be reversed.
- Supplemental
Arena - A supplemental arena lets you store additional data about some data type that is itself stored
in an
Arena.