Skip to content

v0.28.0: New FastNode implementation

Choose a tag to compare

@gaissmai gaissmai released this 20 May 21:09
· 37 commits to main since this release

FastNode changed from fixed-size 256-slot arrays (the original ART design)
to popcount-compressed sparse arrays (as for BartNode) but plus a pre-computed
childRankCache[256]uint8 to improve the level traversing speed in comparison
to BartNode.

The previous allotment propagation mechanism for Fast is removed in favor of
the slower bitset-intersection-based LPM lookup.

The Fast lookup path is refactored to use the same stack-based
backtracking pattern already used by Table.Lookup.

The zero-sized-type restriction on Fast is also lifted, since
the new implementation stores values directly rather than requiring
distinct pointer identity.

FastNode memory reduced:
from a fixed 4,168 bytes to ~368 bytes base + sparse items;
the allot propagation loop and *any pointer indirection are eliminated.

childRankCache: a 256-byte array caching the sparse-array rank for each
child octet, maintained by O(256) increment/decrement loops on insert/delete;
MustGetChild becomes a simple two-array lookup.

ZST (zero-sized-type) restriction removed.