#arena #slab #generational

thunderdome

Fast arena allocator with compact generational indices

5 unstable releases

new 0.3.0 Oct 17, 2020
0.2.1 Oct 2, 2020
0.2.0 Sep 3, 2020
0.1.1 Sep 3, 2020
0.1.0 Sep 3, 2020

#64 in Memory management

28 downloads per month

MIT/Apache

38KB
657 lines

Thunderdome

GitHub CI Status thunderdome on crates.io thunderdome docs

Thunderdome is a gladitorial generational arena inspired by generational-arena, slotmap, and slab. It provides constant time insertion, lookup, and removal via small (8 byte) keys returned from Arena.

Thunderdome's key type, Index, is still 8 bytes when put inside of an Option<T> thanks to Rust's NonZero* types.

Basic Examples

let mut arena = Arena::new();

let foo = arena.insert("Foo");
let bar = arena.insert("Bar");

assert_eq!(arena[foo], "Foo");
assert_eq!(arena[bar], "Bar");

arena[bar] = "Replaced";
assert_eq!(arena[bar], "Replaced");

let foo_value = arena.remove(foo);
assert_eq!(foo_value, Some("Foo"));

// The slot previously used by foo will be reused for baz
let baz = arena.insert("Baz");
assert_eq!(arena[baz], "Baz");

// foo is no longer a valid key
assert_eq!(arena.get(foo), None);

Comparison With Similar Crates

Feature Thunderdome generational-arena slotmap slab
Generational Indices¹ Yes Yes Yes No
size_of::<Index>() 8 16 8 8
size_of::<Option<Index>>() 8 24 8 16
Max Elements 2³² 2⁶⁴ 2³² 2⁶⁴
Non-Copy Values Yes Yes Sorta² Yes
no_std Support No Yes No No
Serde Support No Yes Yes No
  1. Generational indices help solve the ABA Problem, which can cause dangling keys to mistakenly access newly-inserted data.
  2. slotmap's SlotMap and HopSlotMap require values to be Copy on stable Rust versions. slotmap's DenseSlotMap type supports non-Copy types on stable, but has different performance trade-offs.

Minimum Supported Rust Version (MSRV)

Thunderdome supports Rust 1.34.1 and newer. Until Thunderdome reaches 1.0, changes to the MSRV will require major version bumps. After 1.0, MSRV changes will only require minor version bumps, but will need significant justification.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

No runtime deps