v0.5.2 — bench harness expanded to three comparators

Changed (docs)

• benchmarks.md per-operation results now compare ART against three
  implementations rather than one. The bench/ harness gained _Tidwall
  (github.com/tidwall/btree v1.8.1, configured with
  Options{NoLocks: true, Degree: 32} for parity with google/btree's default
  degree and to keep its sync.RWMutex out of the measurement) and _Plar
  (github.com/plar/go-adaptive-radix-tree v1.0.7, whose public API stores
  interface{} values — the per-Put boxing alloc that costs is structural to
  the API and is documented in-table) siblings of Put, Get, GetMiss,
  Delete, and Range. The Verdict prose has been rewritten to reflect the
  new three-comparator landscape rather than the prior google/btree-only
  framing. No core .go files were edited; the change is confined to the
  nested bench/ module and the benchmarks.md doc.

v0.5.1 — refactor + CI/test fixes

Changed (internal)

• Deduplicated the four-way prefix-consume / terminal-check preambles in
  get.go, delete.go, and iterate.go behind three free helpers in
  helpers.go (consumePrefix, terminalValue[V], yieldTerminalInRange[V]).
  −40 net LOC. No additions to the node / innerNode interfaces; every
  helper is a free function over concrete types so no interface-method
  indirection is introduced (runtime.getitab remains absent from Get and
  Delete pprof profiles). put.go is intentionally left expanded — sharing
  a helper across the prefix-split allocation boundary would reintroduce
  interface dispatch on the hot path, per the reverted polymorphism spike
  recorded in polymorphism-failed.md. Hot-path benchmarks at parity with
  v0.5.0 within run variance.

Fixed

• artmap/ordered_test.go: the TestOrdered_Float64_OrderAcrossZero fixture
  now uses math.Copysign(0, -1) for actual IEEE-754 negative zero. The
  prior -0.0 literal was folded to +0.0 by the parser (staticcheck
  SA4026); the test now exercises the intended sign-bit case.

CI

• The fuzz-smoke workflow step now discovers Fuzz* targets dynamically
  across all packages and runs each one scoped to its own package. Replaces
  a go test -fuzz=… ./... invocation that was rejected by Go with
  "cannot use -fuzz flag with multiple packages" once the artmap
  subpackage was introduced. Future fuzz targets in any package are picked
  up automatically; an explicit empty-set guard fails the step if no
  targets are discovered.

v0.5.0

Added

• Tree[V] descending iteration and open-ended range methods: AllDescending, RangeFrom, RangeTo, RangeDescending.
• artmap subpackage exposing Ordered[K cmp.Ordered, V any], a typed sorted-map façade over byte-keyed ART with order-preserving encoders for the cmp.Ordered types. Encoder overhead on int64 keys: +2.6 ns/op (Put), +2.5 ns/op (Get), +1.3 ns/op (Delete).
• art.LockedTree[V]: a sync.RWMutex wrapper exposing Put, Get, Delete, Len, Clear, and Clone. Uncontended Get overhead ~0.8 ns/op.

Performance

• De-parameterised the internal node interface so that V appears only on Tree[V] and the leaf. Delete (bulk 10M, 8-byte keys): −39 ns/key (~34 % faster). Get (hit, 10M, 8-byte keys) showed a +8.5 ns/op regression at landing (d8df19e), but investigation (findings note 2a29d2a7) attributed the gap to code-layout / i-cache sensitivity rather than the node-interface shape; the regression self-healed across subsequent layout-affecting commits. Re-measured at the release commit, Get is 43.68 ns/op — at parity with (slightly below) the pre-E-D2 baseline.

Documented

• benchmarks.md expanded with three-column-per-engine tables (ns/op · B/op · allocs/op) and a key-shape sensitivity section covering seqInt64 / randInt64 / uuid / urlPath.

Stability

• README now carries a ## Stability section enumerating the exported surface of both packages that will be frozen at v1.0 and committing to Semantic Versioning from that tag forward. Target for v1.0.0 is no earlier than 2026-07-23.

v0.4.1 — performance recovery

Recovers the Get (hit) and Delete (bulk) regressions flagged in v0.4.0. Single-file refactor of put.go / delete.go / helpers.go; public API unchanged; Len remains O(1).

Performance

median of 5 reps, -benchtime=3s -count=5, VirtualApple @ 2.50 GHz, Go 1.24.2

Operation	v0.4.0	v0.4.1	Δ
Get (hit)	57.57 ns/op	44.81 ns/op	fully recovered to pre-generics baseline (43.22 ns/op)
Delete (bulk)	124.5 ns/key	115.3 ns/key	−9 ns/key (~7 %); residual ~45 ns/key gap vs pre-generics (70.0 ns/key) tracked for follow-up

ART is now ~21× faster than google/btree on Get (hit), up from 15× at v0.4.0.

