aboutsummaryrefslogtreecommitdiff
path: root/examples/redis-unstable/src/hyperloglog.c
diff options
context:
space:
mode:
Diffstat (limited to 'examples/redis-unstable/src/hyperloglog.c')
-rw-r--r--examples/redis-unstable/src/hyperloglog.c2099
1 files changed, 0 insertions, 2099 deletions
diff --git a/examples/redis-unstable/src/hyperloglog.c b/examples/redis-unstable/src/hyperloglog.c
deleted file mode 100644
index 05a5152..0000000
--- a/examples/redis-unstable/src/hyperloglog.c
+++ /dev/null
@@ -1,2099 +0,0 @@
1/* hyperloglog.c - Redis HyperLogLog probabilistic cardinality approximation.
2 * This file implements the algorithm and the exported Redis commands.
3 *
4 * Copyright (c) 2014-Present, Redis Ltd.
5 * All rights reserved.
6 *
7 * Copyright (c) 2024-present, Valkey contributors.
8 * All rights reserved.
9 *
10 * Licensed under your choice of (a) the Redis Source Available License 2.0
11 * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the
12 * GNU Affero General Public License v3 (AGPLv3).
13 *
14 * Portions of this file are available under BSD3 terms; see REDISCONTRIBUTIONS for more information.
15 */
16
17#include "server.h"
18
19#include <stdint.h>
20#include <math.h>
21
22#ifdef HAVE_AVX2
23/* Define __MM_MALLOC_H to prevent importing the memory aligned
24 * allocation functions, which we don't use. */
25#define __MM_MALLOC_H
26#include <immintrin.h>
27#endif
28
29#ifdef HAVE_AARCH64_NEON
30#include <arm_neon.h>
31#endif
32
33#undef MAX
34#define MAX(a, b) ((a) > (b) ? (a) : (b))
35
36/* The Redis HyperLogLog implementation is based on the following ideas:
37 *
38 * * The use of a 64 bit hash function as proposed in [1], in order to estimate
39 * cardinalities larger than 10^9, at the cost of just 1 additional bit per
40 * register.
41 * * The use of 16384 6-bit registers for a great level of accuracy, using
42 * a total of 12k per key.
43 * * The use of the Redis string data type. No new type is introduced.
44 * * No attempt is made to compress the data structure as in [1]. Also the
45 * algorithm used is the original HyperLogLog Algorithm as in [2], with
46 * the only difference that a 64 bit hash function is used, so no correction
47 * is performed for values near 2^32 as in [1].
48 *
49 * [1] Heule, Nunkesser, Hall: HyperLogLog in Practice: Algorithmic
50 * Engineering of a State of The Art Cardinality Estimation Algorithm.
51 *
52 * [2] P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The
53 * analysis of a near-optimal cardinality estimation algorithm.
54 *
55 * Redis uses two representations:
56 *
57 * 1) A "dense" representation where every entry is represented by
58 * a 6-bit integer.
59 * 2) A "sparse" representation using run length compression suitable
60 * for representing HyperLogLogs with many registers set to 0 in
61 * a memory efficient way.
62 *
63 *
64 * HLL header
65 * ===
66 *
67 * Both the dense and sparse representation have a 16 byte header as follows:
68 *
69 * +------+---+-----+----------+
70 * | HYLL | E | N/U | Cardin. |
71 * +------+---+-----+----------+
72 *
73 * The first 4 bytes are a magic string set to the bytes "HYLL".
74 * "E" is one byte encoding, currently set to HLL_DENSE or
75 * HLL_SPARSE. N/U are three not used bytes.
76 *
77 * The "Cardin." field is a 64 bit integer stored in little endian format
78 * with the latest cardinality computed that can be reused if the data
79 * structure was not modified since the last computation (this is useful
80 * because there are high probabilities that HLLADD operations don't
81 * modify the actual data structure and hence the approximated cardinality).
82 *
83 * When the most significant bit in the most significant byte of the cached
84 * cardinality is set, it means that the data structure was modified and
85 * we can't reuse the cached value that must be recomputed.
86 *
87 * Dense representation
88 * ===
89 *
90 * The dense representation used by Redis is the following:
91 *
92 * +--------+--------+--------+------// //--+
93 * |11000000|22221111|33333322|55444444 .... |
94 * +--------+--------+--------+------// //--+
95 *
96 * The 6 bits counters are encoded one after the other starting from the
97 * LSB to the MSB, and using the next bytes as needed.
98 *
99 * Sparse representation
100 * ===
101 *
102 * The sparse representation encodes registers using a run length
103 * encoding composed of three opcodes, two using one byte, and one using
104 * of two bytes. The opcodes are called ZERO, XZERO and VAL.
105 *
106 * ZERO opcode is represented as 00xxxxxx. The 6-bit integer represented
107 * by the six bits 'xxxxxx', plus 1, means that there are N registers set
108 * to 0. This opcode can represent from 1 to 64 contiguous registers set
109 * to the value of 0.
110 *
111 * XZERO opcode is represented by two bytes 01xxxxxx yyyyyyyy. The 14-bit
112 * integer represented by the bits 'xxxxxx' as most significant bits and
113 * 'yyyyyyyy' as least significant bits, plus 1, means that there are N
114 * registers set to 0. This opcode can represent from 0 to 16384 contiguous
115 * registers set to the value of 0.
116 *
117 * VAL opcode is represented as 1vvvvvxx. It contains a 5-bit integer
118 * representing the value of a register, and a 2-bit integer representing
119 * the number of contiguous registers set to that value 'vvvvv'.
120 * To obtain the value and run length, the integers vvvvv and xx must be
121 * incremented by one. This opcode can represent values from 1 to 32,
122 * repeated from 1 to 4 times.
123 *
124 * The sparse representation can't represent registers with a value greater
125 * than 32, however it is very unlikely that we find such a register in an
126 * HLL with a cardinality where the sparse representation is still more
127 * memory efficient than the dense representation. When this happens the
128 * HLL is converted to the dense representation.
129 *
130 * The sparse representation is purely positional. For example a sparse
131 * representation of an empty HLL is just: XZERO:16384.
132 *
133 * An HLL having only 3 non-zero registers at position 1000, 1020, 1021
134 * respectively set to 2, 3, 3, is represented by the following three
135 * opcodes:
136 *
137 * XZERO:1000 (Registers 0-999 are set to 0)
138 * VAL:2,1 (1 register set to value 2, that is register 1000)
139 * ZERO:19 (Registers 1001-1019 set to 0)
140 * VAL:3,2 (2 registers set to value 3, that is registers 1020,1021)
141 * XZERO:15362 (Registers 1022-16383 set to 0)
142 *
143 * In the example the sparse representation used just 7 bytes instead
144 * of 12k in order to represent the HLL registers. In general for low
145 * cardinality there is a big win in terms of space efficiency, traded
146 * with CPU time since the sparse representation is slower to access.
147 *
148 * The following table shows average cardinality vs bytes used, 100
149 * samples per cardinality (when the set was not representable because
150 * of registers with too big value, the dense representation size was used
151 * as a sample).
152 *
153 * 100 267
154 * 200 485
155 * 300 678
156 * 400 859
157 * 500 1033
158 * 600 1205
159 * 700 1375
160 * 800 1544
161 * 900 1713
162 * 1000 1882
163 * 2000 3480
164 * 3000 4879
165 * 4000 6089
166 * 5000 7138
167 * 6000 8042
168 * 7000 8823
169 * 8000 9500
170 * 9000 10088
171 * 10000 10591
172 *
173 * The dense representation uses 12288 bytes, so there is a big win up to
174 * a cardinality of ~2000-3000. For bigger cardinalities the constant times
175 * involved in updating the sparse representation is not justified by the
176 * memory savings. The exact maximum length of the sparse representation
177 * when this implementation switches to the dense representation is
178 * configured via the define server.hll_sparse_max_bytes.
179 */
180
181struct hllhdr {
182 char magic[4]; /* "HYLL" */
183 uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
184 uint8_t notused[3]; /* Reserved for future use, must be zero. */
185 uint8_t card[8]; /* Cached cardinality, little endian. */
186 uint8_t registers[]; /* Data bytes. */
187};
188
189/* The cached cardinality MSB is used to signal validity of the cached value. */
190#define HLL_INVALIDATE_CACHE(hdr) (hdr)->card[7] |= (1<<7)
191#define HLL_VALID_CACHE(hdr) (((hdr)->card[7] & (1<<7)) == 0)
192
193#define HLL_P 14 /* The greater is P, the smaller the error. */
194#define HLL_Q (64-HLL_P) /* The number of bits of the hash value used for
195 determining the number of leading zeros. */
196#define HLL_REGISTERS (1<<HLL_P) /* With P=14, 16384 registers. */
197#define HLL_P_MASK (HLL_REGISTERS-1) /* Mask to index register. */
198#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
199#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
200#define HLL_HDR_SIZE sizeof(struct hllhdr)
201#define HLL_DENSE_SIZE (HLL_HDR_SIZE+((HLL_REGISTERS*HLL_BITS+7)/8))
202#define HLL_DENSE 0 /* Dense encoding. */
203#define HLL_SPARSE 1 /* Sparse encoding. */
204#define HLL_RAW 255 /* Only used internally, never exposed. */
205#define HLL_MAX_ENCODING 1
206
207static char *invalid_hll_err = "-INVALIDOBJ Corrupted HLL object detected";
208
209#if defined(HAVE_AVX2) || defined(HAVE_AARCH64_NEON)
210static int simd_enabled = 1;
211#endif
212
213#ifdef HAVE_AVX2
214#define HLL_USE_AVX2 (simd_enabled && __builtin_cpu_supports("avx2"))
215#else
216#define HLL_USE_AVX2 0
217#endif
218
219#ifdef HAVE_AARCH64_NEON
220#define HLL_USE_NEON (simd_enabled)
221#else
222#define HLL_USE_NEON 0
223#endif
224
225/* =========================== Low level bit macros ========================= */
226
227/* Macros to access the dense representation.
228 *
229 * We need to get and set 6 bit counters in an array of 8 bit bytes.
230 * We use macros to make sure the code is inlined since speed is critical
231 * especially in order to compute the approximated cardinality in
232 * HLLCOUNT where we need to access all the registers at once.
233 * For the same reason we also want to avoid conditionals in this code path.
234 *
235 * +--------+--------+--------+------//
236 * |11000000|22221111|33333322|55444444
237 * +--------+--------+--------+------//
238 *
239 * Note: in the above representation the most significant bit (MSB)
240 * of every byte is on the left. We start using bits from the LSB to MSB,
241 * and so forth passing to the next byte.
242 *
243 * Example, we want to access to counter at pos = 1 ("111111" in the
244 * illustration above).
245 *
246 * The index of the first byte b0 containing our data is:
247 *
248 * b0 = 6 * pos / 8 = 0
249 *
250 * +--------+
251 * |11000000| <- Our byte at b0
252 * +--------+
253 *
254 * The position of the first bit (counting from the LSB = 0) in the byte
255 * is given by:
256 *
257 * fb = 6 * pos % 8 -> 6
258 *
259 * Right shift b0 of 'fb' bits.
260 *
261 * +--------+
262 * |11000000| <- Initial value of b0
263 * |00000011| <- After right shift of 6 pos.
264 * +--------+
265 *
266 * Left shift b1 of bits 8-fb bits (2 bits)
267 *
268 * +--------+
269 * |22221111| <- Initial value of b1
270 * |22111100| <- After left shift of 2 bits.
271 * +--------+
272 *
273 * OR the two bits, and finally AND with 111111 (63 in decimal) to
274 * clean the higher order bits we are not interested in:
275 *
276 * +--------+
277 * |00000011| <- b0 right shifted
278 * |22111100| <- b1 left shifted
279 * |22111111| <- b0 OR b1
280 * | 111111| <- (b0 OR b1) AND 63, our value.
281 * +--------+
282 *
283 * We can try with a different example, like pos = 0. In this case
284 * the 6-bit counter is actually contained in a single byte.
285 *
286 * b0 = 6 * pos / 8 = 0
287 *
288 * +--------+
289 * |11000000| <- Our byte at b0
290 * +--------+
291 *
292 * fb = 6 * pos % 8 = 0
293 *
294 * So we right shift of 0 bits (no shift in practice) and
295 * left shift the next byte of 8 bits, even if we don't use it,
296 * but this has the effect of clearing the bits so the result
297 * will not be affected after the OR.
298 *
299 * -------------------------------------------------------------------------
300 *
301 * Setting the register is a bit more complex, let's assume that 'val'
302 * is the value we want to set, already in the right range.
303 *
304 * We need two steps, in one we need to clear the bits, and in the other
305 * we need to bitwise-OR the new bits.
306 *
307 * Let's try with 'pos' = 1, so our first byte at 'b' is 0,
308 *
309 * "fb" is 6 in this case.
310 *
311 * +--------+
312 * |11000000| <- Our byte at b0
313 * +--------+
314 *
315 * To create an AND-mask to clear the bits about this position, we just
316 * initialize the mask with the value 63, left shift it of "fs" bits,
317 * and finally invert the result.
318 *
319 * +--------+
320 * |00111111| <- "mask" starts at 63
321 * |11000000| <- "mask" after left shift of "ls" bits.
322 * |00111111| <- "mask" after invert.
323 * +--------+
324 *
325 * Now we can bitwise-AND the byte at "b" with the mask, and bitwise-OR
326 * it with "val" left-shifted of "ls" bits to set the new bits.
327 *
328 * Now let's focus on the next byte b1:
329 *
330 * +--------+
331 * |22221111| <- Initial value of b1
332 * +--------+
333 *
334 * To build the AND mask we start again with the 63 value, right shift
335 * it by 8-fb bits, and invert it.
336 *
337 * +--------+
338 * |00111111| <- "mask" set at 2&6-1
339 * |00001111| <- "mask" after the right shift by 8-fb = 2 bits
340 * |11110000| <- "mask" after bitwise not.
341 * +--------+
342 *
343 * Now we can mask it with b+1 to clear the old bits, and bitwise-OR
344 * with "val" left-shifted by "rs" bits to set the new value.
345 */
346
347/* Note: if we access the last counter, we will also access the b+1 byte
348 * that is out of the array, but sds strings always have an implicit null
349 * term, so the byte exists, and we can skip the conditional (or the need
350 * to allocate 1 byte more explicitly). */
351
352/* Store the value of the register at position 'regnum' into variable 'target'.
353 * 'p' is an array of unsigned bytes. */
354#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
355 uint8_t *_p = (uint8_t*) p; \
356 unsigned long _byte = regnum*HLL_BITS/8; \
357 unsigned long _fb = regnum*HLL_BITS&7; \
358 unsigned long _fb8 = 8 - _fb; \
359 unsigned long b0 = _p[_byte]; \
360 unsigned long b1 = _p[_byte+1]; \
361 target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
362} while(0)
363
364/* Set the value of the register at position 'regnum' to 'val'.
365 * 'p' is an array of unsigned bytes. */
366#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
367 uint8_t *_p = (uint8_t*) p; \
368 unsigned long _byte = (regnum)*HLL_BITS/8; \
369 unsigned long _fb = (regnum)*HLL_BITS&7; \
370 unsigned long _fb8 = 8 - _fb; \
371 unsigned long _v = (val); \
372 _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
373 _p[_byte] |= _v << _fb; \
374 _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
375 _p[_byte+1] |= _v >> _fb8; \
376} while(0)
377
378/* Macros to access the sparse representation.
379 * The macros parameter is expected to be an uint8_t pointer. */
380#define HLL_SPARSE_XZERO_BIT 0x40 /* 01xxxxxx */
381#define HLL_SPARSE_VAL_BIT 0x80 /* 1vvvvvxx */
382#define HLL_SPARSE_IS_ZERO(p) (((*(p)) & 0xc0) == 0) /* 00xxxxxx */
383#define HLL_SPARSE_IS_XZERO(p) (((*(p)) & 0xc0) == HLL_SPARSE_XZERO_BIT)
384#define HLL_SPARSE_IS_VAL(p) ((*(p)) & HLL_SPARSE_VAL_BIT)
385#define HLL_SPARSE_ZERO_LEN(p) (((*(p)) & 0x3f)+1)
386#define HLL_SPARSE_XZERO_LEN(p) (((((*(p)) & 0x3f) << 8) | (*((p)+1)))+1)
387#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
388#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)
389#define HLL_SPARSE_VAL_MAX_VALUE 32
390#define HLL_SPARSE_VAL_MAX_LEN 4
391#define HLL_SPARSE_ZERO_MAX_LEN 64
392#define HLL_SPARSE_XZERO_MAX_LEN 16384
393#define HLL_SPARSE_VAL_SET(p,val,len) do { \
394 *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
395} while(0)
396#define HLL_SPARSE_ZERO_SET(p,len) do { \
397 *(p) = (len)-1; \
398} while(0)
399#define HLL_SPARSE_XZERO_SET(p,len) do { \
400 int _l = (len)-1; \
401 *(p) = (_l>>8) | HLL_SPARSE_XZERO_BIT; \
402 *((p)+1) = (_l&0xff); \
403} while(0)
404#define HLL_ALPHA_INF 0.721347520444481703680 /* constant for 0.5/ln(2) */
405
406/* ========================= HyperLogLog algorithm ========================= */
407
408/* Our hash function is MurmurHash2, 64 bit version.
409 * It was modified for Redis in order to provide the same result in
410 * big and little endian archs (endian neutral). */
411REDIS_NO_SANITIZE("alignment")
412uint64_t MurmurHash64A (const void * key, size_t len, unsigned int seed) {
413 const uint64_t m = 0xc6a4a7935bd1e995;
414 const int r = 47;
415 uint64_t h = seed ^ (len * m);
416 const uint8_t *data = (const uint8_t *)key;
417 const uint8_t *end = data + (len-(len&7));
418
419 while(data != end) {
420 uint64_t k;
421
422#if (BYTE_ORDER == LITTLE_ENDIAN)
423 #ifdef USE_ALIGNED_ACCESS
424 memcpy(&k,data,sizeof(uint64_t));
425 #else
426 k = *((uint64_t*)data);
427 #endif
428#else
429 k = (uint64_t) data[0];
430 k |= (uint64_t) data[1] << 8;
431 k |= (uint64_t) data[2] << 16;
432 k |= (uint64_t) data[3] << 24;
433 k |= (uint64_t) data[4] << 32;
434 k |= (uint64_t) data[5] << 40;
435 k |= (uint64_t) data[6] << 48;
436 k |= (uint64_t) data[7] << 56;
437#endif
438
439 k *= m;
440 k ^= k >> r;
441 k *= m;
442 h ^= k;
443 h *= m;
444 data += 8;
445 }
446
447 switch(len & 7) {
448 case 7: h ^= (uint64_t)data[6] << 48; /* fall-thru */
449 case 6: h ^= (uint64_t)data[5] << 40; /* fall-thru */
450 case 5: h ^= (uint64_t)data[4] << 32; /* fall-thru */
451 case 4: h ^= (uint64_t)data[3] << 24; /* fall-thru */
452 case 3: h ^= (uint64_t)data[2] << 16; /* fall-thru */
453 case 2: h ^= (uint64_t)data[1] << 8; /* fall-thru */
454 case 1: h ^= (uint64_t)data[0];
455 h *= m; /* fall-thru */
456 };
457
458 h ^= h >> r;
459 h *= m;
460 h ^= h >> r;
461 return h;
462}
463
464/* Given a string element to add to the HyperLogLog, returns the length
465 * of the pattern 000..1 of the element hash. As a side effect 'regp' is
466 * set to the register index this element hashes to. */
467int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
468 uint64_t hash, index;
469 int count;
470
471 /* Count the number of zeroes starting from bit HLL_REGISTERS
472 * (that is a power of two corresponding to the first bit we don't use
473 * as index). The max run can be 64-P+1 = Q+1 bits.
474 *
475 * Note that the final "1" ending the sequence of zeroes must be
476 * included in the count, so if we find "001" the count is 3, and
477 * the smallest count possible is no zeroes at all, just a 1 bit
478 * at the first position, that is a count of 1. */
479 hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
480 index = hash & HLL_P_MASK; /* Register index. */
481 hash >>= HLL_P; /* Remove bits used to address the register. */
482 hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates
483 and count will be <= Q+1. */
484
485 count = __builtin_ctzll(hash) + 1;
486 *regp = (int) index;
487 return count;
488}
489
490/* ================== Dense representation implementation ================== */
491
492/* Low level function to set the dense HLL register at 'index' to the
493 * specified value if the current value is smaller than 'count'.
494 *
495 * 'registers' is expected to have room for HLL_REGISTERS plus an
496 * additional byte on the right. This requirement is met by sds strings
497 * automatically since they are implicitly null terminated.
498 *
499 * The function always succeed, however if as a result of the operation
500 * the approximated cardinality changed, 1 is returned. Otherwise 0
501 * is returned. */
502int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
503 uint8_t oldcount;
504
505 HLL_DENSE_GET_REGISTER(oldcount,registers,index);
506 if (count > oldcount) {
507 HLL_DENSE_SET_REGISTER(registers,index,count);
508 return 1;
509 } else {
510 return 0;
511 }
512}
513
514/* "Add" the element in the dense hyperloglog data structure.
515 * Actually nothing is added, but the max 0 pattern counter of the subset
516 * the element belongs to is incremented if needed.
517 *
518 * This is just a wrapper to hllDenseSet(), performing the hashing of the
519 * element in order to retrieve the index and zero-run count. */
520int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
521 long index;
522 uint8_t count = hllPatLen(ele,elesize,&index);
523 /* Update the register if this element produced a longer run of zeroes. */
524 return hllDenseSet(registers,index,count);
525}
526
527/* Compute the register histogram in the dense representation. */
528void hllDenseRegHisto(uint8_t *registers, int* reghisto) {
529 int j;
530
531 /* Redis default is to use 16384 registers 6 bits each. The code works
532 * with other values by modifying the defines, but for our target value
533 * we take a faster path with unrolled loops. */
534 if (HLL_REGISTERS == 16384 && HLL_BITS == 6) {
535 uint8_t *r = registers;
536 unsigned long r0, r1, r2, r3, r4, r5, r6, r7, r8, r9,
537 r10, r11, r12, r13, r14, r15;
538 for (j = 0; j < 1024; j++) {
539 /* Handle 16 registers per iteration. */
540 r0 = r[0] & 63;
541 r1 = (r[0] >> 6 | r[1] << 2) & 63;
542 r2 = (r[1] >> 4 | r[2] << 4) & 63;
543 r3 = (r[2] >> 2) & 63;
544 r4 = r[3] & 63;
545 r5 = (r[3] >> 6 | r[4] << 2) & 63;
546 r6 = (r[4] >> 4 | r[5] << 4) & 63;
547 r7 = (r[5] >> 2) & 63;
548 r8 = r[6] & 63;
549 r9 = (r[6] >> 6 | r[7] << 2) & 63;
550 r10 = (r[7] >> 4 | r[8] << 4) & 63;
551 r11 = (r[8] >> 2) & 63;
552 r12 = r[9] & 63;
553 r13 = (r[9] >> 6 | r[10] << 2) & 63;
554 r14 = (r[10] >> 4 | r[11] << 4) & 63;
555 r15 = (r[11] >> 2) & 63;
556
557 reghisto[r0]++;
558 reghisto[r1]++;
559 reghisto[r2]++;
560 reghisto[r3]++;
561 reghisto[r4]++;
562 reghisto[r5]++;
563 reghisto[r6]++;
564 reghisto[r7]++;
565 reghisto[r8]++;
566 reghisto[r9]++;
567 reghisto[r10]++;
568 reghisto[r11]++;
569 reghisto[r12]++;
570 reghisto[r13]++;
571 reghisto[r14]++;
572 reghisto[r15]++;
573
574 r += 12;
575 }
576 } else {
577 for(j = 0; j < HLL_REGISTERS; j++) {
578 unsigned long reg;
579 HLL_DENSE_GET_REGISTER(reg,registers,j);
580 reghisto[reg]++;
581 }
582 }
583}
584
585/* ================== Sparse representation implementation ================= */
586
587/* Convert the HLL with sparse representation given as input in its dense
588 * representation. Both representations are represented by SDS strings, and
589 * the input representation is freed as a side effect.
590 *
591 * The function returns C_OK if the sparse representation was valid,
592 * otherwise C_ERR is returned if the representation was corrupted. */
593int hllSparseToDense(robj *o) {
594 sds sparse = o->ptr, dense;
595 struct hllhdr *hdr, *oldhdr = (struct hllhdr*)sparse;
596 int idx = 0, runlen, regval;
597 uint8_t *p = (uint8_t*)sparse, *end = p+sdslen(sparse);
598 int valid = 1;
599
600 /* If the representation is already the right one return ASAP. */
601 hdr = (struct hllhdr*) sparse;
602 if (hdr->encoding == HLL_DENSE) return C_OK;
603
604 /* Create a string of the right size filled with zero bytes.
605 * Note that the cached cardinality is set to 0 as a side effect
606 * that is exactly the cardinality of an empty HLL. */
607 dense = sdsnewlen(NULL,HLL_DENSE_SIZE);
608 hdr = (struct hllhdr*) dense;
609 *hdr = *oldhdr; /* This will copy the magic and cached cardinality. */
610 hdr->encoding = HLL_DENSE;
611
612 /* Now read the sparse representation and set non-zero registers
613 * accordingly. */
614 p += HLL_HDR_SIZE;
615 while(p < end) {
616 if (HLL_SPARSE_IS_ZERO(p)) {
617 runlen = HLL_SPARSE_ZERO_LEN(p);
618 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
619 valid = 0;
620 break;
621 }
622 idx += runlen;
623 p++;
624 } else if (HLL_SPARSE_IS_XZERO(p)) {
625 runlen = HLL_SPARSE_XZERO_LEN(p);
626 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
627 valid = 0;
628 break;
629 }
630 idx += runlen;
631 p += 2;
632 } else {
633 runlen = HLL_SPARSE_VAL_LEN(p);
634 regval = HLL_SPARSE_VAL_VALUE(p);
635 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
636 valid = 0;
637 break;
638 }
639 while(runlen--) {
640 HLL_DENSE_SET_REGISTER(hdr->registers,idx,regval);
641 idx++;
642 }
643 p++;
644 }
645 }
646
647 /* If the sparse representation was valid, we expect to find idx
648 * set to HLL_REGISTERS. */
649 if (!valid || idx != HLL_REGISTERS) {
650 sdsfree(dense);
651 return C_ERR;
652 }
653
654 /* Free the old representation and set the new one. */
655 sdsfree(o->ptr);
656 o->ptr = dense;
657 return C_OK;
658}
659
660/* Low level function to set the sparse HLL register at 'index' to the
661 * specified value if the current value is smaller than 'count'.
662 *
663 * The object 'o' is the String object holding the HLL. The function requires
664 * a reference to the object in order to be able to enlarge the string if
665 * needed.
666 *
667 * On success, the function returns 1 if the cardinality changed, or 0
668 * if the register for this element was not updated.
669 * On error (if the representation is invalid) -1 is returned.
670 *
671 * As a side effect the function may promote the HLL representation from
672 * sparse to dense: this happens when a register requires to be set to a value
673 * not representable with the sparse representation, or when the resulting
674 * size would be greater than server.hll_sparse_max_bytes. */
675int hllSparseSet(robj *o, long index, uint8_t count) {
676 struct hllhdr *hdr;
677 uint8_t oldcount, *sparse, *end, *p, *prev, *next;
678 long first, span;
679 long is_zero = 0, is_xzero = 0, is_val = 0, runlen = 0;
680
681 /* If the count is too big to be representable by the sparse representation
682 * switch to dense representation. */
683 if (count > HLL_SPARSE_VAL_MAX_VALUE) goto promote;
684
685 /* When updating a sparse representation, sometimes we may need to enlarge the
686 * buffer for up to 3 bytes in the worst case (XZERO split into XZERO-VAL-XZERO),
687 * and the following code does the enlarge job.
688 * Actually, we use a greedy strategy, enlarge more than 3 bytes to avoid the need
689 * for future reallocates on incremental growth. But we do not allocate more than
690 * 'server.hll_sparse_max_bytes' bytes for the sparse representation.
691 * If the available size of hyperloglog sds string is not enough for the increment
692 * we need, we promote the hyperloglog to dense representation in 'step 3'.
693 */
694 if (sdsalloc(o->ptr) < server.hll_sparse_max_bytes && sdsavail(o->ptr) < 3) {
695 size_t newlen = sdslen(o->ptr) + 3;
696 newlen += min(newlen, 300); /* Greediness: double 'newlen' if it is smaller than 300, or add 300 to it when it exceeds 300 */
697 if (newlen > server.hll_sparse_max_bytes)
698 newlen = server.hll_sparse_max_bytes;
699 o->ptr = sdsResize(o->ptr, newlen, 1);
700 }
701
702 /* Step 1: we need to locate the opcode we need to modify to check
703 * if a value update is actually needed. */
704 sparse = p = ((uint8_t*)o->ptr) + HLL_HDR_SIZE;
705 end = p + sdslen(o->ptr) - HLL_HDR_SIZE;
706
707 first = 0;
708 prev = NULL; /* Points to previous opcode at the end of the loop. */
709 next = NULL; /* Points to the next opcode at the end of the loop. */
710 span = 0;
711 while(p < end) {
712 long oplen;
713
714 /* Set span to the number of registers covered by this opcode.
715 *
716 * This is the most performance critical loop of the sparse
717 * representation. Sorting the conditionals from the most to the
718 * least frequent opcode in many-bytes sparse HLLs is faster. */
719 oplen = 1;
720 if (HLL_SPARSE_IS_ZERO(p)) {
721 span = HLL_SPARSE_ZERO_LEN(p);
722 } else if (HLL_SPARSE_IS_VAL(p)) {
723 span = HLL_SPARSE_VAL_LEN(p);
724 } else { /* XZERO. */
725 span = HLL_SPARSE_XZERO_LEN(p);
726 oplen = 2;
727 }
728 /* Break if this opcode covers the register as 'index'. */
729 if (index <= first+span-1) break;
730 prev = p;
731 p += oplen;
732 first += span;
733 }
734 if (span == 0 || p >= end) return -1; /* Invalid format. */
735
736 next = HLL_SPARSE_IS_XZERO(p) ? p+2 : p+1;
737 if (next >= end) next = NULL;
738
739 /* Cache current opcode type to avoid using the macro again and
740 * again for something that will not change.
741 * Also cache the run-length of the opcode. */
742 if (HLL_SPARSE_IS_ZERO(p)) {
743 is_zero = 1;
744 runlen = HLL_SPARSE_ZERO_LEN(p);
745 } else if (HLL_SPARSE_IS_XZERO(p)) {
746 is_xzero = 1;
747 runlen = HLL_SPARSE_XZERO_LEN(p);
748 } else {
749 is_val = 1;
750 runlen = HLL_SPARSE_VAL_LEN(p);
751 }
752
753 /* Step 2: After the loop:
754 *
755 * 'first' stores to the index of the first register covered
756 * by the current opcode, which is pointed by 'p'.
757 *
758 * 'next' ad 'prev' store respectively the next and previous opcode,
759 * or NULL if the opcode at 'p' is respectively the last or first.
760 *
761 * 'span' is set to the number of registers covered by the current
762 * opcode.
763 *
764 * There are different cases in order to update the data structure
765 * in place without generating it from scratch:
766 *
767 * A) If it is a VAL opcode already set to a value >= our 'count'
768 * no update is needed, regardless of the VAL run-length field.
769 * In this case PFADD returns 0 since no changes are performed.
770 *
771 * B) If it is a VAL opcode with len = 1 (representing only our
772 * register) and the value is less than 'count', we just update it
773 * since this is a trivial case. */
774 if (is_val) {
775 oldcount = HLL_SPARSE_VAL_VALUE(p);
776 /* Case A. */
777 if (oldcount >= count) return 0;
778
779 /* Case B. */
780 if (runlen == 1) {
781 HLL_SPARSE_VAL_SET(p,count,1);
782 goto updated;
783 }
784 }
785
786 /* C) Another trivial to handle case is a ZERO opcode with a len of 1.
787 * We can just replace it with a VAL opcode with our value and len of 1. */
788 if (is_zero && runlen == 1) {
789 HLL_SPARSE_VAL_SET(p,count,1);
790 goto updated;
791 }
792
793 /* D) General case.
794 *
795 * The other cases are more complex: our register requires to be updated
796 * and is either currently represented by a VAL opcode with len > 1,
797 * by a ZERO opcode with len > 1, or by an XZERO opcode.
798 *
799 * In those cases the original opcode must be split into multiple
800 * opcodes. The worst case is an XZERO split in the middle resulting into
801 * XZERO - VAL - XZERO, so the resulting sequence max length is
802 * 5 bytes.
803 *
804 * We perform the split writing the new sequence into the 'new' buffer
805 * with 'newlen' as length. Later the new sequence is inserted in place
806 * of the old one, possibly moving what is on the right a few bytes
807 * if the new sequence is longer than the older one. */
808 uint8_t seq[5], *n = seq;
809 int last = first+span-1; /* Last register covered by the sequence. */
810 int len;
811
812 if (is_zero || is_xzero) {
813 /* Handle splitting of ZERO / XZERO. */
814 if (index != first) {
815 len = index-first;
816 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
817 HLL_SPARSE_XZERO_SET(n,len);
818 n += 2;
819 } else {
820 HLL_SPARSE_ZERO_SET(n,len);
821 n++;
822 }
823 }
824 HLL_SPARSE_VAL_SET(n,count,1);
825 n++;
826 if (index != last) {
827 len = last-index;
828 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
829 HLL_SPARSE_XZERO_SET(n,len);
830 n += 2;
831 } else {
832 HLL_SPARSE_ZERO_SET(n,len);
833 n++;
834 }
835 }
836 } else {
837 /* Handle splitting of VAL. */
838 int curval = HLL_SPARSE_VAL_VALUE(p);
839
840 if (index != first) {
841 len = index-first;
842 HLL_SPARSE_VAL_SET(n,curval,len);
843 n++;
844 }
845 HLL_SPARSE_VAL_SET(n,count,1);
846 n++;
847 if (index != last) {
848 len = last-index;
849 HLL_SPARSE_VAL_SET(n,curval,len);
850 n++;
851 }
852 }
853
854 /* Step 3: substitute the new sequence with the old one.
855 *
856 * Note that we already allocated space on the sds string
857 * calling sdsResize(). */
858 int seqlen = n-seq;
859 int oldlen = is_xzero ? 2 : 1;
860 int deltalen = seqlen-oldlen;
861
862 if (deltalen > 0 &&
863 sdslen(o->ptr) + deltalen > server.hll_sparse_max_bytes) goto promote;
864 serverAssert(sdslen(o->ptr) + deltalen <= sdsalloc(o->ptr));
865 if (deltalen && next) memmove(next+deltalen,next,end-next);
866 sdsIncrLen(o->ptr,deltalen);
867 memcpy(p,seq,seqlen);
868 end += deltalen;
869
870updated:
871 /* Step 4: Merge adjacent values if possible.
872 *
873 * The representation was updated, however the resulting representation
874 * may not be optimal: adjacent VAL opcodes can sometimes be merged into
875 * a single one. */
876 p = prev ? prev : sparse;
877 int scanlen = 5; /* Scan up to 5 upcodes starting from prev. */
878 while (p < end && scanlen--) {
879 if (HLL_SPARSE_IS_XZERO(p)) {
880 p += 2;
881 continue;
882 } else if (HLL_SPARSE_IS_ZERO(p)) {
883 p++;
884 continue;
885 }
886 /* We need two adjacent VAL opcodes to try a merge, having
887 * the same value, and a len that fits the VAL opcode max len. */
888 if (p+1 < end && HLL_SPARSE_IS_VAL(p+1)) {
889 int v1 = HLL_SPARSE_VAL_VALUE(p);
890 int v2 = HLL_SPARSE_VAL_VALUE(p+1);
891 if (v1 == v2) {
892 int len = HLL_SPARSE_VAL_LEN(p)+HLL_SPARSE_VAL_LEN(p+1);
893 if (len <= HLL_SPARSE_VAL_MAX_LEN) {
894 HLL_SPARSE_VAL_SET(p+1,v1,len);
895 memmove(p,p+1,end-p);
896 sdsIncrLen(o->ptr,-1);
897 end--;
898 /* After a merge we reiterate without incrementing 'p'
899 * in order to try to merge the just merged value with
900 * a value on its right. */
901 continue;
902 }
903 }
904 }
905 p++;
906 }
907
908 /* Invalidate the cached cardinality. */
909 hdr = o->ptr;
910 HLL_INVALIDATE_CACHE(hdr);
911 return 1;
912
913promote: /* Promote to dense representation. */
914 if (hllSparseToDense(o) == C_ERR) return -1; /* Corrupted HLL. */
915 hdr = o->ptr;
916
917 /* We need to call hllDenseAdd() to perform the operation after the
918 * conversion. However the result must be 1, since if we need to
919 * convert from sparse to dense a register requires to be updated.
920 *
921 * Note that this in turn means that PFADD will make sure the command
922 * is propagated to slaves / AOF, so if there is a sparse -> dense
923 * conversion, it will be performed in all the slaves as well. */
924 int dense_retval = hllDenseSet(hdr->registers,index,count);
925 serverAssert(dense_retval == 1);
926 return dense_retval;
927}
928
929/* "Add" the element in the sparse hyperloglog data structure.
930 * Actually nothing is added, but the max 0 pattern counter of the subset
931 * the element belongs to is incremented if needed.
932 *
933 * This function is actually a wrapper for hllSparseSet(), it only performs
934 * the hashing of the element to obtain the index and zeros run length. */
935int hllSparseAdd(robj *o, unsigned char *ele, size_t elesize) {
936 long index;
937 uint8_t count = hllPatLen(ele,elesize,&index);
938 /* Update the register if this element produced a longer run of zeroes. */
939 return hllSparseSet(o,index,count);
940}
941
942/* Compute the register histogram in the sparse representation. */
943void hllSparseRegHisto(uint8_t *sparse, int sparselen, int *invalid, int* reghisto) {
944 int idx = 0, runlen, regval;
945 uint8_t *end = sparse+sparselen, *p = sparse;
946 int valid = 1;
947
948 while(p < end) {
949 if (HLL_SPARSE_IS_ZERO(p)) {
950 runlen = HLL_SPARSE_ZERO_LEN(p);
951 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
952 valid = 0;
953 break;
954 }
955 idx += runlen;
956 reghisto[0] += runlen;
957 p++;
958 } else if (HLL_SPARSE_IS_XZERO(p)) {
959 runlen = HLL_SPARSE_XZERO_LEN(p);
960 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
961 valid = 0;
962 break;
963 }
964 idx += runlen;
965 reghisto[0] += runlen;
966 p += 2;
967 } else {
968 runlen = HLL_SPARSE_VAL_LEN(p);
969 regval = HLL_SPARSE_VAL_VALUE(p);
970 if ((runlen + idx) > HLL_REGISTERS) { /* Overflow. */
971 valid = 0;
972 break;
973 }
974 idx += runlen;
975 reghisto[regval] += runlen;
976 p++;
977 }
978 }
979 if ((!valid || idx != HLL_REGISTERS) && invalid) *invalid = 1;
980}
981
982/* ========================= HyperLogLog Count ==============================
983 * This is the core of the algorithm where the approximated count is computed.
984 * The function uses the lower level hllDenseRegHisto() and hllSparseRegHisto()
985 * functions as helpers to compute histogram of register values part of the
986 * computation, which is representation-specific, while all the rest is common. */
987
988/* Implements the register histogram calculation for uint8_t data type
989 * which is only used internally as speedup for PFCOUNT with multiple keys. */
990void hllRawRegHisto(uint8_t *registers, int* reghisto) {
991 uint64_t *word = (uint64_t*) registers;
992 uint8_t *bytes;
993 int j;
994
995 for (j = 0; j < HLL_REGISTERS/8; j++) {
996 if (*word == 0) {
997 reghisto[0] += 8;
998 } else {
999 bytes = (uint8_t*) word;
1000 reghisto[bytes[0]]++;
1001 reghisto[bytes[1]]++;
1002 reghisto[bytes[2]]++;
1003 reghisto[bytes[3]]++;
1004 reghisto[bytes[4]]++;
1005 reghisto[bytes[5]]++;
1006 reghisto[bytes[6]]++;
1007 reghisto[bytes[7]]++;
1008 }
1009 word++;
1010 }
1011}
1012
1013/* Helper function sigma as defined in
1014 * "New cardinality estimation algorithms for HyperLogLog sketches"
1015 * Otmar Ertl, arXiv:1702.01284 */
1016double hllSigma(double x) {
1017 if (x == 1.) return INFINITY;
1018 double zPrime;
1019 double y = 1;
1020 double z = x;
1021 do {
1022 x *= x;
1023 zPrime = z;
1024 z += x * y;
1025 y += y;
1026 } while(zPrime != z);
1027 return z;
1028}
1029
1030/* Helper function tau as defined in
1031 * "New cardinality estimation algorithms for HyperLogLog sketches"
1032 * Otmar Ertl, arXiv:1702.01284 */
1033double hllTau(double x) {
1034 if (x == 0. || x == 1.) return 0.;
1035 double zPrime;
1036 double y = 1.0;
1037 double z = 1 - x;
1038 do {
1039 x = sqrt(x);
1040 zPrime = z;
1041 y *= 0.5;
1042 z -= pow(1 - x, 2)*y;
1043 } while(zPrime != z);
1044 return z / 3;
1045}
1046
1047/* Return the approximated cardinality of the set based on the harmonic
1048 * mean of the registers values. 'hdr' points to the start of the SDS
1049 * representing the String object holding the HLL representation.
1050 *
1051 * If the sparse representation of the HLL object is not valid, the integer
1052 * pointed by 'invalid' is set to non-zero, otherwise it is left untouched.
1053 *
1054 * hllCount() supports a special internal-only encoding of HLL_RAW, that
1055 * is, hdr->registers will point to an uint8_t array of HLL_REGISTERS element.
1056 * This is useful in order to speedup PFCOUNT when called against multiple
1057 * keys (no need to work with 6-bit integers encoding). */
1058uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
1059 double m = HLL_REGISTERS;
1060 double E;
1061 int j;
1062 /* Note that reghisto size could be just HLL_Q+2, because HLL_Q+1 is
1063 * the maximum frequency of the "000...1" sequence the hash function is
1064 * able to return. However it is slow to check for sanity of the
1065 * input: instead we history array at a safe size: overflows will
1066 * just write data to wrong, but correctly allocated, places. */
1067 int reghisto[64] = {0};
1068
1069 /* Compute register histogram */
1070 if (hdr->encoding == HLL_DENSE) {
1071 hllDenseRegHisto(hdr->registers,reghisto);
1072 } else if (hdr->encoding == HLL_SPARSE) {
1073 hllSparseRegHisto(hdr->registers,
1074 sdslen((sds)hdr)-HLL_HDR_SIZE,invalid,reghisto);
1075 } else if (hdr->encoding == HLL_RAW) {
1076 hllRawRegHisto(hdr->registers,reghisto);
1077 } else {
1078 serverPanic("Unknown HyperLogLog encoding in hllCount()");
1079 }
1080
1081 /* Estimate cardinality from register histogram. See:
1082 * "New cardinality estimation algorithms for HyperLogLog sketches"
1083 * Otmar Ertl, arXiv:1702.01284 */
1084 double z = m * hllTau((m-reghisto[HLL_Q+1])/(double)m);
1085 for (j = HLL_Q; j >= 1; --j) {
1086 z += reghisto[j];
1087 z *= 0.5;
1088 }
1089 z += m * hllSigma(reghisto[0]/(double)m);
1090 E = llroundl(HLL_ALPHA_INF*m*m/z);
1091
1092 return (uint64_t) E;
1093}
1094
1095/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
1096int hllAdd(robj *o, unsigned char *ele, size_t elesize) {
1097 struct hllhdr *hdr = o->ptr;
1098 switch(hdr->encoding) {
1099 case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
1100 case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);
1101 default: return -1; /* Invalid representation. */
1102 }
1103}
1104
1105#ifdef HAVE_AVX2
1106/* A specialized version of hllMergeDense, optimized for default configurations.
1107 *
1108 * Requirements:
1109 * 1) HLL_REGISTERS == 16384 && HLL_BITS == 6
1110 * 2) The CPU supports AVX2 (checked at runtime in hllMergeDense)
1111 *
1112 * reg_raw: pointer to the raw representation array (16384 bytes, one byte per register)
1113 * reg_dense: pointer to the dense representation array (12288 bytes, 6 bits per register)
1114 */
1115ATTRIBUTE_TARGET_AVX2
1116void hllMergeDenseAVX2(uint8_t *reg_raw, const uint8_t *reg_dense) {
1117 const __m256i shuffle = _mm256_setr_epi8( //
1118 4, 5, 6, -1, //
1119 7, 8, 9, -1, //
1120 10, 11, 12, -1, //
1121 13, 14, 15, -1, //
1122 0, 1, 2, -1, //
1123 3, 4, 5, -1, //
1124 6, 7, 8, -1, //
1125 9, 10, 11, -1 //
1126 );
1127
1128 /* Merge the first 8 registers (6 bytes) normally
1129 * as the AVX2 algorithm needs 4 padding bytes at the start */
1130 uint8_t val;
1131 for (int i = 0; i < 8; i++) {
1132 HLL_DENSE_GET_REGISTER(val, reg_dense, i);
1133 reg_raw[i] = MAX(reg_raw[i], val);
1134 }
1135
1136 /* Dense to Raw:
1137 *
1138 * 4 registers in 3 bytes:
1139 * {bbaaaaaa|ccccbbbb|ddddddcc}
1140 *
1141 * LOAD 32 bytes (32 registers) per iteration:
1142 * 4(padding) + 12(16 registers) + 12(16 registers) + 4(padding)
1143 * {XXXX|AAAB|BBCC|CDDD|EEEF|FFGG|GHHH|XXXX}
1144 *
1145 * SHUFFLE to:
1146 * {AAA0|BBB0|CCC0|DDD0|EEE0|FFF0|GGG0|HHH0}
1147 * {bbaaaaaa|ccccbbbb|ddddddcc|00000000} x8
1148 *
1149 * AVX2 is little endian, each of the 8 groups is a little-endian int32.
1150 * A group (int32) contains 3 valid bytes (4 registers) and a zero byte.
1151 *
1152 * extract registers in each group with AND and SHIFT:
1153 * {00aaaaaa|00000000|00000000|00000000} x8 (<<0)
1154 * {00000000|00bbbbbb|00000000|00000000} x8 (<<2)
1155 * {00000000|00000000|00cccccc|00000000} x8 (<<4)
1156 * {00000000|00000000|00000000|00dddddd} x8 (<<6)
1157 *
1158 * merge the extracted registers with OR:
1159 * {00aaaaaa|00bbbbbb|00cccccc|00dddddd} x8
1160 *
1161 * Finally, compute MAX(reg_raw, merged) and STORE it back to reg_raw
1162 */
1163
1164 /* Skip 8 registers (6 bytes) */
1165 const uint8_t *r = reg_dense + 6 - 4;
1166 uint8_t *t = reg_raw + 8;
1167
1168 for (int i = 0; i < HLL_REGISTERS / 32 - 1; ++i) {
1169 __m256i x0, x;
1170 x0 = _mm256_loadu_si256((__m256i *)r);
1171 x = _mm256_shuffle_epi8(x0, shuffle);
1172
1173 __m256i a1, a2, a3, a4;
1174 a1 = _mm256_and_si256(x, _mm256_set1_epi32(0x0000003f));
1175 a2 = _mm256_and_si256(x, _mm256_set1_epi32(0x00000fc0));
1176 a3 = _mm256_and_si256(x, _mm256_set1_epi32(0x0003f000));
1177 a4 = _mm256_and_si256(x, _mm256_set1_epi32(0x00fc0000));
1178
1179 a2 = _mm256_slli_epi32(a2, 2);
1180 a3 = _mm256_slli_epi32(a3, 4);
1181 a4 = _mm256_slli_epi32(a4, 6);
1182
1183 __m256i y1, y2, y;
1184 y1 = _mm256_or_si256(a1, a2);
1185 y2 = _mm256_or_si256(a3, a4);
1186 y = _mm256_or_si256(y1, y2);
1187
1188 __m256i z = _mm256_loadu_si256((__m256i *)t);
1189
1190 z = _mm256_max_epu8(z, y);
1191
1192 _mm256_storeu_si256((__m256i *)t, z);
1193
1194 r += 24;
1195 t += 32;
1196 }
1197
1198 /* Merge the last 24 registers normally
1199 * as the AVX2 algorithm needs 4 padding bytes at the end */
1200 for (int i = HLL_REGISTERS - 24; i < HLL_REGISTERS; i++) {
1201 HLL_DENSE_GET_REGISTER(val, reg_dense, i);
1202 reg_raw[i] = MAX(reg_raw[i], val);
1203 }
1204}
1205#endif
1206
1207#ifdef HAVE_AARCH64_NEON
1208/* A specialized version of hllMergeDense, optimized for default configurations.
1209 * Based on the AVX2 version.
1210 *
1211 * Requirements:
1212 * 1) HLL_REGISTERS == 16384 && HLL_BITS == 6
1213 * 2) Aarch64 CPU supports NEON (checked at runtime in hllMergeDense)
1214 *
1215 * reg_raw: pointer to the raw representation array (16384 bytes, one byte per register)
1216 * reg_dense: pointer to the dense representation array (12288 bytes, 6 bits per register)
1217 */
1218void hllMergeDenseAarch64(uint8_t *reg_raw, const uint8_t *reg_dense) {
1219 const uint8_t *r = reg_dense;
1220 uint8_t *t = reg_raw;
1221
1222 /* Shuffle pattern to expand each 12-byte packed group (16 regs x 6 bits)
1223 * to 16 bytes by inserting zeroes at bytes 3, 7, 11 and 15. */
1224 const uint8x16_t shuffle = {
1225 0, 1, 2, -1,
1226 3, 4, 5, -1,
1227 6, 7, 8, -1,
1228 9, 10, 11, -1
1229 };
1230
1231 for (int i = 0; i < HLL_REGISTERS / 16 - 1; ++i) {
1232 /* Load 16 bytes (12 meaningful) and apply table; zeros fill pad positions. */
1233 uint8x16_t x, x0;
1234 x0 = vld1q_u8(r);
1235 x = vqtbl1q_u8(x0, shuffle);
1236
1237 /* Treat as 4x32-bit lanes (LE); each lane now holds 3 packed bytes + one zero. */
1238 uint32x4_t x32 = vreinterpretq_u32_u8(x);
1239
1240 /* Extract the four 6-bit fields per 32-bit lane. */
1241 uint32x4_t a1, a2, a3, a4;
1242 a1 = vandq_u32(x32, vdupq_n_u32(0x0000003f));
1243 a2 = vandq_u32(x32, vdupq_n_u32(0x00000fc0));
1244 a3 = vandq_u32(x32, vdupq_n_u32(0x0003f000));
1245 a4 = vandq_u32(x32, vdupq_n_u32(0x00fc0000));
1246
1247 /* Align fields to byte boundaries within each lane. */
1248 a2 = vshlq_n_u32(a2, 2);
1249 a3 = vshlq_n_u32(a3, 4);
1250 a4 = vshlq_n_u32(a4, 6);
1251
1252 /* Combine fields per lane (32-bit). */
1253 uint32x4_t y32 = vorrq_u32(vorrq_u32(a1, a2), vorrq_u32(a3, a4));
1254
1255 /* Reinterpret to actual 8-bit uints for comparison. */
1256 uint8x16_t y = vreinterpretq_u8_u32(y32);
1257
1258 /* Max-merge with existing raw registers. */
1259 uint8x16_t z = vld1q_u8(t);
1260 z = vmaxq_u8(z, y);
1261
1262 /* Store the results. */
1263 vst1q_u8(t, z);
1264
1265 r += 12;
1266 t += 16;
1267 }
1268
1269 /* Process remaining registers, we do this manually because we don't want to over-read 4 bytes */
1270 uint8_t val;
1271 for (int i = HLL_REGISTERS - 16; i < HLL_REGISTERS; i++) {
1272 HLL_DENSE_GET_REGISTER(val, reg_dense, i);
1273 reg_raw[i] = MAX(reg_raw[i], val);
1274 }
1275}
1276#endif /* HAVE_AARCH64_NEON */
1277
1278/* Merge dense-encoded registers to raw registers array. */
1279void hllMergeDense(uint8_t* reg_raw, const uint8_t* reg_dense) {
1280#if HLL_REGISTERS == 16384 && HLL_BITS == 6
1281#ifdef HAVE_AVX2
1282 if (HLL_USE_AVX2) {
1283 hllMergeDenseAVX2(reg_raw, reg_dense);
1284 return;
1285 }
1286#endif
1287#ifdef HAVE_AARCH64_NEON
1288 if (HLL_USE_NEON) {
1289 hllMergeDenseAarch64(reg_raw, reg_dense);
1290 return;
1291 }
1292#endif
1293#endif
1294
1295 uint8_t val;
1296 for (int i = 0; i < HLL_REGISTERS; i++) {
1297 HLL_DENSE_GET_REGISTER(val, reg_dense, i);
1298 reg_raw[i] = MAX(reg_raw[i], val);
1299 }
1300}
1301
1302/* Merge by computing MAX(registers[i],hll[i]) the HyperLogLog 'hll'
1303 * with an array of uint8_t HLL_REGISTERS registers pointed by 'max'.
1304 *
1305 * The hll object must be already validated via isHLLObjectOrReply()
1306 * or in some other way.
1307 *
1308 * If the HyperLogLog is sparse and is found to be invalid, C_ERR
1309 * is returned, otherwise the function always succeeds. */
1310int hllMerge(uint8_t *max, robj *hll) {
1311 struct hllhdr *hdr = hll->ptr;
1312 int i;
1313
1314 if (hdr->encoding == HLL_DENSE) {
1315 hllMergeDense(max, hdr->registers);
1316 } else {
1317 uint8_t *p = hll->ptr, *end = p + sdslen(hll->ptr);
1318 long runlen, regval;
1319 int valid = 1;
1320
1321 p += HLL_HDR_SIZE;
1322 i = 0;
1323 while(p < end) {
1324 if (HLL_SPARSE_IS_ZERO(p)) {
1325 runlen = HLL_SPARSE_ZERO_LEN(p);
1326 if ((runlen + i) > HLL_REGISTERS) { /* Overflow. */
1327 valid = 0;
1328 break;
1329 }
1330 i += runlen;
1331 p++;
1332 } else if (HLL_SPARSE_IS_XZERO(p)) {
1333 runlen = HLL_SPARSE_XZERO_LEN(p);
1334 if ((runlen + i) > HLL_REGISTERS) { /* Overflow. */
1335 valid = 0;
1336 break;
1337 }
1338 i += runlen;
1339 p += 2;
1340 } else {
1341 runlen = HLL_SPARSE_VAL_LEN(p);
1342 regval = HLL_SPARSE_VAL_VALUE(p);
1343 if ((runlen + i) > HLL_REGISTERS) { /* Overflow. */
1344 valid = 0;
1345 break;
1346 }
1347 while(runlen--) {
1348 if (regval > max[i]) max[i] = regval;
1349 i++;
1350 }
1351 p++;
1352 }
1353 }
1354 if (!valid || i != HLL_REGISTERS) return C_ERR;
1355 }
1356 return C_OK;
1357}
1358
1359#ifdef HAVE_AVX2
1360/* A specialized version of hllDenseCompress, optimized for default configurations.
1361 *
1362 * Requirements:
1363 * 1) HLL_REGISTERS == 16384 && HLL_BITS == 6
1364 * 2) The CPU supports AVX2 (checked at runtime in hllDenseCompress)
1365 *
1366 * reg_dense: pointer to the dense representation array (12288 bytes, 6 bits per register)
1367 * reg_raw: pointer to the raw representation array (16384 bytes, one byte per register)
1368 */
1369ATTRIBUTE_TARGET_AVX2
1370void hllDenseCompressAVX2(uint8_t *reg_dense, const uint8_t *reg_raw) {
1371 const __m256i shuffle = _mm256_setr_epi8( //
1372 0, 1, 2, //
1373 4, 5, 6, //
1374 8, 9, 10, //
1375 12, 13, 14, //
1376 -1, -1, -1, -1, //
1377 0, 1, 2, //
1378 4, 5, 6, //
1379 8, 9, 10, //
1380 12, 13, 14, //
1381 -1, -1, -1, -1 //
1382 );
1383
1384 /* Raw to Dense:
1385 *
1386 * LOAD 32 bytes (32 registers) per iteration:
1387 * {00aaaaaa|00bbbbbb|00cccccc|00dddddd} x8
1388 *
1389 * AVX2 is little endian, each of the 8 groups is a little-endian int32.
1390 * A group (int32) contains 4 registers.
1391 *
1392 * move the registers to correct positions with AND and SHIFT:
1393 * {00aaaaaa|00000000|00000000|00000000} x8 (>>0)
1394 * {bb000000|0000bbbb|00000000|00000000} x8 (>>2)
1395 * {00000000|cccc0000|000000cc|00000000} x8 (>>4)
1396 * {00000000|00000000|dddddd00|00000000} x8 (>>6)
1397 *
1398 * merge the registers with OR:
1399 * {bbaaaaaa|ccccbbbb|ddddddcc|00000000} x8
1400 * {AAA0|BBB0|CCC0|DDD0|EEE0|FFF0|GGG0|HHH0}
1401 *
1402 * SHUFFLE to:
1403 * {AAAB|BBCC|CDDD|0000|EEEF|FFGG|GHHH|0000}
1404 *
1405 * STORE the lower half and higher half respectively:
1406 * AAABBBCCCDDD0000
1407 * EEEFFFGGGHHH0000
1408 * AAABBBCCCDDDEEEFFFGGGHHH0000
1409 *
1410 * Note that the last 4 bytes are padding bytes.
1411 */
1412
1413 const uint8_t *r = reg_raw;
1414 uint8_t *t = reg_dense;
1415
1416 for (int i = 0; i < HLL_REGISTERS / 32 - 1; ++i) {
1417 __m256i x = _mm256_loadu_si256((__m256i *)r);
1418
1419 __m256i a1, a2, a3, a4;
1420 a1 = _mm256_and_si256(x, _mm256_set1_epi32(0x0000003f));
1421 a2 = _mm256_and_si256(x, _mm256_set1_epi32(0x00003f00));
1422 a3 = _mm256_and_si256(x, _mm256_set1_epi32(0x003f0000));
1423 a4 = _mm256_and_si256(x, _mm256_set1_epi32(0x3f000000));
1424
1425 a2 = _mm256_srli_epi32(a2, 2);
1426 a3 = _mm256_srli_epi32(a3, 4);
1427 a4 = _mm256_srli_epi32(a4, 6);
1428
1429 __m256i y1, y2, y;
1430 y1 = _mm256_or_si256(a1, a2);
1431 y2 = _mm256_or_si256(a3, a4);
1432 y = _mm256_or_si256(y1, y2);
1433 y = _mm256_shuffle_epi8(y, shuffle);
1434
1435 __m128i lower, higher;
1436 lower = _mm256_castsi256_si128(y);
1437 higher = _mm256_extracti128_si256(y, 1);
1438
1439 _mm_storeu_si128((__m128i *)t, lower);
1440 _mm_storeu_si128((__m128i *)(t + 12), higher);
1441
1442 r += 32;
1443 t += 24;
1444 }
1445
1446 /* Merge the last 32 registers normally
1447 * as the AVX2 algorithm needs 4 padding bytes at the end */
1448 for (int i = HLL_REGISTERS - 32; i < HLL_REGISTERS; i++) {
1449 HLL_DENSE_SET_REGISTER(reg_dense, i, reg_raw[i]);
1450 }
1451}
1452#endif
1453
1454#ifdef HAVE_AARCH64_NEON
1455/* A specialized version of hllDenseCompress, optimized for default configurations.
1456 * Based on the AVX2 version.
1457 *
1458 * Requirements:
1459 * 1) HLL_REGISTERS == 16384 && HLL_BITS == 6
1460 * 2) Aarch64 CPU supports NEON (checked at runtime in hllDenseCompress)
1461 *
1462 * reg_dense: pointer to the dense representation array (12288 bytes, 6 bits per register)
1463 * reg_raw: pointer to the raw representation array (16384 bytes, one byte per register)
1464 */
1465void hllDenseCompressAarch64(uint8_t *reg_dense, const uint8_t *reg_raw) {
1466 const uint8_t *r = reg_raw;
1467 uint8_t *t = reg_dense;
1468
1469 /* Shuffle pattern to collapse 16 raw bytes (16 regs x 8 bits)
1470 * into 12 bytes (16 regs x 6 bits) by dropping padding bytes 3, 7, 11, 15. */
1471 const uint8x16_t shuffle = {
1472 0, 1, 2,
1473 4, 5, 6,
1474 8, 9, 10,
1475 12, 13, 14,
1476 -1, -1, -1
1477 };
1478
1479 for (int i = 0; i < HLL_REGISTERS / 16 - 1; ++i) {
1480 /* Load 16 raw registers as four 32-bit lanes (LE). */
1481 const uint32x4_t x = vld1q_u32((const uint32_t *)r);
1482
1483 /* Extract the four 6-bit fields per 32-bit lane. */
1484 uint32x4_t a1, a2, a3, a4;
1485 a1 = vandq_u32(x, vdupq_n_u32(0x0000003f));
1486 a2 = vandq_u32(x, vdupq_n_u32(0x00003f00));
1487 a3 = vandq_u32(x, vdupq_n_u32(0x003f0000));
1488 a4 = vandq_u32(x, vdupq_n_u32(0x3f000000));
1489
1490 /* Align fields to packed positions within each lane. */
1491 a2 = vshrq_n_u32(a2, 2);
1492 a3 = vshrq_n_u32(a3, 4);
1493 a4 = vshrq_n_u32(a4, 6);
1494
1495 /* Combine fields per lane (32-bit). */
1496 uint32x4_t y32 = vorrq_u32(vorrq_u32(a1, a2), vorrq_u32(a3, a4));
1497
1498 /* Reinterpret to 8-bit uints; each lane now holds 3 packed bytes + one pad. */
1499 uint8x16_t y = vreinterpretq_u8_u32(y32);
1500
1501 /* Compact to 12 bytes by removing each lane's pad byte. */
1502 y = vqtbl1q_u8(y, shuffle);
1503
1504 /* Store the results. */
1505 vst1q_u8(t, y);
1506
1507 r += 16;
1508 t += 12;
1509 }
1510
1511 /* Merge the last 16 registers normally
1512 * as the NEON algorithm needs 4 padding bytes at the end */
1513 for (int i = HLL_REGISTERS - 16; i < HLL_REGISTERS; i++) {
1514 HLL_DENSE_SET_REGISTER(reg_dense, i, reg_raw[i]);
1515 }
1516}
1517#endif
1518
1519/* Compress raw registers to dense representation. */
1520void hllDenseCompress(uint8_t *reg_dense, const uint8_t *reg_raw) {
1521#if HLL_REGISTERS == 16384 && HLL_BITS == 6
1522#ifdef HAVE_AVX2
1523 if (HLL_USE_AVX2) {
1524 hllDenseCompressAVX2(reg_dense, reg_raw);
1525 return;
1526 }
1527#endif
1528
1529#ifdef HAVE_AARCH64_NEON
1530 if (HLL_USE_NEON) {
1531 hllDenseCompressAarch64(reg_dense, reg_raw);
1532 return;
1533 }
1534#endif
1535#endif
1536
1537 for (int i = 0; i < HLL_REGISTERS; i++) {
1538 HLL_DENSE_SET_REGISTER(reg_dense, i, reg_raw[i]);
1539 }
1540}
1541
1542/* ========================== HyperLogLog commands ========================== */
1543
1544/* Create an HLL object. We always create the HLL using sparse encoding.
1545 * This will be upgraded to the dense representation as needed. */
1546robj *createHLLObject(void) {
1547 robj *o;
1548 struct hllhdr *hdr;
1549 sds s;
1550 uint8_t *p;
1551 int sparselen = HLL_HDR_SIZE +
1552 (((HLL_REGISTERS+(HLL_SPARSE_XZERO_MAX_LEN-1)) /
1553 HLL_SPARSE_XZERO_MAX_LEN)*2);
1554 int aux;
1555
1556 /* Populate the sparse representation with as many XZERO opcodes as
1557 * needed to represent all the registers. */
1558 aux = HLL_REGISTERS;
1559 s = sdsnewlen(NULL,sparselen);
1560 p = (uint8_t*)s + HLL_HDR_SIZE;
1561 while(aux) {
1562 int xzero = HLL_SPARSE_XZERO_MAX_LEN;
1563 if (xzero > aux) xzero = aux;
1564 HLL_SPARSE_XZERO_SET(p,xzero);
1565 p += 2;
1566 aux -= xzero;
1567 }
1568 serverAssert((p-(uint8_t*)s) == sparselen);
1569
1570 /* Create the actual object. */
1571 o = createObject(OBJ_STRING,s);
1572 hdr = o->ptr;
1573 memcpy(hdr->magic,"HYLL",4);
1574 hdr->encoding = HLL_SPARSE;
1575 return o;
1576}
1577
1578/* Check if the object is a String with a valid HLL representation.
1579 * Return C_OK if this is true, otherwise reply to the client
1580 * with an error and return C_ERR. */
1581int isHLLObjectOrReply(client *c, robj *o) {
1582 struct hllhdr *hdr;
1583
1584 /* Key exists, check type */
1585 if (checkType(c,o,OBJ_STRING))
1586 return C_ERR; /* Error already sent. */
1587
1588 if (!sdsEncodedObject(o)) goto invalid;
1589 if (stringObjectLen(o) < sizeof(*hdr)) goto invalid;
1590 hdr = o->ptr;
1591
1592 /* Magic should be "HYLL". */
1593 if (hdr->magic[0] != 'H' || hdr->magic[1] != 'Y' ||
1594 hdr->magic[2] != 'L' || hdr->magic[3] != 'L') goto invalid;
1595
1596 if (hdr->encoding > HLL_MAX_ENCODING) goto invalid;
1597
1598 /* Dense representation string length should match exactly. */
1599 if (hdr->encoding == HLL_DENSE &&
1600 stringObjectLen(o) != HLL_DENSE_SIZE) goto invalid;
1601
1602 /* All tests passed. */
1603 return C_OK;
1604
1605invalid:
1606 addReplyError(c,"-WRONGTYPE Key is not a valid "
1607 "HyperLogLog string value.");
1608 return C_ERR;
1609}
1610
1611/* PFADD var ele ele ele ... ele => :0 or :1 */
1612void pfaddCommand(client *c) {
1613 uint64_t oldlen;
1614 dictEntryLink link;
1615 size_t oldsize = 0;
1616 kvobj *kv = lookupKeyWriteWithLink(c->db,c->argv[1], &link);
1617
1618 struct hllhdr *hdr;
1619 int updated = 0, j;
1620
1621 if (kv == NULL) {
1622 /* Create the key with a string value of the exact length to
1623 * hold our HLL data structure. sdsnewlen() when NULL is passed
1624 * is guaranteed to return bytes initialized to zero. */
1625 robj *o = createHLLObject();
1626 kv = dbAddByLink(c->db, c->argv[1], &o, &link);
1627 updated++;
1628 } else {
1629 if (isHLLObjectOrReply(c,kv) != C_OK) return;
1630 kv = dbUnshareStringValue(c->db,c->argv[1],kv);
1631 }
1632 oldlen = stringObjectLen(kv);
1633 if (server.memory_tracking_per_slot)
1634 oldsize = stringObjectAllocSize(kv);
1635
1636 /* Perform the low level ADD operation for every element. */
1637 for (j = 2; j < c->argc; j++) {
1638 int retval = hllAdd(kv, (unsigned char*)c->argv[j]->ptr,
1639 sdslen(c->argv[j]->ptr));
1640 switch(retval) {
1641 case 1:
1642 updated++;
1643 break;
1644 case -1:
1645 addReplyError(c,invalid_hll_err);
1646 if (server.memory_tracking_per_slot)
1647 updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, stringObjectAllocSize(kv));
1648 return;
1649 }
1650 }
1651
1652 hdr = kv->ptr;
1653 updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr), OBJ_STRING, oldlen, stringObjectLen(kv));
1654 if (server.memory_tracking_per_slot)
1655 updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, stringObjectAllocSize(kv));
1656 if (updated) {
1657 HLL_INVALIDATE_CACHE(hdr);
1658 keyModified(c,c->db,c->argv[1],kv,1);
1659 notifyKeyspaceEvent(NOTIFY_STRING,"pfadd",c->argv[1],c->db->id);
1660 server.dirty += updated;
1661 }
1662 addReply(c, updated ? shared.cone : shared.czero);
1663}
1664
1665/* PFCOUNT var -> approximated cardinality of set. */
1666void pfcountCommand(client *c) {
1667 struct hllhdr *hdr;
1668 uint64_t card;
1669
1670 /* Case 1: multi-key keys, cardinality of the union.
1671 *
1672 * When multiple keys are specified, PFCOUNT actually computes
1673 * the cardinality of the merge of the N HLLs specified. */
1674 if (c->argc > 2) {
1675 uint8_t max[HLL_HDR_SIZE+HLL_REGISTERS], *registers;
1676 int j;
1677
1678 /* Compute an HLL with M[i] = MAX(M[i]_j). */
1679 memset(max,0,sizeof(max));
1680 hdr = (struct hllhdr*) max;
1681 hdr->encoding = HLL_RAW; /* Special internal-only encoding. */
1682 registers = max + HLL_HDR_SIZE;
1683 for (j = 1; j < c->argc; j++) {
1684 /* Check type and size. */
1685 kvobj *o = lookupKeyRead(c->db,c->argv[j]);
1686 if (o == NULL) continue; /* Assume empty HLL for non existing var.*/
1687 if (isHLLObjectOrReply(c,o) != C_OK) return;
1688
1689 /* Merge with this HLL with our 'max' HLL by setting max[i]
1690 * to MAX(max[i],hll[i]). */
1691 if (hllMerge(registers,o) == C_ERR) {
1692 addReplyError(c,invalid_hll_err);
1693 return;
1694 }
1695 }
1696
1697 /* Compute cardinality of the resulting set. */
1698 addReplyLongLong(c,hllCount(hdr,NULL));
1699 return;
1700 }
1701
1702 /* Case 2: cardinality of the single HLL.
1703 *
1704 * The user specified a single key. Either return the cached value
1705 * or compute one and update the cache.
1706 *
1707 * Since a HLL is a regular Redis string type value, updating the cache does
1708 * modify the value. We do a lookupKeyRead anyway since this is flagged as a
1709 * read-only command. The difference is that with lookupKeyWrite, a
1710 * logically expired key on a replica is deleted, while with lookupKeyRead
1711 * it isn't, but the lookup returns NULL either way if the key is logically
1712 * expired, which is what matters here. */
1713 kvobj *o = lookupKeyRead(c->db, c->argv[1]);
1714 if (o == NULL) {
1715 /* No key? Cardinality is zero since no element was added, otherwise
1716 * we would have a key as HLLADD creates it as a side effect. */
1717 addReply(c,shared.czero);
1718 } else {
1719 if (isHLLObjectOrReply(c,o) != C_OK) return;
1720 o = dbUnshareStringValue(c->db,c->argv[1],o);
1721
1722 /* Check if the cached cardinality is valid. */
1723 hdr = o->ptr;
1724 if (HLL_VALID_CACHE(hdr)) {
1725 /* Just return the cached value. */
1726 card = (uint64_t)hdr->card[0];
1727 card |= (uint64_t)hdr->card[1] << 8;
1728 card |= (uint64_t)hdr->card[2] << 16;
1729 card |= (uint64_t)hdr->card[3] << 24;
1730 card |= (uint64_t)hdr->card[4] << 32;
1731 card |= (uint64_t)hdr->card[5] << 40;
1732 card |= (uint64_t)hdr->card[6] << 48;
1733 card |= (uint64_t)hdr->card[7] << 56;
1734 } else {
1735 int invalid = 0;
1736 /* Recompute it and update the cached value. */
1737 card = hllCount(hdr,&invalid);
1738 if (invalid) {
1739 addReplyError(c,invalid_hll_err);
1740 return;
1741 }
1742 hdr->card[0] = card & 0xff;
1743 hdr->card[1] = (card >> 8) & 0xff;
1744 hdr->card[2] = (card >> 16) & 0xff;
1745 hdr->card[3] = (card >> 24) & 0xff;
1746 hdr->card[4] = (card >> 32) & 0xff;
1747 hdr->card[5] = (card >> 40) & 0xff;
1748 hdr->card[6] = (card >> 48) & 0xff;
1749 hdr->card[7] = (card >> 56) & 0xff;
1750 /* This is considered a read-only command even if the cached value
1751 * may be modified and given that the HLL is a Redis string
1752 * we need to propagate the change. */
1753 keyModified(c,c->db,c->argv[1],o,1);
1754 server.dirty++;
1755 }
1756 addReplyLongLong(c,card);
1757 }
1758}
1759
1760/* PFMERGE dest src1 src2 src3 ... srcN => OK */
1761void pfmergeCommand(client *c) {
1762 uint8_t max[HLL_REGISTERS];
1763 struct hllhdr *hdr;
1764 int j;
1765 int use_dense = 0; /* Use dense representation as target? */
1766 size_t oldsize = 0;
1767
1768 /* Compute an HLL with M[i] = MAX(M[i]_j).
1769 * We store the maximum into the max array of registers. We'll write
1770 * it to the target variable later. */
1771 memset(max,0,sizeof(max));
1772 for (j = 1; j < c->argc; j++) {
1773 /* Check type and size. */
1774 kvobj *o = lookupKeyRead(c->db, c->argv[j]);
1775 if (o == NULL) continue; /* Assume empty HLL for non existing var. */
1776 if (isHLLObjectOrReply(c, o) != C_OK) return;
1777
1778 /* If at least one involved HLL is dense, use the dense representation
1779 * as target ASAP to save time and avoid the conversion step. */
1780 hdr = o->ptr;
1781 if (hdr->encoding == HLL_DENSE) use_dense = 1;
1782
1783 /* Merge with this HLL with our 'max' HLL by setting max[i]
1784 * to MAX(max[i],hll[i]). */
1785 if (hllMerge(max,o) == C_ERR) {
1786 addReplyError(c,invalid_hll_err);
1787 return;
1788 }
1789 }
1790
1791 /* Create / unshare the destination key's value if needed. */
1792 dictEntryLink link;
1793 kvobj *kv = lookupKeyWriteWithLink(c->db,c->argv[1],&link);
1794 if (kv == NULL) {
1795 /* Create the key with a string value of the exact length to
1796 * hold our HLL data structure. sdsnewlen() when NULL is passed
1797 * is guaranteed to return bytes initialized to zero. */
1798 robj *o = createHLLObject();
1799 kv = dbAddByLink(c->db, c->argv[1], &o, &link);
1800 } else {
1801 /* If key exists we are sure it's of the right type/size
1802 * since we checked when merging the different HLLs, so we
1803 * don't check again. */
1804 kv = dbUnshareStringValue(c->db,c->argv[1],kv);
1805 }
1806
1807 uint64_t oldLen = stringObjectLen(kv);
1808 if (server.memory_tracking_per_slot)
1809 oldsize = stringObjectAllocSize(kv);
1810
1811 /* Convert the destination object to dense representation if at least
1812 * one of the inputs was dense. */
1813 if (use_dense && hllSparseToDense(kv) == C_ERR) {
1814 addReplyError(c,invalid_hll_err);
1815 return;
1816 }
1817
1818 /* Write the resulting HLL to the destination HLL registers and
1819 * invalidate the cached value. */
1820 if (use_dense) {
1821 hdr = kv->ptr;
1822 hllDenseCompress(hdr->registers, max);
1823 } else {
1824 for (j = 0; j < HLL_REGISTERS; j++) {
1825 if (max[j] == 0) continue;
1826 hdr = kv->ptr;
1827 switch (hdr->encoding) {
1828 case HLL_DENSE: hllDenseSet(hdr->registers,j,max[j]); break;
1829 case HLL_SPARSE: hllSparseSet(kv,j,max[j]); break;
1830 }
1831 }
1832 }
1833 hdr = kv->ptr; /* o->ptr may be different now, as a side effect of
1834 last hllSparseSet() call. */
1835 HLL_INVALIDATE_CACHE(hdr);
1836
1837 if (server.memory_tracking_per_slot)
1838 updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, stringObjectAllocSize(kv));
1839 keyModified(c,c->db,c->argv[1],kv,1);
1840 /* We generate a PFADD event for PFMERGE for semantical simplicity
1841 * since in theory this is a mass-add of elements. */
1842 notifyKeyspaceEvent(NOTIFY_STRING,"pfadd",c->argv[1],c->db->id);
1843
1844 updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr),
1845 OBJ_STRING, oldLen, stringObjectLen(kv));
1846 server.dirty++;
1847 addReply(c,shared.ok);
1848}
1849
1850/* ========================== Testing / Debugging ========================== */
1851
1852/* PFSELFTEST
1853 * This command performs a self-test of the HLL registers implementation.
1854 * Something that is not easy to test from within the outside. */
1855#define HLL_TEST_CYCLES 1000
1856void pfselftestCommand(client *c) {
1857 unsigned int j, i;
1858 sds bitcounters = sdsnewlen(NULL,HLL_DENSE_SIZE);
1859 struct hllhdr *hdr = (struct hllhdr*) bitcounters, *hdr2;
1860 robj *o = NULL;
1861 uint8_t bytecounters[HLL_REGISTERS];
1862
1863 /* Test 1: access registers.
1864 * The test is conceived to test that the different counters of our data
1865 * structure are accessible and that setting their values both result in
1866 * the correct value to be retained and not affect adjacent values. */
1867 for (j = 0; j < HLL_TEST_CYCLES; j++) {
1868 /* Set the HLL counters and an array of unsigned byes of the
1869 * same size to the same set of random values. */
1870 for (i = 0; i < HLL_REGISTERS; i++) {
1871 unsigned int r = rand() & HLL_REGISTER_MAX;
1872
1873 bytecounters[i] = r;
1874 HLL_DENSE_SET_REGISTER(hdr->registers,i,r);
1875 }
1876 /* Check that we are able to retrieve the same values. */
1877 for (i = 0; i < HLL_REGISTERS; i++) {
1878 unsigned int val;
1879
1880 HLL_DENSE_GET_REGISTER(val,hdr->registers,i);
1881 if (val != bytecounters[i]) {
1882 addReplyErrorFormat(c,
1883 "TESTFAILED Register %d should be %d but is %d",
1884 i, (int) bytecounters[i], (int) val);
1885 goto cleanup;
1886 }
1887 }
1888 }
1889
1890 /* Test 2: approximation error.
1891 * The test adds unique elements and check that the estimated value
1892 * is always reasonable bounds.
1893 *
1894 * We check that the error is smaller than a few times than the expected
1895 * standard error, to make it very unlikely for the test to fail because
1896 * of a "bad" run.
1897 *
1898 * The test is performed with both dense and sparse HLLs at the same
1899 * time also verifying that the computed cardinality is the same. */
1900 memset(hdr->registers,0,HLL_DENSE_SIZE-HLL_HDR_SIZE);
1901 o = createHLLObject();
1902 double relerr = 1.04/sqrt(HLL_REGISTERS);
1903 int64_t checkpoint = 1;
1904 uint64_t seed = (uint64_t)rand() | (uint64_t)rand() << 32;
1905 uint64_t ele;
1906 for (j = 1; j <= 10000000; j++) {
1907 ele = j ^ seed;
1908 hllDenseAdd(hdr->registers,(unsigned char*)&ele,sizeof(ele));
1909 hllAdd(o,(unsigned char*)&ele,sizeof(ele));
1910
1911 /* Make sure that for small cardinalities we use sparse
1912 * encoding. */
1913 if (j == checkpoint && j < server.hll_sparse_max_bytes/2) {
1914 hdr2 = o->ptr;
1915 if (hdr2->encoding != HLL_SPARSE) {
1916 addReplyError(c, "TESTFAILED sparse encoding not used");
1917 goto cleanup;
1918 }
1919 }
1920
1921 /* Check that dense and sparse representations agree. */
1922 if (j == checkpoint && hllCount(hdr,NULL) != hllCount(o->ptr,NULL)) {
1923 addReplyError(c, "TESTFAILED dense/sparse disagree");
1924 goto cleanup;
1925 }
1926
1927 /* Check error. */
1928 if (j == checkpoint) {
1929 int64_t abserr = checkpoint - (int64_t)hllCount(hdr,NULL);
1930 uint64_t maxerr = ceil(relerr*6*checkpoint);
1931
1932 /* Adjust the max error we expect for cardinality 10
1933 * since from time to time it is statistically likely to get
1934 * much higher error due to collision, resulting into a false
1935 * positive. */
1936 if (j == 10) maxerr = 1;
1937
1938 if (abserr < 0) abserr = -abserr;
1939 if (abserr > (int64_t)maxerr) {
1940 addReplyErrorFormat(c,
1941 "TESTFAILED Too big error. card:%llu abserr:%llu",
1942 (unsigned long long) checkpoint,
1943 (unsigned long long) abserr);
1944 goto cleanup;
1945 }
1946 checkpoint *= 10;
1947 }
1948 }
1949
1950 /* Success! */
1951 addReply(c,shared.ok);
1952
1953cleanup:
1954 sdsfree(bitcounters);
1955 if (o) decrRefCount(o);
1956}
1957
1958/* Different debugging related operations about the HLL implementation.
1959 *
1960 * PFDEBUG GETREG <key>
1961 * PFDEBUG DECODE <key>
1962 * PFDEBUG ENCODING <key>
1963 * PFDEBUG TODENSE <key>
1964 * PFDEBUG SIMD (ON|OFF)
1965 */
1966void pfdebugCommand(client *c) {
1967 char *cmd = c->argv[1]->ptr;
1968 struct hllhdr *hdr;
1969 kvobj *o;
1970 int j;
1971 size_t oldsize = 0;
1972
1973 if (!strcasecmp(cmd, "simd")) {
1974 if (c->argc != 3) goto arityerr;
1975
1976 if (!strcasecmp(c->argv[2]->ptr, "on")) {
1977#if defined(HAVE_AVX2) || defined(HAVE_AARCH64_NEON)
1978 simd_enabled = 1;
1979#endif
1980 } else if (!strcasecmp(c->argv[2]->ptr, "off")) {
1981#if defined(HAVE_AVX2) || defined(HAVE_AARCH64_NEON)
1982 simd_enabled = 0;
1983#endif
1984 } else {
1985 addReplyError(c, "Argument must be ON or OFF");
1986 }
1987
1988 addReplyStatus(c, HLL_USE_AVX2 || HLL_USE_NEON ? "enabled" : "disabled");
1989
1990 return;
1991 }
1992
1993 o = lookupKeyWrite(c->db,c->argv[2]);
1994 if (o == NULL) {
1995 addReplyError(c,"The specified key does not exist");
1996 return;
1997 }
1998 if (isHLLObjectOrReply(c,o) != C_OK) return;
1999 o = dbUnshareStringValue(c->db,c->argv[2],o);
2000 hdr = o->ptr;
2001 if (server.memory_tracking_per_slot)
2002 oldsize = stringObjectAllocSize(o);
2003
2004 /* PFDEBUG GETREG <key> */
2005 if (!strcasecmp(cmd,"getreg")) {
2006 if (c->argc != 3) goto arityerr;
2007
2008 if (hdr->encoding == HLL_SPARSE) {
2009 uint64_t oldlen = (uint64_t) stringObjectLen(o);
2010 if (hllSparseToDense(o) == C_ERR) {
2011 addReplyError(c,invalid_hll_err);
2012 return;
2013 }
2014 updateKeysizesHist(c->db, getKeySlot(c->argv[2]->ptr), OBJ_STRING, oldlen, stringObjectLen(o));
2015 if (server.memory_tracking_per_slot)
2016 updateSlotAllocSize(c->db, getKeySlot(c->argv[2]->ptr), oldsize, stringObjectAllocSize(o));
2017 server.dirty++; /* Force propagation on encoding change. */
2018 }
2019
2020 hdr = o->ptr;
2021 addReplyArrayLen(c,HLL_REGISTERS);
2022 for (j = 0; j < HLL_REGISTERS; j++) {
2023 uint8_t val;
2024
2025 HLL_DENSE_GET_REGISTER(val,hdr->registers,j);
2026 addReplyLongLong(c,val);
2027 }
2028 }
2029 /* PFDEBUG DECODE <key> */
2030 else if (!strcasecmp(cmd,"decode")) {
2031 if (c->argc != 3) goto arityerr;
2032
2033 uint8_t *p = o->ptr, *end = p+sdslen(o->ptr);
2034 sds decoded = sdsempty();
2035
2036 if (hdr->encoding != HLL_SPARSE) {
2037 sdsfree(decoded);
2038 addReplyError(c,"HLL encoding is not sparse");
2039 return;
2040 }
2041
2042 p += HLL_HDR_SIZE;
2043 while(p < end) {
2044 int runlen, regval;
2045
2046 if (HLL_SPARSE_IS_ZERO(p)) {
2047 runlen = HLL_SPARSE_ZERO_LEN(p);
2048 p++;
2049 decoded = sdscatprintf(decoded,"z:%d ",runlen);
2050 } else if (HLL_SPARSE_IS_XZERO(p)) {
2051 runlen = HLL_SPARSE_XZERO_LEN(p);
2052 p += 2;
2053 decoded = sdscatprintf(decoded,"Z:%d ",runlen);
2054 } else {
2055 runlen = HLL_SPARSE_VAL_LEN(p);
2056 regval = HLL_SPARSE_VAL_VALUE(p);
2057 p++;
2058 decoded = sdscatprintf(decoded,"v:%d,%d ",regval,runlen);
2059 }
2060 }
2061 decoded = sdstrim(decoded," ");
2062 addReplyBulkCBuffer(c,decoded,sdslen(decoded));
2063 sdsfree(decoded);
2064 }
2065 /* PFDEBUG ENCODING <key> */
2066 else if (!strcasecmp(cmd,"encoding")) {
2067 char *encodingstr[2] = {"dense","sparse"};
2068 if (c->argc != 3) goto arityerr;
2069
2070 addReplyStatus(c,encodingstr[hdr->encoding]);
2071 }
2072 /* PFDEBUG TODENSE <key> */
2073 else if (!strcasecmp(cmd,"todense")) {
2074 int conv = 0;
2075 if (c->argc != 3) goto arityerr;
2076
2077 if (hdr->encoding == HLL_SPARSE) {
2078 int64_t oldlen = (int64_t) stringObjectLen(o);
2079 if (hllSparseToDense(o) == C_ERR) {
2080 addReplyError(c,invalid_hll_err);
2081 return;
2082 }
2083 updateKeysizesHist(c->db, getKeySlot(c->argv[2]->ptr), OBJ_STRING, oldlen, stringObjectLen(o));
2084 if (server.memory_tracking_per_slot)
2085 updateSlotAllocSize(c->db, getKeySlot(c->argv[2]->ptr), oldsize, stringObjectAllocSize(o));
2086 conv = 1;
2087 server.dirty++; /* Force propagation on encoding change. */
2088 }
2089 addReply(c,conv ? shared.cone : shared.czero);
2090 } else {
2091 addReplyErrorFormat(c,"Unknown PFDEBUG subcommand '%s'", cmd);
2092 }
2093 return;
2094
2095arityerr:
2096 addReplyErrorFormat(c,
2097 "Wrong number of arguments for the '%s' subcommand",cmd);
2098}
2099
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-30 01:15:23 +0000