2 releases
0.5.1 | Jan 14, 2021 |
---|---|
0.5.0 | Jan 10, 2021 |
#1936 in Data structures
Used in pui
275KB
5K
SLoC
pui-arena
A set of very efficient, and very customizable arenas that can elide bounds checks wherever possible.
License: MIT/Apache-2.0
lib.rs
:
A set of very efficient, and very customizable arenas that can elide bounds checks wherever possible.
This crate is heavily inspired by crates like slotmap
and slab
.
pui-arena
provides a set of collections that allow you to insert and delete
items in at least amortized O(1)
, access elements in O(1)
. It also provides
the tools required to avoid the ABA
problem.
You can think of the collections in pui-arena
as a HashMap
/BTreeMap
where
the arena manages the keys, and provides a very efficient way to access elements.
Why use pui-arena
over alternatives
pui-arena
allows you to minimize overhead wherever possible, and fully customize
the arenas. This allows you to use an api like slab
or slotmap
based on how
you use the api. (There are also newtypes featured-gated by the features slab
and slotmap
that implement a similar interface to those two crates).
If you use the pui
/scoped
feature, then you can also eliminate bounds checks
entirely, which can be a huge performance save in performance sensitive regions.
pui-arena
also provides a more features than competitors, such as a vacant entry
api for versioned arenas, and drain_filter
for all arenas.
Choosing sparse
, hop
, or dense
-
If you want fast insertion/deletion/acccess and don't care about iteration speed, use
sparse
. -
If you want fast iteration speed above all else, use
dense
-
If you want reasonable iteration speed and also fast access/delete, or if
dense
is to memory heavy, usehop
You can read about the details of how each works in the corrosponding module docs
Performance characteristics
Speed
all of the collections in pui-arena
allow you to
- insert elements in amortized
O(1)
- delete/access elements in
O(1)
- guarantee that keys never get invalidated unless
remove
is called
Memory
For each Arena<T, _, V>
where V: Version
, the memory overhead is as follows:
sparse
Arena
-size_of(V) + max(size_of(T), size_of(usize))
per slothop
Arena
-size_of(V) + max(size_of(T), 3 * size_of(usize))
per slotdense
Arena
-size_of(V) + size_of(usize)
per slot, andsize_of(usize) + size_of(T)
per value
Implementation Details
The core of this crate is the the Version
trait,
the ArenaKey
trait, and the BuildArenaKey
trait.
Version
specifies the behavior of the arenas.
pui-arena
provides three implementations,
see Version
for more details:
DefaultVersion
- Ensures that all keys produced by
insert
are unique - backed by a
u32
, so it may waste space for small values- technically if items are inserted/removed many times, slots will be "leaked", and iteraton performance may degrade but, this is unlikely, unless the same slot is reused over 2 billion times
- Ensures that all keys produced by
TinyVersion
-- Ensures that all keys produced by
insert
are unique - backed by a
u8
, if items are inserted/removed many times, slots will be "leaked", and iteraton performance may degrade
- Ensures that all keys produced by
Unversioned
-- Keys produced by
insert
are not guartneed to be unique - slots will never be "leaked"
- Keys produced by
ArenaKey
specifies the behavior of keys into arenas.
pui-arena
provides a number of implementations. See ArenaKey
for details.
usize
- allows accessing a given slot directly, with no regard for it's version- Note: when I say "with no regard for it's version", it still checks the version to see if the slot is occupied, but it has no means of checking if a slot a value was re-inserted into the same slot
Key<K, _>
- allows accessing a slot specified byK
, and checks the generation of the slot before providing a value.K
can be one of the other keys listed here (except forScopedKey
)
TrustedIndex
- allows accessing a given slot directly, with no regard for it's version- elides bounds checks, but is unsafe to construct
- This one should be used with care, if at all. It is better to use the
pui
feature and usepui_vec::Id
instead. It is safe, and also guartnees bound check elision
ScopedKey<'_, _>
- only allows access into scoped arenas (otherwise identical toKey
)
enabled with the pui
feature
pui_vec::Id
- allows accessing a given slot directly, with no regard for it's version- elides bounds checks
BuildArenaKey
specifies how arenas should create keys, all implementors of ArenaKey
provided by this crate also implement BuildArenaKey
except for TrustedIndex
.
Custom arenas
You can newtype arenas with the newtype
macro, or the features: slab
, slotmap
, or scoped
.
slab
- provides a similar api to theslab
crate- uses
usize
keys, andUnversioned
slots
- uses
slotmap
- provides a similar api to theslab
crate- uses
Key<usize>
keys, andDefaultVersion
slots
- uses
scoped
- provides newtyped arenas that usepui_core::scoped
to elide bounds checks- uses
scoped::ScopedKey<'_, _>
keys, and is generic over the version
- uses
newtype
- creates a set of newtyped arenas with the module structure ofbase
- These arenas elide bounds checks, in favor of id checks, which are cheaper,
and depending on your backing id, can be no check at all!
(see
pui_core::scalar_allocator
details)
- These arenas elide bounds checks, in favor of id checks, which are cheaper,
and depending on your backing id, can be no check at all!
(see
// Because the backing id type is `()`, there are no bounds checks when using
// this arena!
pui_arena::newtype! {
struct MyCustomArena;
}
let my_sparse_arena = sparse::Arena::new();
let my_dense_arena = dense::Arena::new();
let my_hop_arena = hop::Arena::new();
Becomes something like
pui_core::scalar_allocator! {
struct MyCustomArena;
}
mod sparse {
pub(super) Arena(pub(super) pui_arena::base::sparse::Arena<...>);
/// more type aliases here
}
mod dense {
pub(super) Arena(pub(super) pui_arena::base::dense::Arena<...>);
/// more type aliases here
}
mod hop {
pub(super) Arena(pub(super) pui_arena::base::hop::Arena<...>);
/// more type aliases here
}
let my_sparse_arena = sparse::Arena::new();
let my_dense_arena = dense::Arena::new();
let my_hop_arena = hop::Arena::new();
Where each Arena
newtype has a simplified api, and better error messages.