62 Arena allocation for RPM nodes

Status: unimplemented proposal. This chapter considers allocating resident RPM nodes from arenas and representing references between them with arena indexes.

Current representation

RPM nodes are currently allocated individually with new and released with delete. Each node has a pointer to its parent, and each resident internal node contains an array of 256 child pointers. On a 64-bit build the child-pointer array alone occupies 2 kB.

The RPM loads nodes on demand. It can also evict individual clean nodes that have not been used recently, so an alternative allocator must continue to support reclamation of individual nodes.

Arena allocation

Allocating RPM nodes from an arena could reduce general-purpose heap allocation overhead and heap fragmentation. Placing nodes together could also improve locality when traversing the RPM. Destroying the whole RPM would not require a separate heap operation for every resident node.

A purely monotonic arena would not be suitable because evicted nodes would continue to occupy memory. The arena would need to reuse released slots, probably by maintaining a free list. RPM node types have different sizes and behaviour, so separate arenas for RPM0, RPMi, and RPM3 would avoid sizing every slot for the largest node. The RPM7 root can remain owned directly by the LSS.

Indexes instead of pointers

Parent and child references could be represented by indexes into the appropriate arena. A reserved index, such as zero, would represent a null reference. Using 32-bit indexes would reduce an internal node's 256-entry child array from 2 kB to 1 kB on a 64-bit build. It would also allow arena storage to move without rewriting every reference.

An index should be an in-memory handle rather than part of the persistent LSS format. If a released slot can be reused while an old handle might still exist, the handle should include a generation or the design must otherwise guarantee that stale indexes cannot be dereferenced.

Code can resolve an index to a pointer while operating on a node, but must not retain that pointer across an operation that can relocate arena storage. Alternatively, arena storage can be divided into non-moving blocks, preserving pointer stability while retaining compact indexes for stored references.

Possible implementation sequence

  1. Introduce type-specific pools or arenas while retaining pointers between RPM nodes.
  2. Measure allocation cost, resident memory, and RPM traversal performance.
  3. If pointer storage remains significant, replace parent and child pointers with 32-bit handles.
  4. Preserve the existing ability to evict and reuse individual clean nodes.

Arena allocation and indexed references are related but independent changes. The arena principally addresses allocation cost, fragmentation, and locality. Indexed references principally reduce the size of internal nodes and make relocation possible.