What changed

• Tree.size is now tracked at the insertLeaf / clearTerminalIfMatches chokepoints instead of being propagated through recursive return tuples. Parent frames detect no-op by pointer equality on the returned subtree. putInto / putIntoNodeN / deleteFrom revert to single-return-value signatures.
• The Get recovery is a code-layout / register-pressure side effect of the put/delete refactor — no change to get.go.

Documented

• benchmarks.md re-baselined at commit d14c9c6. Regression annotations removed / adjusted.
• CHANGELOG.md backfilled with entries for v0.3.0, v0.4.0, v0.4.1.

Install

go get github.com/KentBeck/AdaptiveRadixTree2@v0.4.1

Compare: v0.4.0...v0.4.1

v0.4.0 — benchmark re-baseline

Re-measured all 10 benchmarks at -benchtime=3s -count=5 against current HEAD. benchmarks.md now reflects post-generics reality with a documented protocol / environment footer.

Headline numbers

median of 5 reps, VirtualApple @ 2.50GHz, Go 1.24.2

Operation	ART	B-tree	Winner
Put (bulk)	150.8 ns/key	752.6 ns/key	ART 5.0×
Get (hit)	57.57 ns/op	861.9 ns/op	ART 15×
Get (miss)	9.36 ns/op	118.5 ns/op	ART 12.7×
Delete (bulk)	124.5 ns/key	796.3 ns/key	ART 6.4×
Range (1 %, 100 K)	19.21 ns/key	10.73 ns/key	B-tree 1.8×

Flagged for follow-up (regressions vs pre-generics)

• ART Get (hit) +33 %
• ART Delete +78 %

Both deferred — investigation is a separate PR.

Surprise improvement

• ART build-time allocs/entry dropped 2.02 → 1.02 (−50 %), likely a monomorphisation benefit from the generics refactor.

Install

go get github.com/KentBeck/AdaptiveRadixTree2@v0.4.0

Compare: v0.3.0...v0.4.0

v0.3.0 — CI, packaging, and corpus

Publishability polish.

Added

• GitHub Actions workflow (.github/workflows/test.yml): matrix on Go 1.23.x / 1.24.x with build, vet, gofmt, staticcheck, race tests, and 30 s fuzz smoke.
• Nested bench/ module: consumer dep graph no longer pulls in github.com/google/btree. Root go.mod has zero third-party deps.
• Fuzz corpus: testdata/fuzz/FuzzSortedMap/ — 12 hand-authored seed entries covering promotions, demotions, prefix split/merge, empty key, Clone, and Ceiling / Floor mid-prefix.
• CHANGELOG.md (Keep a Changelog) with v0.1.0 and v0.2.0 history.
• README: CI badge and CHANGELOG link.

Removed

• Four unused isEmpty() methods and their interface declaration (staticcheck U1000).

Install

go get github.com/KentBeck/AdaptiveRadixTree2@v0.3.0

Compare: v0.2.0...v0.3.0

v0.2.0 — sorted-map surface

Adds sorted-map query operations and structural helpers.

Added

• Min() — smallest (key, value, ok).
• Max() — largest (key, value, ok).
• Ceiling(target) — successor (smallest key ≥ target).
• Floor(target) — predecessor (largest key ≤ target).
• Clone() — independent structural copy.
• Clear() — O(1) remove-all.
• Six new ExampleTree_* functions (12 total).

Documented

• Nil-key / empty-key equivalence contract across doc.go, Put, Get, Delete.

Tests

• +17 unit tests (92 total).
• Fuzzer extended with Min / Max / Ceiling / Floor / Clone / Clear operations, cross-checked against a sorted oracle.

Install

go get github.com/KentBeck/AdaptiveRadixTree2@v0.2.0

Compare: v0.1.0...v0.2.0

v0.1.0 — initial release

Adaptive Radix Tree as a sorted map from []byte to V.

Highlights

• Generic Tree[V any] public API (New, Put, Get, Delete, Len, All, Range).
• O(k) Put / Get / Delete, O(1) Len.
• Sorted iteration via Go 1.23 range-over-func (All, Range).
• Path compression with prefix splitting and terminal-carrying collapse.
• Inline small-key buffer (≤ 24 bytes) to halve Put allocations.
• Adaptive node sizing (node4 / node16 / node48 / node256) with promotion and demotion.
• Differential fuzzer against map[string]V + sorted oracle — 45M+ execs, zero divergences.
• Mutation testing efficacy 96.55 % (100 % of killable mutants).
• Six verified ExampleTree_* functions.
• Package documentation (doc.go) and goroutine-safety contract on Tree.

Concurrency

A Tree is not safe for concurrent use by multiple goroutines when any goroutine is writing. Guard with your own sync.RWMutex if needed.

Install

go get github.com/KentBeck/AdaptiveRadixTree2@v0.1.0