| 1 |
|
| # Shared::Arena::HyperLogLog - how many distinct, in a few kilobytes. |
| 2 |
|
| # |
| 3 |
|
| # The third sketch. Bloom and cuckoo answer "seen it?", count-min answers "how |
| 4 |
|
| # often?", this answers "how many DIFFERENT?" - and an add is a lock-free max on |
| 5 |
|
| # one register, so eight workers hammering one sketch never conflict. |
| 6 |
|
| |
| 7 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena PREFIX = sar_ |
| 8 |
|
| |
| 9 |
|
| # $arena->hll($name, precision => 14) |
| 10 |
|
| # |
| 11 |
|
| # `precision` p gives 2^p registers: the sketch costs 2^p bytes and estimates |
| 12 |
|
| # within about 1.04 / sqrt(2^p) - 0.8% at the default 14, for 16 kilobytes. |
| 13 |
|
| # A later caller names the same precision or inherits it. |
| 14 |
|
| SV * |
| 15 |
|
| sar_hll(self, name, ...) |
| 16 |
|
| SV *self |
| 17 |
|
| SV *name |
| 18 |
|
| PREINIT: |
| 19 |
|
| sa_region *arena; |
| 20 |
|
| sa_reg *e; |
| 21 |
|
| sa_hll *h; |
| 22 |
|
| const char *nm; |
| 23 |
|
| STRLEN nlen; |
| 24 |
209 |
| UV p = 0; /* 0 = not given: inherit or default */ |
| 25 |
|
| uint64_t want; |
| 26 |
209 |
| int err = SA_E_OK; |
| 27 |
|
| I32 i; |
| 28 |
|
| SV *obj; |
| 29 |
|
| CODE: |
| 30 |
209 |
| arena = SA_SELF(sa_region, self); |
| 31 |
209 |
▶ | if (!arena || !arena->map.base) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!arena || !arena->map.base) |
209 |
0 |
209 |
| if (!arena || !arena->map.base) |
0 |
209 |
209 |
|
| 32 |
0 |
| croak("Shared::Arena: this region is released"); |
| 33 |
209 |
| nm = SvPV(name, nlen); |
| 34 |
385 |
▶ | for (i = 2; i + 1 < items; i += 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 2; i + 1 < items; i += 2) { |
176 |
209 |
385 |
|
| 35 |
176 |
| const char *o = SvPV_nolen(ST(i)); |
| 36 |
176 |
▶ | if (strEQ(o, "precision")) p = SvUV(ST(i + 1)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (strEQ(o, "precision")) p = SvUV(ST(i + 1)); |
176 |
0 |
176 |
|
| 37 |
|
| } |
| 38 |
209 |
▶ | if (p && (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P)) |
Branch: 3 branches
| Branch | True | False | Total |
| if (p && (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P)) |
176 |
33 |
209 |
| if (p && (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P)) |
159 |
17 |
176 |
| if (p && (p < SA_HLL_MIN_P || p > SA_HLL_MAX_P)) |
0 |
159 |
159 |
|
| 39 |
17 |
| croak("Shared::Arena: hll precision must be %d to %d, not %lu", |
| 40 |
|
| (int)SA_HLL_MIN_P, (int)SA_HLL_MAX_P, (unsigned long)p); |
| 41 |
|
| /* Like the scoreboard: a caller naming no precision binds to what is |
| 42 |
|
| * there, and only a fresh sketch gets the default. */ |
| 43 |
192 |
▶ | if (p) want = sa_hll_bytes((uint32_t)p); |
Branch: 1 branch
| Branch | True | False | Total |
| if (p) want = sa_hll_bytes((uint32_t)p); |
159 |
33 |
192 |
|
| 44 |
33 |
▶ | else if (sa_find(arena, nm, (size_t)nlen)) want = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| else if (sa_find(arena, nm, (size_t)nlen)) want = 0; |
33 |
0 |
33 |
|
| 45 |
0 |
| else want = sa_hll_bytes(14); |
| 46 |
|
| |
| 47 |
192 |
| e = sa_carve(arena, nm, (size_t)nlen, want, SA_T_HLL, &err); |
| 48 |
192 |
▶ | if (!e) croak("Shared::Arena: the hll '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) croak("Shared::Arena: the hll '%s' %s", nm, sa_strerror(err)); |
17 |
175 |
192 |
|
| 49 |
|
| #if SA_HAVE_ATOMICS |
| 50 |
175 |
| h = sa_hll_bind(arena, e, (uint32_t)p, &err); |
| 51 |
175 |
▶ | if (!h) croak("Shared::Arena: the hll '%s' %s", nm, sa_strerror(err)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena: the hll '%s' %s", nm, sa_strerror(err)); |
0 |
175 |
175 |
|
| 52 |
|
| #else |
| 53 |
|
| croak("Shared::Arena: hll needs atomics this build does not have"); |
| 54 |
|
| #endif |
| 55 |
175 |
| obj = newSV(0); |
| 56 |
175 |
| sv_setref_pv(obj, "Shared::Arena::HyperLogLog", (void *)h); |
| 57 |
175 |
| sv_magicext(SvRV(obj), SvRV(self), PERL_MAGIC_ext, NULL, NULL, 0); |
| 58 |
175 |
| SvREFCNT_inc(SvRV(self)); |
| 59 |
175 |
| RETVAL = obj; |
| 60 |
|
| OUTPUT: |
| 61 |
|
| RETVAL |
| 62 |
|
| |
| 63 |
|
| MODULE = Shared::Arena PACKAGE = Shared::Arena::HyperLogLog PREFIX = sah_ |
| 64 |
|
| |
| 65 |
|
| # $hll->add($key) - count a key. Adding it again changes nothing. Lock-free. |
| 66 |
|
| # Returns true if the sketch changed, which is a hint and not a membership |
| 67 |
|
| # answer: a key can leave the sketch unchanged because another key already |
| 68 |
|
| # raised its register. |
| 69 |
|
| int |
| 70 |
|
| sah_add(self, key) |
| 71 |
|
| SV *self |
| 72 |
|
| SV *key |
| 73 |
|
| PREINIT: |
| 74 |
|
| sa_hll *h; |
| 75 |
|
| const char *k; |
| 76 |
|
| STRLEN kl; |
| 77 |
|
| CODE: |
| 78 |
1108917 |
| h = SA_SELF(sa_hll, self); |
| 79 |
1108917 |
▶ | if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
1108917 |
1108917 |
|
| 80 |
1108917 |
| k = SvPV(key, kl); |
| 81 |
1108917 |
| RETVAL = sa_hll_add(h, k, (size_t)kl); |
| 82 |
|
| OUTPUT: |
| 83 |
|
| RETVAL |
| 84 |
|
| |
| 85 |
|
| # $hll->count - the estimate of how many distinct keys have been added, across |
| 86 |
|
| # every process that added to this sketch. |
| 87 |
|
| NV |
| 88 |
|
| sah_count(self) |
| 89 |
|
| SV *self |
| 90 |
|
| PREINIT: |
| 91 |
|
| sa_hll *h; |
| 92 |
|
| CODE: |
| 93 |
228 |
| h = SA_SELF(sa_hll, self); |
| 94 |
228 |
▶ | if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
228 |
228 |
|
| 95 |
228 |
| RETVAL = sa_hll_count(h); |
| 96 |
|
| OUTPUT: |
| 97 |
|
| RETVAL |
| 98 |
|
| |
| 99 |
|
| # $hll->merge($other) - fold another sketch of the same precision into this |
| 100 |
|
| # one, so this one then estimates the UNION of what both saw. Lock-free; the |
| 101 |
|
| # other is not changed. Croaks on a precision mismatch, which is a bug. |
| 102 |
|
| void |
| 103 |
|
| sah_merge(self, other) |
| 104 |
|
| SV *self |
| 105 |
|
| SV *other |
| 106 |
|
| PREINIT: |
| 107 |
|
| sa_hll *h, *o; |
| 108 |
|
| CODE: |
| 109 |
34 |
| h = SA_SELF(sa_hll, self); |
| 110 |
34 |
| o = SA_SELF(sa_hll, other); |
| 111 |
34 |
▶ | if (!h || !o) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h || !o) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
34 |
0 |
34 |
| if (!h || !o) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
34 |
34 |
|
| 112 |
34 |
▶ | if (!sa_hll_merge(h, o)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_hll_merge(h, o)) |
17 |
17 |
34 |
|
| 113 |
17 |
| croak("Shared::Arena::HyperLogLog: cannot merge precision %u into %u", |
| 114 |
|
| (unsigned)o->p, (unsigned)h->p); |
| 115 |
|
| |
| 116 |
|
| # $hll->reset - forget everything. |
| 117 |
|
| void |
| 118 |
|
| sah_reset(self) |
| 119 |
|
| SV *self |
| 120 |
|
| PREINIT: |
| 121 |
|
| sa_hll *h; |
| 122 |
|
| CODE: |
| 123 |
17 |
| h = SA_SELF(sa_hll, self); |
| 124 |
17 |
▶ | if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
17 |
17 |
|
| 125 |
17 |
| sa_hll_reset(h); |
| 126 |
|
| |
| 127 |
|
| UV |
| 128 |
|
| sah_precision(self) |
| 129 |
|
| SV *self |
| 130 |
|
| PREINIT: |
| 131 |
|
| sa_hll *h; |
| 132 |
|
| CODE: |
| 133 |
34 |
| h = SA_SELF(sa_hll, self); |
| 134 |
34 |
▶ | if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
34 |
34 |
|
| 135 |
34 |
▶ | RETVAL = (UV)h->p; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = (UV)h->p; |
0 |
34 |
34 |
|
| 136 |
|
| OUTPUT: |
| 137 |
|
| RETVAL |
| 138 |
|
| |
| 139 |
|
| # precision / registers / bytes / filled / error |
| 140 |
|
| # |
| 141 |
|
| # `filled` is how many registers are non-zero; `error` is the sketch's |
| 142 |
|
| # standard relative error, 1.04 / sqrt(registers), the number to quote beside |
| 143 |
|
| # any count. |
| 144 |
|
| void |
| 145 |
|
| sah_stats(self) |
| 146 |
|
| SV *self |
| 147 |
|
| PREINIT: |
| 148 |
|
| sa_hll *h; |
| 149 |
|
| PPCODE: |
| 150 |
34 |
| h = SA_SELF(sa_hll, self); |
| 151 |
34 |
▶ | if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); |
0 |
34 |
34 |
|
| 152 |
34 |
▶ | EXTEND(SP, 10); |
Branch: 1 branch
| Branch | True | False | Total |
| EXTEND(SP, 10); |
0 |
34 |
34 |
|
| 153 |
34 |
| mPUSHp("precision", 9); mPUSHu((UV)h->p); |
| 154 |
34 |
| mPUSHp("registers", 9); mPUSHu((UV)h->m); |
| 155 |
34 |
| mPUSHp("bytes", 5); mPUSHu((UV)sa_hll_bytes(h->p)); |
| 156 |
34 |
| mPUSHp("filled", 6); mPUSHu((UV)sa_hll_filled(h)); |
| 157 |
34 |
| mPUSHp("error", 5); mPUSHn(1.04 / sqrt((double)h->m)); |
| 158 |
|
| |
| 159 |
|
| void |
| 160 |
|
| sah_DESTROY(self) |
| 161 |
|
| SV *self |
| 162 |
|
| PREINIT: |
| 163 |
|
| sa_hll *h; |
| 164 |
|
| CODE: |
| 165 |
175 |
| h = SA_SELF(sa_hll, self); |
| 166 |
175 |
▶ | if (h) { sa_hll_free(h); sv_setiv(SvRV(self), 0); } |
Branch: 1 branch
| Branch | True | False | Total |
| if (h) { sa_hll_free(h); sv_setiv(SvRV(self), 0); } |
175 |
0 |
175 |
|