Crate compact_arena
source ·Expand description
A crate with a few single-typed arenas that work exclusively with indexes. The indexes are sized with the arena. This can reduce memory footprint when changing pointers to indices e.g. on 64-bit systems.
The arenas use a variant of “branded indices”: The indices contain an invariant lifetime tag that binds them to their respective arena so you cannot mix up two arenas by accident. Unlike the indexing crate, this generates the type tags from unique mutable borrows of unit tuples without requiring a closure. This allows us to store indices within objects that we put into the arena, which is a boon to things like graph data structures.
The lifetime tags make it impossible to share an arena via an Arc
, but
one can use crossbeam-utils
’ scoped
threads to work around this limitation. See examples/threads.rs
for a
working example.
Use the mk_arena!
/mk_tiny_arena!
/mk_nano_arena!
macros to
create an arena, then add
or try_add
items to it and index it with
arena[idx]
.
§Examples
mk_nano_arena!(arena);
let idx = arena.add(1usize);
assert_eq!(1, arena[idx]);
You can work with multiple arenas:
mk_nano_arena!(a);
mk_nano_arena!(b);
..
The compiler gives you a type error if you mix up arenas:
mk_nano_arena!(a);
mk_nano_arena!(b);
let i = a.add(1usize);
let _ = b[i];
The indices should not be able to escape the block with the mk_*arena
call
let idx = { mk_tiny_arena!(arena); arena.add(1usize) };
Also, arenas may not be instantiated recursively:
fn recursive(idx: Option<Idx8<'_>>) {
mk_nano_arena!(arena); // `tag` does not live long enough
if let Some(idx) = idx {
assert_eq!("hello", arena[idx]);
} else {
recursive(Some(arena.add("hello")));
}
}
recursive(None);
Even if you try to mix up arenas using multiple threads, you will run into lifetime errors:
fn mixup(c: Result<Sender<Idx16<'_>>, Receiver<Idx16<'_>>>) {
mk_tiny_arena!(arena);
match (s, r) {
Ok(s) => s.send(arena.add(1usize)).unwrap(),
Err(r) => assert_eq!(1, arena[r.recv().unwrap()]),
}
}
fn main() {
let (s, r) = channel();
let st = thread::spawn(|| mixup(Ok(s)));
let rt = thread::spawn(|| mixup(Err(r)));
st.join().unwrap();
rt.join().unwrap();
}
The SmallArena
type keeps its storage in a Vec
that may be useful to
reuse. For that reason we have the recycle_arena!
macro. There is no
variant of this for the Tinyarena
and NanoArena
types, which store
their items inline.
Macros§
- Run a piece of code inside an arena
- Run code using a nano arena. The indirection through the macro is required to bind the indices to the arena.
- Run code using a tiny arena. The indirection through this macro is required to bind the indices to the arena.
- Run code using an arena. The indirection through the macro is required to safely bind the indices to the arena. The macro takes an identifier that will be bound to the
&mut Arena<_, _>
and an expression that will be executed within a block where the arena is instantiated. The arena will be dropped afterwards. - Create a tiny arena. The indirection through this macro is required to bind the indices to the arena.
- Create a tiny arena. The indirection through this macro is required to bind the indices to the arena.
- Empty the arena, and set the binding to a new arena using the storage of the argument.
- Fix an invariant lifetime to a
tag
value.
Structs§
- An error type that gets returned on trying to add an element to an already full arena. It contains the element so you can reuse it
- An index into the arena. You will not directly use this type, but one of the aliases this crate provides (
Idx32
,Idx16
orIdx8
). - This is one part of the secret sauce that ensures that indices from different arenas cannot be mixed. You should never need to use this type in your code.
- A “nano” arena containing up to 256 elements.
- A “Small” arena based on a resizable slice (i.e. a
Vec
) that can be indexed with 32-bitIdx32
s. This can help reduce memory overhead when using many pointer-heavy objects on 64-bit systems. - A “tiny” arena containing <64K elements.
Functions§
- Create an invariant lifetime. This is one part of the secret sauce that ensures that indices from different arenas cannot be mixed. You should never need to use this type in your code.
Type Aliases§
- The index type for a nano arena is 8 bits large. You will usually get the index from the arena and use it by indexing, e.g.
arena[index]
. - The index type for a tiny arena is 16 bits large. You will usually get the index from the arena and use it by indexing, e.g.
arena[index]
. - The index type for a small arena is 32 bits large. You will usually get the index from the arena and use it by indexing, e.g.
arena[index]
.