Partially select oversized candidate rankings
perfloop/fsst · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_g39fqbf61n
Verdict
VERIFIED · settled 2026-07-24 · merged as axiomhq/fsst#5
What happened: Validated after correcting the stale heap-specific retention comment. The fresh co-measured public art_of_war Train result improved from 1,921,204 to 1,813,109 ns/op (5.63% lower; p=0.00105003), exceeding the 5% goal. Primary allocs/op held at 2; B/op was statistically unconfirmed (190,218 to 192,243). The three public-Train threshold workloads and their allocation metrics passed their no-regression bounds, and all focused determinism, round-trip, reachability, and tied-cutoff ordering checks passed. The final production change remains bounded reusable scratch selection with partitioning and prefix sorting, plus its focused ordering test and corrected retention documentation.
Hypothesis
Train invokes buildCandidates at frac 8, 38, 68, 98, and 128, so this ranking runs five times per Train call. selectCandidates currently scans every candidate through a fixed-size 510-entry min-heap, repairs that heap for admissions, and then performs 510 heap pops to produce descending output. In a disposable instrumentation check of Train on testdata/art_of_war.txt, candidate counts at those fractions were 1,226, 3,546, 1,559, 1,003, and 223; the first four rounds exceed the retained limit. Thus N=len(candidates) reaches thousands on the exercised byte-corpus workload while K remains 510, and the current path can pay heap maintenance proportional to N log K plus K log K output work. A targeted baseline CPU profile from `go test ./... -run '^$' -bench '^BenchmarkCorpusCompressionSuite/art_of_war.txt/train$' -benchtime=2s -cpuprofile` attributed 580 ms cumulative, 25.8% of sampled CPU, to selectCandidates; the profile list placed substantial cumulative time at heap down and pop call sites. As a directional falsification probe only, a disposable partition-then-sort-510 prototype passed TestTrainDeterministic, TestTrainDeterministicManyCandidates, TestSelectCandidatesKeepsStrongestInDescendingOrder, and TestTrainEncodeDecode; five sequential CPU=1 benchmark samples were 1.875–2.011 ms/op for baseline versus 1.758–1.879 ms/op for that prototype. That sequential comparison is not a controlled regression result, and the CPU/memory effect of retaining a larger pooled scratch slice remains a hypothesis. The removed delta is repeated heap repair plus heap-pop ordering work on oversized maps, replaced by one partition and sorting only K retained values. Confirm with an interleaved benchmark and CPU profile sweeping corpus diversity/cardinality on both sides of N=510, while checking allocations and pooled retained memory; require byte-identical serialized tables and round-trip compression results before accepting the change.
Change to test: For candidate sets above 510, collect map values into deliberately bounded reusable scratch storage, partition to the strongest 510 in expected linear time, then sort only that retained prefix with the existing total betterThan ordering. Keep the small-set path simple and preserve descending order because buildCandidates relies on collision fallbacks being attempted strongest first.
Where it lives
perfloop/fsst · train.go