Stop futile string-frequency map growth at half cardinality

perfloop/btrblocks · ALLOCATION HOT LOOP

https://perfloop.ai/t/oss/case_m9safc95nq

Verdict

VERIFIED · settled 2026-08-17

What happened: The paired measurements met the required improvement.

Hypothesis

The target creates a frequency map and currently hashes/inserts every value until more than 4,096 distinct strings have been retained. Yet `estimateStringDict` rejects a count above n/2, and Sparse requires one value to cover at least 90% of rows. On arrival of a new string when the map already contains at least n/2 keys, the actual cardinality becomes greater than n/2; Dict is therefore ineligible, and that many distinct values also makes a 90% dominant value impossible. The integer counterpart already uses this pre-insert n/2 cutoff. The direct caller invokes this stats pass once per string-column planning invocation when frequency collection is enabled, so the cadence is one full row scan per such column.

Measured in a disposable focused `go test` probe that mirrored this function except for the proposed pre-insert cutoff, a 4,096-row all-unique string array changed from 517–529 µs/op, about 423 KB/op, and 36 allocs/op to 261–268 µs/op, about 205 KB/op, and 19 allocs/op. This measures the synthetic trigger, not its production prevalence; the likely removed work is post-threshold map hashing/insertion and map growth, while the required row, byte, and run scan remains. A prior focused existing stats test also passed. A case session should add a differential test across just-below/above-half cardinality mixtures that confirms Dict and Sparse eligibility, totalBytes, isConst, and avgRunLength are unchanged, then benchmark `computeStringStatsForPlanner` with 1K/4K/8K rows and CPU/allocation profiles. The confirming signal is fewer ns/op, B/op, and allocs/op only on enabled, high-cardinality inputs before the 4,096 cap, without changed scheme selection.

Change to test: Mirror the integer stats policy: distinguish an existing key from a newly seen string, and before inserting a new key drop frequency tracking when the retained cardinality is already at the 4,096 budget or at least n/2. Preserve the existing overflow sentinel (distinctCount=n and mostFrequent=0), while continuing the total-byte and run-stat scans unchanged.

Where it lives

perfloop/btrblocks · compress/compress_str.go

Evidence

all-unique string compressor stats path, 4096 rows, frequency collection enabled · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 406076 211860 −47.7% (−193586) −210082 to −173101 < −20304 PASSED
B/op 423163 204729 −51.6% (−218434) −218434 to −218432 < −21158 PASSED
allocs/op 36 19 −47.2% (−17) −17 to −17 < −1.8 PASSED

Checks: 3 of 3 passed. Verification: no defect found.

Timeline