include/sa/sa_hll.h

filter: Statementstmt 91.3% 106 / 116 Branchbran 60.3% 64 / 106 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 76.5% 170 / 222 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/cms.xs ↑ Summary xs/frozen.xs »
1 #ifndef SA_HLL_H
2 #define SA_HLL_H
3  
4 /* sa_hll.h - how many DISTINCT, in a few kilobytes. Perl-free.
5 *
6 * ---- the third question --------------------------------------------------
7 *
8 * The bloom and cuckoo filters answer "have I seen this key?"; the count-min
9 * sketch answers "how often?". Neither answers "HOW MANY DIFFERENT ones?" -
10 * distinct visitors today, distinct client addresses behind one token, distinct
11 * URLs a crawler touched. A map of every key is unbounded, and counting per
12 * worker is wrong by construction: one visitor lands on eight workers and is
13 * counted eight times.
14 *
15 * HyperLogLog is the standard answer. Hash each key; the top p bits pick one of
16 * m = 2^p registers, and the register keeps the LONGEST run of leading zeros
17 * (plus one) ever seen in the rest of the hash. A run of k leading zeros is a
18 * 1-in-2^k event, so the longest run seen is a log-scale witness to how many
19 * different values have been hashed, and m registers averaged (harmonically)
20 * turn a noisy witness into an estimate with a relative error of about
21 * 1.04 / sqrt(m): 0.8% at p = 14, which costs 16 kilobytes.
22 *
23 * ---- why this is the most shared-memory-shaped tenant in the dist -------
24 *
25 * The write is register[i] = max(register[i], rank). A MAX is commutative and
26 * idempotent: it does not matter in what order eight processes apply theirs,
27 * nor if one applies the same one twice, and there is no read-modify-write
28 * sequence to tear. So an add is a compare-and-swap on one register and takes
29 * no lock, no stripe, no seqlock; two processes racing on one register both
30 * land on the larger value. Every other tenant has to reason about ordering;
31 * this one has nothing to order.
32 *
33 * Two sketches MERGE the same way, register by register, so a union is cheap
34 * and needs no coordination either.
35 *
36 * ---- the hash ----------------------------------------------------------
37 *
38 * The arena's FNV-1a is fine for choosing a stripe and useless here: its low
39 * bits avalanche poorly, and the rank is the leading zeros of exactly those
40 * bits. So the FNV word goes through a 64-bit finaliser (the murmur3 fmix)
41 * before it is split, which is cheap and gives every bit a fair coin.
42 *
43 * ---- the registers are bytes, the atomics are words ----------------------
44 *
45 * A register never exceeds 64 - p + 1, so a byte holds it and the sketch stays
46 * small, which is its whole point. The portable atomics here are 32- and
47 * 64-bit, so the max is done as a CAS on the 32-bit word that contains the
48 * byte: read the word, if our byte is already >= rank stop, else swap in the
49 * word with that byte raised. A neighbour byte changing underneath us fails
50 * the CAS and we re-read: the loop converges because every iteration either
51 * stops or raises a byte, and bytes only ever go up.
52 *
53 * Needs sa_arena.h.
54 */
55  
56 #include <math.h>
57 #include "sa/sa_arena.h"
58  
59 #define SA_HLL_MAGIC 0x4C4C4C48u /* 'H','L','L','L' little-endian */
60  
61 #define SA_HLL_MIN_P 4
62 #define SA_HLL_MAX_P 18
63  
64 typedef struct {
65 volatile uint32_t magic; /* published LAST at init */
66 uint32_t p; /* precision: m = 2^p registers */
67 uint64_t regs_off; /* from the SKETCH's base */
68 volatile unsigned char locks[SA_LOCK_STRIPES]; /* init only */
69 } sa_hll_hdr;
70  
71 #ifndef SA_HLL_FWD
72 #define SA_HLL_FWD
73 typedef struct sa_hll sa_hll;
74 #endif
75  
76 struct sa_hll {
77 sa_region *arena;
78 sa_hll_hdr *hdr;
79 volatile uint32_t *words; /* the registers, as words for the CAS */
80 uint32_t p;
81 uint64_t m; /* 2^p */
82 };
83  
84 661 static uint64_t sa_hll_regs_bytes(uint32_t p) {
85 661 return sa_align_up(((uint64_t)1 << p) + 3u) & ~(uint64_t)3u;
86 }
87  
88 661 static uint64_t sa_hll_bytes(uint32_t p) {
89 661 return sa_align_up((uint64_t)sizeof(sa_hll_hdr)) + sa_hll_regs_bytes(p);
90 }
91  
92 /* murmur3's 64-bit finaliser: every input bit affects every output bit. */
93 1111917 static uint64_t sa_hll_mix(uint64_t h) {
94 1111917 h ^= h >> 33;
95 1111917 h *= 0xff51afd7ed558ccdULL;
96 1111917 h ^= h >> 33;
97 1111917 h *= 0xc4ceb9fe1a85ec53ULL;
98 1111917 h ^= h >> 33;
99 1111917 return h;
100 }
101  
102 1111917 static uint64_t sa_hll_hash(const void *key, size_t klen) {
103 1111917 return sa_hll_mix(sa_at_fnv(key, klen));
104 }
105  
106 /* Leading zeros of a 64-bit word, portable; only called with w != 0. */
107 1111917 static uint32_t sa_hll_clz64(uint64_t w) {
108 1111917 uint32_t n = 0;
109 1111917 ▶ if (!(w & 0xFFFFFFFF00000000ULL)) { n += 32; w <<= 32; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0xFFFFFFFF00000000ULL)) { n += 32; w <<= 32; } 0 1111917 1111917
110 1111917 ▶ if (!(w & 0xFFFF000000000000ULL)) { n += 16; w <<= 16; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0xFFFF000000000000ULL)) { n += 16; w <<= 16; } 34 1111883 1111917
111 1111917 ▶ if (!(w & 0xFF00000000000000ULL)) { n += 8; w <<= 8; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0xFF00000000000000ULL)) { n += 8; w <<= 8; } 4361 1107556 1111917
112 1111917 ▶ if (!(w & 0xF000000000000000ULL)) { n += 4; w <<= 4; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0xF000000000000000ULL)) { n += 4; w <<= 4; } 64927 1046990 1111917
113 1111917 ▶ if (!(w & 0xC000000000000000ULL)) { n += 2; w <<= 2; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0xC000000000000000ULL)) { n += 2; w <<= 2; } 223547 888370 1111917
114 1111917 ▶ if (!(w & 0x8000000000000000ULL)) { n += 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!(w & 0x8000000000000000ULL)) { n += 1; } 365771 746146 1111917
115 1111917 return n;
116 }
117  
118 #if SA_HAVE_ATOMICS
119  
120 178 static sa_hll *sa_hll_bind(sa_region *arena, sa_reg *e, uint32_t p, int *err) {
121 sa_hll *h;
122 sa_hll_hdr *hd;
123 uint64_t hash;
124  
125 178 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 178 0 178
126 178 ▶ if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 3 branches
BranchTrueFalseTotal
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 178 0 178
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 178 178
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
127  
128 178 hd = (sa_hll_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_hll_hdr));
129 178 ▶ if (!hd) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!hd) { if (err) *err = SA_E_NOENT; return NULL; } 0 178 178
if (!hd) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
130  
131 178 ▶ if (sa_at_load32_acq(&hd->magic) != SA_HLL_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&hd->magic) != SA_HLL_MAGIC) { 144 34 178
132 144 hash = sa_at_fnv(e->name, strlen(e->name));
133 144 ▶ if (sa_at_lock(hd->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(hd->locks, hash)) { 144 0 144
134 144 ▶ if (sa_at_load32_acq(&hd->magic) != SA_HLL_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&hd->magic) != SA_HLL_MAGIC) { 144 0 144
135 144 ▶ if (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P
Branch: 2 branches
BranchTrueFalseTotal
if (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P 144 0 144
if (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P 144 0 144
136 144 ▶ || sa_hll_bytes(p) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_hll_bytes(p) > e->len) { 0 144 144
137 0 sa_at_unlock(hd->locks, hash);
138 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
139 0 return NULL;
140 }
141 144 memset((void *)hd, 0, (size_t)sa_hll_bytes(p));
142 144 hd->p = p;
143 144 hd->regs_off = sa_align_up((uint64_t)sizeof(sa_hll_hdr));
144 144 sa_at_store32_rel(&hd->magic, SA_HLL_MAGIC);
145 }
146 144 sa_at_unlock(hd->locks, hash);
147 }
148 144 ▶ if (!sa_wait_magic32(&hd->magic, SA_HLL_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&hd->magic, SA_HLL_MAGIC)) { 0 144 144
149 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
150 0 return NULL;
151 }
152 }
153  
154 /* The precision in the header is somebody else's number: a header claiming
155 * p = 60 would put every register read past the mapping. Check it, and a
156 * caller that asked for a precision must have asked for THIS one. */
157 178 ▶ if (hd->p < SA_HLL_MIN_P || hd->p > SA_HLL_MAX_P
Branch: 2 branches
BranchTrueFalseTotal
if (hd->p < SA_HLL_MIN_P || hd->p > SA_HLL_MAX_P 178 0 178
if (hd->p < SA_HLL_MIN_P || hd->p > SA_HLL_MAX_P 178 0 178
158 178 ▶ || sa_hll_bytes(hd->p) > e->len
Branch: 1 branch
BranchTrueFalseTotal
|| sa_hll_bytes(hd->p) > e->len 178 0 178
159 178 ▶ || hd->regs_off != sa_align_up((uint64_t)sizeof(sa_hll_hdr))) {
Branch: 1 branch
BranchTrueFalseTotal
|| hd->regs_off != sa_align_up((uint64_t)sizeof(sa_hll_hdr))) { 0 178 178
160 0 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 0 0 0
161 0 return NULL;
162 }
163 178 ▶ if (p && hd->p != p) { if (err) *err = SA_E_SHAPE; return NULL; }
Branch: 3 branches
BranchTrueFalseTotal
if (p && hd->p != p) { if (err) *err = SA_E_SHAPE; return NULL; } 144 34 178
if (p && hd->p != p) { if (err) *err = SA_E_SHAPE; return NULL; } 0 144 144
if (p && hd->p != p) { if (err) *err = SA_E_SHAPE; return NULL; } 0 0 0
164  
165 178 h = (sa_hll *)calloc(1, sizeof(sa_hll));
166 178 ▶ if (!h) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { if (err) *err = SA_E_NOMEM; return NULL; } 0 178 178
if (!h) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
167 178 h->arena = arena;
168 178 h->hdr = hd;
169 178 h->words = (volatile uint32_t *)((char *)hd + (size_t)hd->regs_off);
170 178 h->p = hd->p;
171 178 h->m = (uint64_t)1 << hd->p;
172 178 return h;
173 }
174  
175 178 static void sa_hll_free(sa_hll *h) { free(h); }
176  
177 /* Raise register `idx` to at least `rank`. Lock-free; see the header comment
178 * for why the CAS is on the containing word. Returns 1 if the register moved,
179 * 0 if it was already at least that high - which is what a repeated key is. */
180 1309044 static int sa_hll_raise(sa_hll *h, uint64_t idx, uint32_t rank) {
181 1309044 volatile uint32_t *w = &h->words[idx >> 2];
182 1309044 uint32_t shift = (uint32_t)(idx & 3u) * 8u;
183 6 for (;;) {
184 1309050 uint32_t old = sa_at_load32_acq(w);
185 1309050 uint32_t cur = (old >> shift) & 0xFFu;
186 uint32_t neu;
187 1309050 ▶ if (cur >= rank) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (cur >= rank) return 0; 597015 712035 1309050
188 712035 neu = (old & ~(0xFFu << shift)) | (rank << shift);
189 712035 ▶ if (sa_at_cas32(w, old, neu)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_cas32(w, old, neu)) return 1; 712029 6 712035
190 }
191 }
192  
193 /* Add a key. Returns 1 if the sketch changed, 0 if this key (or one that
194 * collides with it) had no effect - NOT a membership answer, only a hint. */
195 1111917 static int sa_hll_add(sa_hll *h, const void *key, size_t klen) {
196 uint64_t x, idx, rest;
197 uint32_t rank;
198 1111917 ▶ if (!h) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return 0; 0 1111917 1111917
199 1111917 x = sa_hll_hash(key, klen);
200 1111917 idx = x >> (64 - h->p);
201 1111917 rest = (x << h->p) | ((uint64_t)1 << (h->p - 1)); /* cap the run */
202 1111917 rank = sa_hll_clz64(rest) + 1;
203 1111917 return sa_hll_raise(h, idx, rank);
204 }
205  
206 /* ---- the estimate ----------------------------------------------------------
207 *
208 * The original paper's estimator is a harmonic mean with two patches: linear
209 * counting below 2.5m, and a raw mean above. The seam between them has a hump
210 * - measured here, +1% at n = 3m - which HyperLogLog++ flattens with tables of
211 * empirically fitted constants per precision.
212 *
213 * This is Ertl's estimator (2017) instead. It works from the HISTOGRAM of
214 * register values, with two closed-form series (sigma for the empty registers,
215 * tau for the saturated ones) that account exactly for the ends of the range
216 * that bias the harmonic mean, so there is no seam, no switch, and no table.
217 * The two loops each converge in a few dozen iterations. */
218  
219 233 static double sa_hll_sigma(double x) {
220 233 double y = 1.0, z = x, zp;
221 233 ▶ if (x == 1.0) return HUGE_VAL; /* every register empty: n = 0 */
Branch: 1 branch
BranchTrueFalseTotal
if (x == 1.0) return HUGE_VAL; /* every register empty: n = 0 */ 36 197 233
222 1545 ▶ do { x *= x; zp = z; z += x * y; y += y; } while (z != zp);
Branch: 1 branch
BranchTrueFalseTotal
do { x *= x; zp = z; z += x * y; y += y; } while (z != zp); 1348 197 1545
223 197 return z;
224 }
225  
226 233 static double sa_hll_tau(double x) {
227 233 double y = 1.0, z = 1.0 - x, zp;
228 233 ▶ if (x == 0.0 || x == 1.0) return 0.0;
Branch: 2 branches
BranchTrueFalseTotal
if (x == 0.0 || x == 1.0) return 0.0; 233 0 233
if (x == 0.0 || x == 1.0) return 0.0; 233 0 233
229 0 do { x = sqrt(x); zp = z; y *= 0.5; z -= (1.0 - x) * (1.0 - x) * y; }
230 0 ▶ while (z != zp);
Branch: 1 branch
BranchTrueFalseTotal
while (z != zp); 0 0 0
231 0 return z / 3.0;
232 }
233  
234 233 static double sa_hll_count(sa_hll *h) {
235 uint64_t hist[66]; /* a register holds 0 .. 64 - p + 1 */
236 uint64_t i;
237 uint32_t q, k;
238 double m, z;
239  
240 233 ▶ if (!h) return 0.0;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return 0.0; 0 233 233
241 233 memset(hist, 0, sizeof hist);
242 3298537 ▶ for (i = 0; i < h->m; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->m; i++) { 3298304 233 3298537
243 3298304 uint32_t r = (sa_at_load32_acq(&h->words[i >> 2]) >> ((i & 3u) * 8u))
244 & 0xFFu;
245 3298304 ▶ if (r > 65) r = 65; /* a corrupt byte cannot index past it */
Branch: 1 branch
BranchTrueFalseTotal
if (r > 65) r = 65; /* a corrupt byte cannot index past it */ 0 3298304 3298304
246 3298304 hist[r]++;
247 }
248 233 m = (double)h->m;
249 233 q = 64 - h->p;
250 233 z = m * sa_hll_tau(1.0 - (double)hist[q + 1] / m);
251 11975 ▶ for (k = q; k >= 1; k--) z = 0.5 * (z + (double)hist[k]);
Branch: 1 branch
BranchTrueFalseTotal
for (k = q; k >= 1; k--) z = 0.5 * (z + (double)hist[k]); 11742 233 11975
252 233 z += m * sa_hll_sigma((double)hist[0] / m);
253 233 return m * m / (2.0 * log(2.0) * z); /* alpha_inf = 1 / (2 ln 2) */
254 }
255  
256 /* Fold `src` into `dst`: register-wise max. Both must share a precision. The
257 * result is the sketch of the UNION of everything either saw. Returns 0 on a
258 * precision mismatch, 1 otherwise. */
259 35 static int sa_hll_merge(sa_hll *dst, sa_hll *src) {
260 uint64_t i;
261 35 ▶ if (!dst || !src || dst->p != src->p) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!dst || !src || dst->p != src->p) return 0; 35 0 35
if (!dst || !src || dst->p != src->p) return 0; 35 0 35
if (!dst || !src || dst->p != src->p) return 0; 17 18 35
262 279570 ▶ for (i = 0; i < src->m; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < src->m; i++) { 279552 18 279570
263 279552 uint32_t r = (sa_at_load32_acq(&src->words[i >> 2]) >> ((i & 3u) * 8u))
264 & 0xFFu;
265 279552 ▶ if (r) sa_hll_raise(dst, i, r);
Branch: 1 branch
BranchTrueFalseTotal
if (r) sa_hll_raise(dst, i, r); 197127 82425 279552
266 }
267 18 return 1;
268 }
269  
270 /* Registers set (non-zero), for a caller wondering how full the sketch is. */
271 36 static uint64_t sa_hll_filled(sa_hll *h) {
272 36 uint64_t i, n = 0;
273 36 ▶ if (!h) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return 0; 0 36 36
274 559140 ▶ for (i = 0; i < h->m; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->m; i++) { 559104 36 559140
275 559104 ▶ if ((sa_at_load32_acq(&h->words[i >> 2]) >> ((i & 3u) * 8u)) & 0xFFu)
Branch: 1 branch
BranchTrueFalseTotal
if ((sa_at_load32_acq(&h->words[i >> 2]) >> ((i & 3u) * 8u)) & 0xFFu) 652 558452 559104
276 652 n++;
277 }
278 36 return n;
279 }
280  
281 /* Forget everything. An add racing a reset lands either before it (lost) or
282 * after (kept); a sketch is a statistic, and a reset is a moment, not a
283 * transaction, so that is the honest answer. */
284 18 static void sa_hll_reset(sa_hll *h) {
285 uint64_t i, nw;
286 18 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 18 18
287 18 nw = (h->m + 3u) >> 2;
288 69906 ▶ for (i = 0; i < nw; i++) sa_at_store32_rel(&h->words[i], 0);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nw; i++) sa_at_store32_rel(&h->words[i], 0); 69888 18 69906
289 }
290  
291 #else /* !SA_HAVE_ATOMICS */
292  
293 /* No atomics: no sketch. Defined for the ABI table; inert. */
294 static sa_hll *sa_hll_bind(sa_region *arena, sa_reg *e, uint32_t p, int *err) {
295 (void)arena; (void)e; (void)p;
296 if (err) *err = SA_E_NOATOMICS;
297 return NULL;
298 }
299 static void sa_hll_free(sa_hll *h) { free(h); }
300 static int sa_hll_add(sa_hll *h, const void *key, size_t klen) {
301 (void)h; (void)key; (void)klen; return 0;
302 }
303 static double sa_hll_count(sa_hll *h) { (void)h; return 0.0; }
304 static int sa_hll_merge(sa_hll *dst, sa_hll *src) { (void)dst; (void)src; return 0; }
305 static uint64_t sa_hll_filled(sa_hll *h) { (void)h; return 0; }
306 static void sa_hll_reset(sa_hll *h) { (void)h; }
307  
308 #endif /* SA_HAVE_ATOMICS */
309  
310 #endif /* SA_HLL_H */
« xs/cms.xs ↑ Summary xs/frozen.xs »