A high-performance implementation of the HyperLogLog probabilistic cardity estimator in the odin programming language, benchmarked against an exact distinct-count built on Odin's standard hashmap.
HyperLogLog estimates the number of distinct elements in a stream using
constant memory (2^p bytes, independent of the stream length), at the
cost of a small, controllable error. The configurable precision parameter p
selects the number of register streams m = 2^p; the relative standard error
is approximately 1.04 / sqrt(m).
- Variable precision
pfrom 4 to 18 (memory from 16 B to 256 KiB, error from ~26% down to ~0.08%). - High-performance hot path - bounds-check-free, single
LZCNT-based rank,SplitMix64hashing, one allocation, flat cache-friendly register array. - Mergeable sketches (
hll_merge) for distributed counting. - Exact reference counter using
map[u64]bool, with capacity pre-sized to the hashmap's 75% load factor so insertion never rehashes. - Built-in benchmark over
1K -> 1Belements measuring time, memory, and estimation error for both algorithms side-by-side.
| File | Purpose |
|---|---|
hyperloglog.odin |
The HyperLogLog data structure + precision test harness. |
standard_hashmap_count.odin |
Exact distinct counter over Odin's built-in map[u64]bool. |
main.odin |
Entry point: precision tests + head-to-head benchmark table. |
ARCHITECTURE.txt |
Detailed architecture & code walkthrough of the HLL struct. |
odin build . -out:cardinality -o:speed
./cardinality [precision_p] [max_hashmap_n]Arguments (both optional):
precision_p- HyperLogLog precision,4..18(default14).max_hashmap_n- cap the (memory-heavy) hashmap test at this many elements.0or omitted = run every size up to 1 billion (needs ~34 GiB RAM for the 1B hashmap case).
Examples:
./cardinality # p=14, run everything (needs lots of RAM)
./cardinality 14 1000000 # p=14, skip hashmap above 1M (fast)
./cardinality 16 0 # p=16, ~0.4% error, run everythingBenchmark on a 24-core Intel machine, -o:speed, single thread.
Elements are the distinct u64 values 0..N-1.
./cardinality.exe
HyperLogLog (p=14, m=16384 registers = 16.00 KiB, ~0.812% std error) vs exact hashmap set count
Usage: ./cardinality [precision_p=4..18] [max_hashmap_n=0..N]
================================================================
HyperLogLog precision tests (estimated vs true cardinality)
Averaged over several independent hash seeds.
================================================================
--- p=10 (m=1024 registers = 1024 bytes, theoretical std error ~ 3.2500%) ---
true N avg |err| max |err| avg err %
1000 28 58 2.8143%
10000 284 517 2.8414%
100000 2645 3331 2.6454%
1000000 19822 43327 1.9822%
10000000 369212 765193 3.6921%
--- p=12 (m=4096 registers = 4096 bytes, theoretical std error ~ 1.6250%) ---
true N avg |err| max |err| avg err %
1000 11 20 1.0857%
10000 375 568 3.7514%
100000 1289 2428 1.2891%
1000000 15070 22523 1.5070%
10000000 110128 241923 1.1013%
--- p=14 (m=16384 registers = 16384 bytes, theoretical std error ~ 0.8125%) ---
true N avg |err| max |err| avg err %
1000 3 8 0.3429%
10000 52 198 0.5171%
100000 583 1025 0.5830%
1000000 6431 10024 0.6431%
10000000 42617 99619 0.4262%
--- p=16 (m=65536 registers = 65536 bytes, theoretical std error ~ 0.4062%) ---
true N avg |err| max |err| avg err %
1000 2 4 0.2286%
10000 24 37 0.2386%
100000 406 716 0.4061%
1000000 2848 5912 0.2848%
10000000 30595 61486 0.3060%
================================================================
Performance & memory comparison (HLL precision p=14)
================================================================
N | HLL time | HLL est | err % | HLL mem | Map time | Map count | Map mem
--------------+------------+-------------+---------+-----------+------------+-------------+-----------
1,000 | 8.48 us | 995 | 0.500% | 16.00 KiB | 15.27 us | 1,000 | 34.12 KiB
10,000 | 35.88 us | 9,929 | 0.710% | 16.00 KiB | 247.01 us | 10,000 | 272.12 KiB
100,000 | 315.95 us | 101,347 | 1.347% | 16.00 KiB | 1.93 ms | 100,000 | 4.25 MiB
1,000,000 | 1.67 ms | 1,022,694 | 2.269% | 16.00 KiB | 42.34 ms | 1,000,000 | 34.00 MiB
10,000,000 | 13.47 ms | 9,973,671 | 0.263% | 16.00 KiB | 757.35 ms | 10,000,000 | 272.00 MiB
100,000,000 | 130.10 ms | 98,873,421 | 1.127% | 16.00 KiB | 15.38 s | 100,000,000 | 2.13 GiB
1,000,000,000 | 1.30 s | 1,001,600,498 | 0.160% | 16.00 KiB | 103.30 s | 1,000,000,000 | 34.00 GiB
Notes:
* HLL memory is constant (2^p bytes) regardless of N.
* Map memory is O(N); shown is peak live bytes including resize spikes.
* HLL estimate is probabilistic; Map count is exact.
Headline numbers at 1 billion distinct elements:
| Metric | HyperLogLog | Hashmap set | Ratio (HLL vs map) |
|---|---|---|---|
| Time | 1.30 s | 103.30 s | ~79.5x faster |
| Peak memory | 16 KiB | 34 GiB | ~2,100,000x smaller |
| Relative error | 0.16% | exact | (probabilistic vs exact) |
- HyperLogLog memory is constant - 16 KiB regardless of N. Hashmap memory
grows linearly (
~36 bytesper element including resize spikes). - HyperLogLog is dramatically faster at scale: the crossover where HLL beats the hashmap is already at N=1,000, and the gap widens with N. At 1B elements HLL is ~70.5x faster.
- Error is small and bounded: with p=14 the observed error stays within
~2.3% (single trial), matching the predicted
1.04/sqrt(16384) ~= 0.81%standard error. Largerptrades a little more memory for less error.
Theoretical standard error 1.04/sqrt(m) vs observed average relative error:
| p | m (registers) | Memory | Theoretical SE | Observed avg error range |
|---|---|---|---|---|
| 10 | 1,024 | 1 KiB | 3.250% | 1.98%-3.69% |
| 12 | 4,096 | 4 KiB | 1.625% | 1.09%-3.75% |
| 14 | 16,384 | 16 KiB | 0.812% | 0.34%-0.64% |
| 16 | 65,536 | 64 KiB | 0.406% | 0.23%-0.41% |
Choosing p: double p to halve the error, at 2x the (still tiny) memory.
Each element is hashed to a 64-bit value. The top p bits select one of
m = 2^p registers; in that register we store the position of the leftmost
1-bit in the remaining 64-p bits (its "rank"). Hashes act like uniform random
numbers, so the maximum rank in a register grows like log2(count); averaging
across all m registers and applying a bias correction yields the estimate.
See ARCHITECTURE.txt for a full code walkthrough.
MIT Open Source License
Best regards,
Joao Carvalho