xs/hll.xs

filter: Statementstmt 96.0% 49 / 51 Branchbran 63.6% 28 / 44 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 81.0% 77 / 95 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/ring.xs ↑ Summary xs/cache.xs »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); 0 34 34
135 34 ▶ RETVAL = (UV)h->p;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!h) croak("Shared::Arena::HyperLogLog: this sketch is released"); 0 34 34
152 34 ▶ EXTEND(SP, 10);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (h) { sa_hll_free(h); sv_setiv(SvRV(self), 0); } 175 0 175
« xs/ring.xs ↑ Summary xs/cache.xs »