gaissmai / bart / 40366188620

95%

main: 95%

Build Type

Pull #440

github

Committed by gaissmai

Commit Message

refactor: Remove bart.Fast, rely on the rank cache in sparse.Array256

sparse.Array256 carries its own rank cache now, so a rank needs one
popcount instead of four. Get and MustGet take about 35-45% less time
than the former Rank based versions (microbenchmarks, AMD EPYC 9275F)
and are inlinable. This makes the per-node [256]uint8 cache of
bart.Fast redundant.

Remove the Fast table and FastNode together with their generated code,
tests, example, benchmarks, generator entries and NODETYPES.md.
bart.Table and bart.Lite remain.

Keep bart.Fast as a deprecated generic type alias for bart.Table, so
existing code keeps compiling. The alias carries a //go:fix inline
directive, "go fix ./..." (Go 1.26 or later) rewrites bart.Fast to
bart.Table.

Lookups:
- Contains, Lookup and lookupPrefixLPM call Children.Get(octet) instead
  of Children.Test(octet) followed by MustGetChild(octet).
- Contains: drop the "longest-prefix matching" wording from the doc,
  the method reports any match.

Node code:
- Move InsertChild, GetChild, MustGetChild, DeleteChild and ChildCount
  into the common template, they are identical for all node types.
- Generate AllIndices, LookupIdx and Lookup for LiteNode too and drop
  the SKIP_LITE markers. LiteNode.MustGetPrefix returns the zero value.
- Write the BartNode prefix methods by hand in bart.go.
- Rename LiteNode.Prefixes.Count to the unexported count.

Tests and benchmarks:
- Rename the Bart benchmarks to Table and add Lite counterparts,
  remove the Fast benchmarks.
- Drop BitSet256.Rank from the must-inline list, it is no longer on the
  lookup path.
- Run the sparse.Array256 subtests in parallel.

README: describe the two remaining tables, remove the Fast comparison
and the NODETYPES.md link, use Lite.Contains for the benchmark teaser.

Pull Request Pull Request #440: Deprecate Fast as a Table alias and cache sparse-array ranks

Coverage Stats

86 of 88 new or added lines in 8 files covered. (97.73%)

2 existing lines in 1 file now uncovered.

3819 of 4031 relevant lines covered (94.74%)

0.95 hits per line