Avoid general exponentiation for every dense register

perfloop-oss/hyperloglog · INEFFICIENT ALGORITHM

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

Verdict

VERIFIED · settled 2026-10-01 · pull request opened as axiomhq/hyperloglog#75

What happened: The paired measurements met the required improvement.

Hypothesis

Dense count-distinct reads calculate a power of two for every stored register. That may add substantial CPU to a count query. The CPU saving and real callers' query frequency remain unmeasured.

At revision 398140fe0361ed5bb870b3daeef2b417d3b22ea1, the README describes counting distinct items in a multiset and a 16 KB, precision-14 configuration. The benefiting operation is `Sketch.Estimate()` on a sketch built with the public `NewNoSparse()` constructor, populated through `Insert` or `InsertHash`, and then queried for its count. The constructor creates 16,384 byte registers in dense mode (`hyperloglog.go:42-43,77-93`). This cost-relevant state is fixed by the chosen constructor, not inferred from a synthetic input distribution. With inserts but no operation that replaces the sketch's representation, a successful `Estimate` always reaches `sumAndZeros` once. The inferred eligible-call cadence is one scan per count read in this dense mode; its use and read frequency among library consumers are unknown. A zero-value sketch returns immediately, and a sparse sketch that stays sparse returns without this scan.

For each such dense read, `sumAndZeros` calls `math.Pow(2,float64(v))` once per register: 16,384 general-power evaluations for precision 14, whether the register is zero or nonzero. It also reads each byte, checks for zero, and adds to the sum. `Sketch.Estimate` evaluates its correction once after the scan. The register rank is a byte, so the reciprocal powers are exactly representable in float64. The number of exponentiations and their comparison with one sequential byte scan and one correction are source-derived CPU-cost inferences, not measured time or a claim of production traffic. The per-register general calculation is plausibly material beside those other CPU costs at the fixed 16,384-register size; a zero-heavy sketch may make individual `math.Pow` calls cheaper. Eliminating those 16,384 evaluations should lower CPU per dense count read if lookup overhead is smaller, while leaving the scan and correction. No particular percentage gain or net saving for insertion-heavy use is established.

A Case can falsify that inferred benefit by building `NewNoSparse()` sketches through ordinary distinct and duplicate `Insert` calls, retaining their populated state, and comparing baseline and changed CPU per complete `Sketch.Estimate()` call on the same precision-14 state. It should check exact estimates, including insertion, merge, reset, and binary round-trip cases across supported precisions. Empty sketches and higher precisions are optional samples to test cost sensitivity, not evidence of consumer frequency. A same-state full-operation benchmark showing no meaningful CPU decrease would reject the performance claim; production mode selection and call cadence would require evidence outside this repository.

Change to test: Reduce CPU spent computing dense cardinality estimates without changing their results. Replace per-register general exponentiation with exact precomputed powers for byte-valued ranks, preserving zero counting and accumulation order.

Where it lives

perfloop-oss/hyperloglog · hyperloglog.go

Evidence

populated NewNoSparse p14 Estimate · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 300531 52747 −82.6% (−248192) −259959 to −241076 < −15027 PASSED

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

Timeline