60 RPM improvements

Status: unimplemented proposals. The current Recoverable Packet Map is described in Recoverable Packet Map (RPM). This chapter collects possible changes to its representation, allocation interface, and maintenance.

Remove redundant nodes

An RPM node with no descendant data packets cannot always be deleted because it can preserve Seid allocation state and thereby prevent reuse of previously allocated Seids. Most Seid spaces are not used for local allocation, however, and do not need to preserve that state.

The LSS could be told which Seid spaces are eligible for allocation. It could then recursively remove empty RPM nodes from all other spaces. The upper levels do not need to preserve SeidHigh allocation state because that state is held by the non-evictable RPM7 root. A related optimisation could remove redundant nodes more aggressively from an RPM3 that uses only non-affiliated allocation.

Pin a Seid-allocation node

The LSS could give a client a handle to a Seid space used for allocation. Keeping the corresponding level-three RPM node resident would avoid traversing the upper four levels for every allocation. The handle would need to be closed explicitly so the node could again become eligible for eviction.

Replace byte-wise Seid access with shifting and masking

The contiguous-Seid implementations of GetParentNodeAndChildIndex() and AlwaysGetParentNodeAndChildIndex() take the address of a Seid and walk its bytes from most to least significant. They could instead operate directly on the 64-bit value, extracting each path component with shifts and an 0xff mask. This would express the numeric layout directly, remove the byte-pointer arithmetic and associated dependence on host byte order, and make register-only evaluation easier for the compiler to recognise.

This should not be assumed to improve performance without measurement. An optimising compiler may already replace the source-level byte accesses with register operations, while the dependent RPM node lookups are likely to dominate the cost. Compare optimised assembly and benchmark the complete lookup path before and after the change. Any replacement should preserve handling of leading 0xff bytes, the mapping from packet level to child index, missing-node returns, and the TouchRPM0() call for data packets.

Use a variable radix with wider bottom-level nodes

The RPM currently consumes one byte of a Seid at each level, giving every node a radix of eight bits and up to 256 children. A candidate variable-radix layout, listed from the root towards the data packet, is 10, 10, 12, 10, 10, 12. This covers all 64 bits in six levels and splits cleanly into identical 10, 10, 12 decompositions of SeidHigh and SeidLow. Each component can be obtained with constant shifts and masks.

The 12-bit bottom radix is important because the vast majority of RPM nodes are at the bottom of the tree. A bottom node would contain up to 4096 packet positions rather than 256. For dense, sequentially allocated Seids, one larger bottom node replaces approximately sixteen current bottom nodes. The number of heap allocations for RPM nodes could therefore approach a sixteen-fold reduction, together with similar reductions in per-node construction, destruction, metadata, parent-child links, eviction-list maintenance, and dirty-node bookkeeping. A 10-bit parent of these nodes spans 1024 * 4096, or 4,194,304, data-packet Seids.

This arrangement puts the larger fan-out where consecutive Seids naturally fill it, while using 10-bit, 1024-entry nodes elsewhere. Assuming eight bytes per entry, a dense 10-bit array occupies about 8 KiB and a dense 12-bit array about 32 KiB. Across a densely allocated range, sixteen 256-entry arrays and one 4096-entry array contain the same number of entries; consolidation saves the repeated RPM-node and allocation overhead rather than increasing the total entry storage. Reducing the depth from eight levels to six also removes two dependent node lookups, index operations, and existence branches from a full traversal.

The trade-off is coarser granularity. A sparsely occupied 12-bit leaf can waste more space, and loading, dirtying, serialising, or evicting a 32 KiB node for a small number of entries may cause read or write amplification. A dense-prefix representation could avoid allocating unused trailing entries in memory, but persistence and eviction granularity would still need consideration. The existing scheme for encoding RPM packet levels with leading 0xff bytes also assumes an eight-bit radix and would need to be redesigned. Measurements should compare node-allocation rate, resident memory, cache behaviour, serialised I/O, eviction behaviour, and complete lookup latency.

Sparse nodes

Each RPM node currently reserves a full array of 256 log-record positions even when few entries are present. Alternative in-memory and serialised representations could reduce the memory and storage cost of sparsely populated or formerly full nodes. Any compact representation would trade space against lookup cost and mutation complexity.

Further investigation

  • Review thread safety and possible deadlocks.
  • Measure eviction behaviour and memory use.
  • Verify that Seids cannot be recycled unexpectedly.
  • Test the RPM independently of the rest of the LSS.
  • Make the external contracts and internal invariants explicit in the code.

The separate Arena allocation for RPM nodes proposal considers pooling resident nodes and replacing in-memory pointers with compact handles.