Expand description
A safe, indexed, n-ary tree implementation
§About
This module explores using arena allocation for fewer allocations and simpler reference munging via indexes. This implementation includes several critical compromises over the link-based approach. See the Drawbacks below for more details.
Compromises over the link-based tree include being less spatially efficient as the arena’s growth algorithm logically shifts “pointers” to Nodes in the arena.
§Design
The implementation stores all Node values in a Vec-backed arena. For small trees (fewer than ~100 nodes), it is marginally slower than the Rc<RefCell>-based design due to fixed arena management overhead. However, for larger trees (starting around 1,000–10,000 nodes), it improves construction speed by roughly 20–25%, primarily from reduced heap allocations and better cache locality.
§Drawbacks
The Vec-backed design is intended to provide a more ergonomic design over the heavy-handed syntax and semantics of reference counting and interior mutability over the pointer-backed version of this general tree. Unfortunately, this Vec-backed design also comes with its own compromises, which may prove to be more impactful. The Vec-backed design is less spatially efficient due to the structure’s growth. As the tree gets mutated, it also potentially loses cache locality.
§Example