gaissmai / bart / 26016311828

91%

main: 91%

Build Type

Pull #379

github

Committed by gaissmai

Commit Message

new FastNode implementation

Changed from fixed-size 256-slot arrays (the original ART design)
to popcount-compressed sparse arrays plus a pre-computed
childRankCache[256]uint8 to improve the level traversing speed.

The allotment propagation mechanism 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 address, maintained by O(256) increment/decrement loops on insert/delete;
MustGetChild becomes a simple two-array lookup.

ZST restriction removed: sync.Once + PanicOnZST replaced by [0]sync.Mutex
(noCopy sentinel for go vet), allowing Fast[struct{}] and similar types.

Pull Request Pull Request #379: new FastNode implementation

Coverage Stats

193 of 195 new or added lines in 13 files covered. (98.97%)

3 existing lines in 2 files now uncovered.

6754 of 7442 relevant lines covered (90.76%)

1.02 hits per line