Bitarena: designing for sparse iteration

The workload

Generational arenas provide stable handles while detecting stale references after removal. The tradeoff appears when a long-lived table becomes sparse: straightforward iteration still visits the holes, even when only a small part of the allocated space is live.

The design

Bitarena pairs generational slots with occupancy bitsets. Iteration can inspect a machine word of occupancy information at a time and skip empty blocks rather than checking every slot individually. Handles retain a slot and generation so a removed value cannot be accessed through an older index.

Correctness is part of the data structure

The repository documents the invariants instead of leaving them implicit. Unit tests cover expected behavior, and Miri runs in CI to catch undefined behavior in the unsafe code. There is also a property-test oracle that compares operations against a simple model, but today the main oracle runs a single case per test (the parallel oracle runs 128), so I do not count it as strong evidence yet. Expanding it is the next step. The crate supports no_std with alloc, with optional Serde and Rayon integrations.

Performance without universal claims

The benchmark suite compares Bitarena with other arena and slot-map representations across sparse and dense workloads, different value sizes, and common operations. Results are kept with their reproduction instructions because a data structure only “wins” relative to a workload and measurement setup.

Where it fits, and where it does not

Bitarena is designed for long-lived tables that accumulate holes and are swept repeatedly. A dense packed representation remains a better fit when iteration dominates, mutations are rare, or ordering requirements conflict with arena semantics. Stating that boundary is part of the design, not a limitation to hide.