1/* hyperloglog.c - Redis HyperLogLog probabilistic cardinality approximation.
2 * This file implements the algorithm and the exported Redis commands.
3 *
4 * Copyright (c) 2014, Salvatore Sanfilippo <antirez at gmail dot com>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of Redis nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without
17 * specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#include "hyperloglog.hpp"
33#include "sds.hpp"
34
35#include <assert.h>
36#include <stdint.h>
37#include <math.h>
38#include <stddef.h>
39#include <string.h>
40#include <stdlib.h>
41
42#define HLL_SPARSE_MAX_BYTES 3000
43
44/* The Redis HyperLogLog implementation is based on the following ideas:
45 *
46 * * The use of a 64 bit hash function as proposed in [1], in order to don't
47 * limited to cardinalities up to 10^9, at the cost of just 1 additional
48 * bit per register.
49 * * The use of 16384 6-bit registers for a great level of accuracy, using
50 * a total of 12k per key.
51 * * The use of the Redis string data type. No new type is introduced.
52 * * No attempt is made to compress the data structure as in [1]. Also the
53 * algorithm used is the original HyperLogLog Algorithm as in [2], with
54 * the only difference that a 64 bit hash function is used, so no correction
55 * is performed for values near 2^32 as in [1].
56 *
57 * [1] Heule, Nunkesser, Hall: HyperLogLog in Practice: Algorithmic
58 * Engineering of a State of The Art Cardinality Estimation Algorithm.
59 *
60 * [2] P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The
61 * analysis of a near-optimal cardinality estimation algorithm.
62 *
63 * Redis uses two representations:
64 *
65 * 1) A "dense" representation where every entry is represented by
66 * a 6-bit integer.
67 * 2) A "sparse" representation using run length compression suitable
68 * for representing HyperLogLogs with many registers set to 0 in
69 * a memory efficient way.
70 *
71 *
72 * HLL header
73 * ===
74 *
75 * Both the dense and sparse representation have a 16 byte header as follows:
76 *
77 * +------+---+-----+----------+
78 * | HYLL | E | N/U | Cardin. |
79 * +------+---+-----+----------+
80 *
81 * The first 4 bytes are a magic string set to the bytes "HYLL".
82 * "E" is one byte encoding, currently set to HLL_DENSE or
83 * HLL_SPARSE. N/U are three not used bytes.
84 *
85 * The "Cardin." field is a 64 bit integer stored in little endian format
86 * with the latest cardinality computed that can be reused if the data
87 * structure was not modified since the last computation (this is useful
88 * because there are high probabilities that HLLADD operations don't
89 * modify the actual data structure and hence the approximated cardinality).
90 *
91 * When the most significant bit in the most significant byte of the cached
92 * cardinality is set, it means that the data structure was modified and
93 * we can't reuse the cached value that must be recomputed.
94 *
95 * Dense representation
96 * ===
97 *
98 * The dense representation used by Redis is the following:
99 *
100 * +--------+--------+--------+------// //--+
101 * |11000000|22221111|33333322|55444444 .... |
102 * +--------+--------+--------+------// //--+
103 *
104 * The 6 bits counters are encoded one after the other starting from the
105 * LSB to the MSB, and using the next bytes as needed.
106 *
107 * Sparse representation
108 * ===
109 *
110 * The sparse representation encodes registers using a run length
111 * encoding composed of three opcodes, two using one byte, and one using
112 * of two bytes. The opcodes are called ZERO, XZERO and VAL.
113 *
114 * ZERO opcode is represented as 00xxxxxx. The 6-bit integer represented
115 * by the six bits 'xxxxxx', plus 1, means that there are N registers set
116 * to 0. This opcode can represent from 1 to 64 contiguous registers set
117 * to the value of 0.
118 *
119 * XZERO opcode is represented by two bytes 01xxxxxx yyyyyyyy. The 14-bit
120 * integer represented by the bits 'xxxxxx' as most significant bits and
121 * 'yyyyyyyy' as least significant bits, plus 1, means that there are N
122 * registers set to 0. This opcode can represent from 0 to 16384 contiguous
123 * registers set to the value of 0.
124 *
125 * VAL opcode is represented as 1vvvvvxx. It contains a 5-bit integer
126 * representing the value of a register, and a 2-bit integer representing
127 * the number of contiguous registers set to that value 'vvvvv'.
128 * To obtain the value and run length, the integers vvvvv and xx must be
129 * incremented by one. This opcode can represent values from 1 to 32,
130 * repeated from 1 to 4 times.
131 *
132 * The sparse representation can't represent registers with a value greater
133 * than 32, however it is very unlikely that we find such a register in an
134 * HLL with a cardinality where the sparse representation is still more
135 * memory efficient than the dense representation. When this happens the
136 * HLL is converted to the dense representation.
137 *
138 * The sparse representation is purely positional. For example a sparse
139 * representation of an empty HLL is just: XZERO:16384.
140 *
141 * An HLL having only 3 non-zero registers at position 1000, 1020, 1021
142 * respectively set to 2, 3, 3, is represented by the following three
143 * opcodes:
144 *
145 * XZERO:1000 (Registers 0-999 are set to 0)
146 * VAL:2,1 (1 register set to value 2, that is register 1000)
147 * ZERO:19 (Registers 1001-1019 set to 0)
148 * VAL:3,2 (2 registers set to value 3, that is registers 1020,1021)
149 * XZERO:15362 (Registers 1022-16383 set to 0)
150 *
151 * In the example the sparse representation used just 7 bytes instead
152 * of 12k in order to represent the HLL registers. In general for low
153 * cardinality there is a big win in terms of space efficiency, traded
154 * with CPU time since the sparse representation is slower to access:
155 *
156 * The following table shows average cardinality vs bytes used, 100
157 * samples per cardinality (when the set was not representable because
158 * of registers with too big value, the dense representation size was used
159 * as a sample).
160 *
161 * 100 267
162 * 200 485
163 * 300 678
164 * 400 859
165 * 500 1033
166 * 600 1205
167 * 700 1375
168 * 800 1544
169 * 900 1713
170 * 1000 1882
171 * 2000 3480
172 * 3000 4879
173 * 4000 6089
174 * 5000 7138
175 * 6000 8042
176 * 7000 8823
177 * 8000 9500
178 * 9000 10088
179 * 10000 10591
180 *
181 * The dense representation uses 12288 bytes, so there is a big win up to
182 * a cardinality of ~2000-3000. For bigger cardinalities the constant times
183 * involved in updating the sparse representation is not justified by the
184 * memory savings. The exact maximum length of the sparse representation
185 * when this implementation switches to the dense representation is
186 * configured via the define server.hll_sparse_max_bytes.
187 */
188
189struct hllhdr {
190 char magic[4]; /* "HYLL" */
191 uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
192 uint8_t notused[3]; /* Reserved for future use, must be zero. */
193 uint8_t card[8]; /* Cached cardinality, little endian. */
194 uint8_t registers[]; /* Data bytes. */
195};
196
197/* The cached cardinality MSB is used to signal validity of the cached value. */
198#define HLL_INVALIDATE_CACHE(hdr) (hdr)->card[7] |= (1<<7)
199#define HLL_VALID_CACHE(hdr) (((hdr)->card[7] & (1<<7)) == 0)
200
201#define HLL_P 14 /* The greater is P, the smaller the error. */
202#define HLL_Q (64-HLL_P) /* The number of bits of the hash value used for
203 determining the number of leading zeros. */
204#define HLL_REGISTERS (1<<HLL_P) /* With P=14, 16384 registers. */
205#define HLL_P_MASK (HLL_REGISTERS-1) /* Mask to index register. */
206#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
207#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
208#define HLL_HDR_SIZE sizeof(struct hllhdr)
209#define HLL_DENSE_SIZE (HLL_HDR_SIZE+((HLL_REGISTERS*HLL_BITS+7)/8))
210#define HLL_DENSE 0 /* Dense encoding. */
211#define HLL_SPARSE 1 /* Sparse encoding. */
212#define HLL_RAW 255 /* Only used internally, never exposed. */
213#define HLL_MAX_ENCODING 1
214
215/* =========================== Low level bit macros ========================= */
216
217/* Macros to access the dense representation.
218 *
219 * We need to get and set 6 bit counters in an array of 8 bit bytes.
220 * We use macros to make sure the code is inlined since speed is critical
221 * especially in order to compute the approximated cardinality in
222 * HLLCOUNT where we need to access all the registers at once.
223 * For the same reason we also want to avoid conditionals in this code path.
224 *
225 * +--------+--------+--------+------//
226 * |11000000|22221111|33333322|55444444
227 * +--------+--------+--------+------//
228 *
229 * Note: in the above representation the most significant bit (MSB)
230 * of every byte is on the left. We start using bits from the LSB to MSB,
231 * and so forth passing to the next byte.
232 *
233 * Example, we want to access to counter at pos = 1 ("111111" in the
234 * illustration above).
235 *
236 * The index of the first byte b0 containing our data is:
237 *
238 * b0 = 6 * pos / 8 = 0
239 *
240 * +--------+
241 * |11000000| <- Our byte at b0
242 * +--------+
243 *
244 * The position of the first bit (counting from the LSB = 0) in the byte
245 * is given by:
246 *
247 * fb = 6 * pos % 8 -> 6
248 *
249 * Right shift b0 of 'fb' bits.
250 *
251 * +--------+
252 * |11000000| <- Initial value of b0
253 * |00000011| <- After right shift of 6 pos.
254 * +--------+
255 *
256 * Left shift b1 of bits 8-fb bits (2 bits)
257 *
258 * +--------+
259 * |22221111| <- Initial value of b1
260 * |22111100| <- After left shift of 2 bits.
261 * +--------+
262 *
263 * OR the two bits, and finally AND with 111111 (63 in decimal) to
264 * clean the higher order bits we are not interested in:
265 *
266 * +--------+
267 * |00000011| <- b0 right shifted
268 * |22111100| <- b1 left shifted
269 * |22111111| <- b0 OR b1
270 * | 111111| <- (b0 OR b1) AND 63, our value.
271 * +--------+
272 *
273 * We can try with a different example, like pos = 0. In this case
274 * the 6-bit counter is actually contained in a single byte.
275 *
276 * b0 = 6 * pos / 8 = 0
277 *
278 * +--------+
279 * |11000000| <- Our byte at b0
280 * +--------+
281 *
282 * fb = 6 * pos % 8 = 0
283 *
284 * So we right shift of 0 bits (no shift in practice) and
285 * left shift the next byte of 8 bits, even if we don't use it,
286 * but this has the effect of clearing the bits so the result
287 * will not be affacted after the OR.
288 *
289 * -------------------------------------------------------------------------
290 *
291 * Setting the register is a bit more complex, let's assume that 'val'
292 * is the value we want to set, already in the right range.
293 *
294 * We need two steps, in one we need to clear the bits, and in the other
295 * we need to bitwise-OR the new bits.
296 *
297 * Let's try with 'pos' = 1, so our first byte at 'b' is 0,
298 *
299 * "fb" is 6 in this case.
300 *
301 * +--------+
302 * |11000000| <- Our byte at b0
303 * +--------+
304 *
305 * To create a AND-mask to clear the bits about this position, we just
306 * initialize the mask with the value 63, left shift it of "fs" bits,
307 * and finally invert the result.
308 *
309 * +--------+
310 * |00111111| <- "mask" starts at 63
311 * |11000000| <- "mask" after left shift of "ls" bits.
312 * |00111111| <- "mask" after invert.
313 * +--------+
314 *
315 * Now we can bitwise-AND the byte at "b" with the mask, and bitwise-OR
316 * it with "val" left-shifted of "ls" bits to set the new bits.
317 *
318 * Now let's focus on the next byte b1:
319 *
320 * +--------+
321 * |22221111| <- Initial value of b1
322 * +--------+
323 *
324 * To build the AND mask we start again with the 63 value, right shift
325 * it by 8-fb bits, and invert it.
326 *
327 * +--------+
328 * |00111111| <- "mask" set at 2&6-1
329 * |00001111| <- "mask" after the right shift by 8-fb = 2 bits
330 * |11110000| <- "mask" after bitwise not.
331 * +--------+
332 *
333 * Now we can mask it with b+1 to clear the old bits, and bitwise-OR
334 * with "val" left-shifted by "rs" bits to set the new value.
335 */
336
337/* Note: if we access the last counter, we will also access the b+1 byte
338 * that is out of the array, but sds strings always have an implicit null
339 * term, so the byte exists, and we can skip the conditional (or the need
340 * to allocate 1 byte more explicitly). */
341
342/* Store the value of the register at position 'regnum' into variable 'target'.
343 * 'p' is an array of unsigned bytes. */
344#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
345 uint8_t *_p = (uint8_t*) p; \
346 unsigned long _byte = regnum*HLL_BITS/8; \
347 unsigned long _fb = regnum*HLL_BITS&7; \
348 unsigned long _fb8 = 8 - _fb; \
349 unsigned long b0 = _p[_byte]; \
350 unsigned long b1 = _p[_byte+1]; \
351 target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
352} while(0)
353
354/* Set the value of the register at position 'regnum' to 'val'.
355 * 'p' is an array of unsigned bytes. */
356#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
357 uint8_t *_p = (uint8_t*) p; \
358 unsigned long _byte = regnum*HLL_BITS/8; \
359 unsigned long _fb = regnum*HLL_BITS&7; \
360 unsigned long _fb8 = 8 - _fb; \
361 unsigned long _v = val; \
362 _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
363 _p[_byte] |= _v << _fb; \
364 _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
365 _p[_byte+1] |= _v >> _fb8; \
366} while(0)
367
368/* Macros to access the sparse representation.
369 * The macros parameter is expected to be an uint8_t pointer. */
370#define HLL_SPARSE_XZERO_BIT 0x40 /* 01xxxxxx */
371#define HLL_SPARSE_VAL_BIT 0x80 /* 1vvvvvxx */
372#define HLL_SPARSE_IS_ZERO(p) (((*(p)) & 0xc0) == 0) /* 00xxxxxx */
373#define HLL_SPARSE_IS_XZERO(p) (((*(p)) & 0xc0) == HLL_SPARSE_XZERO_BIT)
374#define HLL_SPARSE_IS_VAL(p) ((*(p)) & HLL_SPARSE_VAL_BIT)
375#define HLL_SPARSE_ZERO_LEN(p) (((*(p)) & 0x3f)+1)
376#define HLL_SPARSE_XZERO_LEN(p) (((((*(p)) & 0x3f) << 8) | (*((p)+1)))+1)
377#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
378#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)
379#define HLL_SPARSE_VAL_MAX_VALUE 32
380#define HLL_SPARSE_VAL_MAX_LEN 4
381#define HLL_SPARSE_ZERO_MAX_LEN 64
382#define HLL_SPARSE_XZERO_MAX_LEN 16384
383#define HLL_SPARSE_VAL_SET(p,val,len) do { \
384 *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
385} while(0)
386#define HLL_SPARSE_ZERO_SET(p,len) do { \
387 *(p) = (len)-1; \
388} while(0)
389#define HLL_SPARSE_XZERO_SET(p,len) do { \
390 int _l = (len)-1; \
391 *(p) = (_l>>8) | HLL_SPARSE_XZERO_BIT; \
392 *((p)+1) = (_l&0xff); \
393} while(0)
394#define HLL_ALPHA_INF 0.721347520444481703680 /* constant for 0.5/ln(2) */
395
396/* ========================= HyperLogLog algorithm ========================= */
397
398/* Our hash function is MurmurHash2, 64 bit version.
399 * It was modified for Redis in order to provide the same result in
400 * big and little endian archs (endian neutral). */
401uint64_t MurmurHash64A (const void * key, int len, unsigned int seed) {
402 const uint64_t m = 0xc6a4a7935bd1e995;
403 const int r = 47;
404 uint64_t h = seed ^ (len * m);
405 const uint8_t *data = (const uint8_t *)key;
406 const uint8_t *end = data + (len-(len&7));
407
408 while(data != end) {
409 uint64_t k;
410
411#if (BYTE_ORDER == LITTLE_ENDIAN)
412 #ifdef USE_ALIGNED_ACCESS
413 memcpy(&k,data,sizeof(uint64_t));
414 #else
415 k = *((uint64_t*)data);
416 #endif
417#else
418 k = (uint64_t) data[0];
419 k |= (uint64_t) data[1] << 8;
420 k |= (uint64_t) data[2] << 16;
421 k |= (uint64_t) data[3] << 24;
422 k |= (uint64_t) data[4] << 32;
423 k |= (uint64_t) data[5] << 40;
424 k |= (uint64_t) data[6] << 48;
425 k |= (uint64_t) data[7] << 56;
426#endif
427
428 k *= m;
429 k ^= k >> r;
430 k *= m;
431 h ^= k;
432 h *= m;
433 data += 8;
434 }
435
436 switch(len & 7) {
437 case 7: h ^= (uint64_t)data[6] << 48; /* fall-thru */
438 case 6: h ^= (uint64_t)data[5] << 40; /* fall-thru */
439 case 5: h ^= (uint64_t)data[4] << 32; /* fall-thru */
440 case 4: h ^= (uint64_t)data[3] << 24; /* fall-thru */
441 case 3: h ^= (uint64_t)data[2] << 16; /* fall-thru */
442 case 2: h ^= (uint64_t)data[1] << 8; /* fall-thru */
443 case 1: h ^= (uint64_t)data[0];
444 h *= m; /* fall-thru */
445 };
446
447 h ^= h >> r;
448 h *= m;
449 h ^= h >> r;
450 return h;
451}
452
453/* Given a string element to add to the HyperLogLog, returns the length
454 * of the pattern 000..1 of the element hash. As a side effect 'regp' is
455 * set to the register index this element hashes to. */
456int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
457 uint64_t hash, bit, index;
458 int count;
459
460 /* Count the number of zeroes starting from bit HLL_REGISTERS
461 * (that is a power of two corresponding to the first bit we don't use
462 * as index). The max run can be 64-P+1 = Q+1 bits.
463 *
464 * Note that the final "1" ending the sequence of zeroes must be
465 * included in the count, so if we find "001" the count is 3, and
466 * the smallest count possible is no zeroes at all, just a 1 bit
467 * at the first position, that is a count of 1.
468 *
469 * This may sound like inefficient, but actually in the average case
470 * there are high probabilities to find a 1 after a few iterations. */
471 hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
472 index = hash & HLL_P_MASK; /* Register index. */
473 hash >>= HLL_P; /* Remove bits used to address the register. */
474 hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates
475 and count will be <= Q+1. */
476 bit = 1;
477 count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */
478 while((hash & bit) == 0) {
479 count++;
480 bit <<= 1;
481 }
482 *regp = (int) index;
483 return count;
484}
485
486/* ================== Dense representation implementation ================== */
487
488/* Low level function to set the dense HLL register at 'index' to the
489 * specified value if the current value is smaller than 'count'.
490 *
491 * 'registers' is expected to have room for HLL_REGISTERS plus an
492 * additional byte on the right. This requirement is met by sds strings
493 * automatically since they are implicitly null terminated.
494 *
495 * The function always succeed, however if as a result of the operation
496 * the approximated cardinality changed, 1 is returned. Otherwise 0
497 * is returned. */
498int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
499 uint8_t oldcount;
500
501 HLL_DENSE_GET_REGISTER(oldcount,registers,index);
502 if (count > oldcount) {
503 HLL_DENSE_SET_REGISTER(registers,index,count);
504 return 1;
505 } else {
506 return 0;
507 }
508}
509
510/* "Add" the element in the dense hyperloglog data structure.
511 * Actually nothing is added, but the max 0 pattern counter of the subset
512 * the element belongs to is incremented if needed.
513 *
514 * This is just a wrapper to hllDenseSet(), performing the hashing of the
515 * element in order to retrieve the index and zero-run count. */
516int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
517 long index;
518 uint8_t count = hllPatLen(ele,elesize,&index);
519 /* Update the register if this element produced a longer run of zeroes. */
520 return hllDenseSet(registers,index,count);
521}
522
523/* Compute the register histogram in the dense representation. */
524void hllDenseRegHisto(uint8_t *registers, int* reghisto) {
525 int j;
526
527 /* Redis default is to use 16384 registers 6 bits each. The code works
528 * with other values by modifying the defines, but for our target value
529 * we take a faster path with unrolled loops. */
530 if (HLL_REGISTERS == 16384 && HLL_BITS == 6) {
531 uint8_t *r = registers;
532 unsigned long r0, r1, r2, r3, r4, r5, r6, r7, r8, r9,
533 r10, r11, r12, r13, r14, r15;
534 for (j = 0; j < 1024; j++) {
535 /* Handle 16 registers per iteration. */
536 r0 = r[0] & 63;
537 r1 = (r[0] >> 6 | r[1] << 2) & 63;
538 r2 = (r[1] >> 4 | r[2] << 4) & 63;
539 r3 = (r[2] >> 2) & 63;
540 r4 = r[3] & 63;
541 r5 = (r[3] >> 6 | r[4] << 2) & 63;
542 r6 = (r[4] >> 4 | r[5] << 4) & 63;
543 r7 = (r[5] >> 2) & 63;
544 r8 = r[6] & 63;
545 r9 = (r[6] >> 6 | r[7] << 2) & 63;
546 r10 = (r[7] >> 4 | r[8] << 4) & 63;
547 r11 = (r[8] >> 2) & 63;
548 r12 = r[9] & 63;
549 r13 = (r[9] >> 6 | r[10] << 2) & 63;
550 r14 = (r[10] >> 4 | r[11] << 4) & 63;
551 r15 = (r[11] >> 2) & 63;
552
553 reghisto[r0]++;
554 reghisto[r1]++;
555 reghisto[r2]++;
556 reghisto[r3]++;
557 reghisto[r4]++;
558 reghisto[r5]++;
559 reghisto[r6]++;
560 reghisto[r7]++;
561 reghisto[r8]++;
562 reghisto[r9]++;
563 reghisto[r10]++;
564 reghisto[r11]++;
565 reghisto[r12]++;
566 reghisto[r13]++;
567 reghisto[r14]++;
568 reghisto[r15]++;
569
570 r += 12;
571 }
572 } else {
573 for(j = 0; j < HLL_REGISTERS; j++) {
574 unsigned long reg;
575 HLL_DENSE_GET_REGISTER(reg,registers,j);
576 reghisto[reg]++;
577 }
578 }
579}
580
581/* ================== Sparse representation implementation ================= */
582
583/* Convert the HLL with sparse representation given as input in its dense
584 * representation. Both representations are represented by SDS strings, and
585 * the input representation is freed as a side effect.
586 *
587 * The function returns C_OK if the sparse representation was valid,
588 * otherwise C_ERR is returned if the representation was corrupted. */
589int hllSparseToDense(robj *o) {
590 sds sparse = (sds) o->ptr, dense;
591 struct hllhdr *hdr, *oldhdr = (struct hllhdr*)sparse;
592 int idx = 0, runlen, regval;
593 uint8_t *p = (uint8_t*)sparse, *end = p+sdslen(sparse);
594
595 /* If the representation is already the right one return ASAP. */
596 hdr = (struct hllhdr*) sparse;
597 if (hdr->encoding == HLL_DENSE) return C_OK;
598
599 /* Create a string of the right size filled with zero bytes.
600 * Note that the cached cardinality is set to 0 as a side effect
601 * that is exactly the cardinality of an empty HLL. */
602 dense = sdsnewlen(NULL,HLL_DENSE_SIZE);
603 hdr = (struct hllhdr*) dense;
604 *hdr = *oldhdr; /* This will copy the magic and cached cardinality. */
605 hdr->encoding = HLL_DENSE;
606
607 /* Now read the sparse representation and set non-zero registers
608 * accordingly. */
609 p += HLL_HDR_SIZE;
610 while(p < end) {
611 if (HLL_SPARSE_IS_ZERO(p)) {
612 runlen = HLL_SPARSE_ZERO_LEN(p);
613 idx += runlen;
614 p++;
615 } else if (HLL_SPARSE_IS_XZERO(p)) {
616 runlen = HLL_SPARSE_XZERO_LEN(p);
617 idx += runlen;
618 p += 2;
619 } else {
620 runlen = HLL_SPARSE_VAL_LEN(p);
621 regval = HLL_SPARSE_VAL_VALUE(p);
622 while(runlen--) {
623 HLL_DENSE_SET_REGISTER(hdr->registers,idx,regval);
624 idx++;
625 }
626 p++;
627 }
628 }
629
630 /* If the sparse representation was valid, we expect to find idx
631 * set to HLL_REGISTERS. */
632 if (idx != HLL_REGISTERS) {
633 sdsfree(dense);
634 return C_ERR;
635 }
636
637 /* Free the old representation and set the new one. */
638 sdsfree((sds) o->ptr);
639 o->ptr = dense;
640 return C_OK;
641}
642
643/* Low level function to set the sparse HLL register at 'index' to the
644 * specified value if the current value is smaller than 'count'.
645 *
646 * The object 'o' is the String object holding the HLL. The function requires
647 * a reference to the object in order to be able to enlarge the string if
648 * needed.
649 *
650 * On success, the function returns 1 if the cardinality changed, or 0
651 * if the register for this element was not updated.
652 * On error (if the representation is invalid) -1 is returned.
653 *
654 * As a side effect the function may promote the HLL representation from
655 * sparse to dense: this happens when a register requires to be set to a value
656 * not representable with the sparse representation, or when the resulting
657 * size would be greater than server.hll_sparse_max_bytes. */
658int hllSparseSet(robj *o, long index, uint8_t count) {
659 struct hllhdr *hdr;
660 uint8_t oldcount, *sparse, *end, *p, *prev, *next;
661 long first, span;
662 long is_zero = 0, is_xzero = 0, is_val = 0, runlen = 0;
663 uint8_t seq[5], *n;
664 int last;
665 int len;
666 int seqlen;
667 int oldlen;
668 int deltalen;
669
670 /* If the count is too big to be representable by the sparse representation
671 * switch to dense representation. */
672 if (count > HLL_SPARSE_VAL_MAX_VALUE) goto promote;
673
674 /* When updating a sparse representation, sometimes we may need to
675 * enlarge the buffer for up to 3 bytes in the worst case (XZERO split
676 * into XZERO-VAL-XZERO). Make sure there is enough space right now
677 * so that the pointers we take during the execution of the function
678 * will be valid all the time. */
679 o->ptr = (sds) sdsMakeRoomFor((sds) o->ptr,3);
680
681 /* Step 1: we need to locate the opcode we need to modify to check
682 * if a value update is actually needed. */
683 sparse = p = ((uint8_t*)o->ptr) + HLL_HDR_SIZE;
684 end = p + sdslen((sds) o->ptr) - HLL_HDR_SIZE;
685
686 first = 0;
687 prev = NULL; /* Points to previous opcode at the end of the loop. */
688 next = NULL; /* Points to the next opcode at the end of the loop. */
689 span = 0;
690 while(p < end) {
691 long oplen;
692
693 /* Set span to the number of registers covered by this opcode.
694 *
695 * This is the most performance critical loop of the sparse
696 * representation. Sorting the conditionals from the most to the
697 * least frequent opcode in many-bytes sparse HLLs is faster. */
698 oplen = 1;
699 if (HLL_SPARSE_IS_ZERO(p)) {
700 span = HLL_SPARSE_ZERO_LEN(p);
701 } else if (HLL_SPARSE_IS_VAL(p)) {
702 span = HLL_SPARSE_VAL_LEN(p);
703 } else { /* XZERO. */
704 span = HLL_SPARSE_XZERO_LEN(p);
705 oplen = 2;
706 }
707 /* Break if this opcode covers the register as 'index'. */
708 if (index <= first+span-1) break;
709 prev = p;
710 p += oplen;
711 first += span;
712 }
713 if (span == 0) return -1; /* Invalid format. */
714
715 next = HLL_SPARSE_IS_XZERO(p) ? p+2 : p+1;
716 if (next >= end) next = NULL;
717
718 /* Cache current opcode type to avoid using the macro again and
719 * again for something that will not change.
720 * Also cache the run-length of the opcode. */
721 if (HLL_SPARSE_IS_ZERO(p)) {
722 is_zero = 1;
723 runlen = HLL_SPARSE_ZERO_LEN(p);
724 } else if (HLL_SPARSE_IS_XZERO(p)) {
725 is_xzero = 1;
726 runlen = HLL_SPARSE_XZERO_LEN(p);
727 } else {
728 is_val = 1;
729 runlen = HLL_SPARSE_VAL_LEN(p);
730 }
731
732 /* Step 2: After the loop:
733 *
734 * 'first' stores to the index of the first register covered
735 * by the current opcode, which is pointed by 'p'.
736 *
737 * 'next' ad 'prev' store respectively the next and previous opcode,
738 * or NULL if the opcode at 'p' is respectively the last or first.
739 *
740 * 'span' is set to the number of registers covered by the current
741 * opcode.
742 *
743 * There are different cases in order to update the data structure
744 * in place without generating it from scratch:
745 *
746 * A) If it is a VAL opcode already set to a value >= our 'count'
747 * no update is needed, regardless of the VAL run-length field.
748 * In this case PFADD returns 0 since no changes are performed.
749 *
750 * B) If it is a VAL opcode with len = 1 (representing only our
751 * register) and the value is less than 'count', we just update it
752 * since this is a trivial case. */
753 if (is_val) {
754 oldcount = HLL_SPARSE_VAL_VALUE(p);
755 /* Case A. */
756 if (oldcount >= count) return 0;
757
758 /* Case B. */
759 if (runlen == 1) {
760 HLL_SPARSE_VAL_SET(p,count,1);
761 goto updated;
762 }
763 }
764
765 /* C) Another trivial to handle case is a ZERO opcode with a len of 1.
766 * We can just replace it with a VAL opcode with our value and len of 1. */
767 if (is_zero && runlen == 1) {
768 HLL_SPARSE_VAL_SET(p,count,1);
769 goto updated;
770 }
771
772 /* D) General case.
773 *
774 * The other cases are more complex: our register requires to be updated
775 * and is either currently represented by a VAL opcode with len > 1,
776 * by a ZERO opcode with len > 1, or by an XZERO opcode.
777 *
778 * In those cases the original opcode must be split into multiple
779 * opcodes. The worst case is an XZERO split in the middle resuling into
780 * XZERO - VAL - XZERO, so the resulting sequence max length is
781 * 5 bytes.
782 *
783 * We perform the split writing the new sequence into the 'new' buffer
784 * with 'newlen' as length. Later the new sequence is inserted in place
785 * of the old one, possibly moving what is on the right a few bytes
786 * if the new sequence is longer than the older one. */
787 n = seq;
788 last = first+span-1; /* Last register covered by the sequence. */
789
790 if (is_zero || is_xzero) {
791 /* Handle splitting of ZERO / XZERO. */
792 if (index != first) {
793 len = index-first;
794 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
795 HLL_SPARSE_XZERO_SET(n,len);
796 n += 2;
797 } else {
798 HLL_SPARSE_ZERO_SET(n,len);
799 n++;
800 }
801 }
802 HLL_SPARSE_VAL_SET(n,count,1);
803 n++;
804 if (index != last) {
805 len = last-index;
806 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
807 HLL_SPARSE_XZERO_SET(n,len);
808 n += 2;
809 } else {
810 HLL_SPARSE_ZERO_SET(n,len);
811 n++;
812 }
813 }
814 } else {
815 /* Handle splitting of VAL. */
816 int curval = HLL_SPARSE_VAL_VALUE(p);
817
818 if (index != first) {
819 len = index-first;
820 HLL_SPARSE_VAL_SET(n,curval,len);
821 n++;
822 }
823 HLL_SPARSE_VAL_SET(n,count,1);
824 n++;
825 if (index != last) {
826 len = last-index;
827 HLL_SPARSE_VAL_SET(n,curval,len);
828 n++;
829 }
830 }
831
832 /* Step 3: substitute the new sequence with the old one.
833 *
834 * Note that we already allocated space on the sds string
835 * calling sdsMakeRoomFor(). */
836 seqlen = n-seq;
837 oldlen = is_xzero ? 2 : 1;
838 deltalen = seqlen-oldlen;
839
840 if (deltalen > 0 &&
841 sdslen((sds) o->ptr)+deltalen > HLL_SPARSE_MAX_BYTES) goto promote;
842 if (deltalen && next) memmove(next+deltalen,next,end-next);
843 sdsIncrLen((sds) o->ptr,deltalen);
844 memcpy(p,seq,seqlen);
845 end += deltalen;
846
847updated: {
848 /* Step 4: Merge adjacent values if possible.
849 *
850 * The representation was updated, however the resulting representation
851 * may not be optimal: adjacent VAL opcodes can sometimes be merged into
852 * a single one. */
853 p = prev ? prev : sparse;
854 int scanlen = 5; /* Scan up to 5 upcodes starting from prev. */
855 while (p < end && scanlen--) {
856 if (HLL_SPARSE_IS_XZERO(p)) {
857 p += 2;
858 continue;
859 } else if (HLL_SPARSE_IS_ZERO(p)) {
860 p++;
861 continue;
862 }
863 /* We need two adjacent VAL opcodes to try a merge, having
864 * the same value, and a len that fits the VAL opcode max len. */
865 if (p+1 < end && HLL_SPARSE_IS_VAL(p+1)) {
866 int v1 = HLL_SPARSE_VAL_VALUE(p);
867 int v2 = HLL_SPARSE_VAL_VALUE(p+1);
868 if (v1 == v2) {
869 int len = HLL_SPARSE_VAL_LEN(p)+HLL_SPARSE_VAL_LEN(p+1);
870 if (len <= HLL_SPARSE_VAL_MAX_LEN) {
871 HLL_SPARSE_VAL_SET(p+1,v1,len);
872 memmove(p,p+1,end-p);
873 sdsIncrLen((sds) o->ptr,-1);
874 end--;
875 /* After a merge we reiterate without incrementing 'p'
876 * in order to try to merge the just merged value with
877 * a value on its right. */
878 continue;
879 }
880 }
881 }
882 p++;
883 }
884
885 /* Invalidate the cached cardinality. */
886 hdr = (struct hllhdr *) o->ptr;
887 HLL_INVALIDATE_CACHE(hdr);
888 return 1;
889}
890promote: /* Promote to dense representation. */
891 if (hllSparseToDense(o) == C_ERR) return -1; /* Corrupted HLL. */
892 hdr = (struct hllhdr *) o->ptr;
893
894 /* We need to call hllDenseAdd() to perform the operation after the
895 * conversion. However the result must be 1, since if we need to
896 * convert from sparse to dense a register requires to be updated.
897 *
898 * Note that this in turn means that PFADD will make sure the command
899 * is propagated to slaves / AOF, so if there is a sparse -> dense
900 * conversion, it will be performed in all the slaves as well. */
901 int dense_retval = hllDenseSet(hdr->registers,index,count);
902 assert(dense_retval == 1);
903 return dense_retval;
904}
905
906/* "Add" the element in the sparse hyperloglog data structure.
907 * Actually nothing is added, but the max 0 pattern counter of the subset
908 * the element belongs to is incremented if needed.
909 *
910 * This function is actually a wrapper for hllSparseSet(), it only performs
911 * the hashshing of the elmenet to obtain the index and zeros run length. */
912int hllSparseAdd(robj *o, unsigned char *ele, size_t elesize) {
913 long index;
914 uint8_t count = hllPatLen(ele,elesize,&index);
915 /* Update the register if this element produced a longer run of zeroes. */
916 return hllSparseSet(o,index,count);
917}
918
919/* Compute the register histogram in the sparse representation. */
920void hllSparseRegHisto(uint8_t *sparse, int sparselen, int *invalid, int* reghisto) {
921 int idx = 0, runlen, regval;
922 uint8_t *end = sparse+sparselen, *p = sparse;
923
924 while(p < end) {
925 if (HLL_SPARSE_IS_ZERO(p)) {
926 runlen = HLL_SPARSE_ZERO_LEN(p);
927 idx += runlen;
928 reghisto[0] += runlen;
929 p++;
930 } else if (HLL_SPARSE_IS_XZERO(p)) {
931 runlen = HLL_SPARSE_XZERO_LEN(p);
932 idx += runlen;
933 reghisto[0] += runlen;
934 p += 2;
935 } else {
936 runlen = HLL_SPARSE_VAL_LEN(p);
937 regval = HLL_SPARSE_VAL_VALUE(p);
938 idx += runlen;
939 reghisto[regval] += runlen;
940 p++;
941 }
942 }
943 if (idx != HLL_REGISTERS && invalid) *invalid = 1;
944}
945
946/* ========================= HyperLogLog Count ==============================
947 * This is the core of the algorithm where the approximated count is computed.
948 * The function uses the lower level hllDenseRegHisto() and hllSparseRegHisto()
949 * functions as helpers to compute histogram of register values part of the
950 * computation, which is representation-specific, while all the rest is common. */
951
952/* Implements the register histogram calculation for uint8_t data type
953 * which is only used internally as speedup for PFCOUNT with multiple keys. */
954void hllRawRegHisto(uint8_t *registers, int* reghisto) {
955 uint64_t *word = (uint64_t*) registers;
956 uint8_t *bytes;
957 int j;
958
959 for (j = 0; j < HLL_REGISTERS/8; j++) {
960 if (*word == 0) {
961 reghisto[0] += 8;
962 } else {
963 bytes = (uint8_t*) word;
964 reghisto[bytes[0]]++;
965 reghisto[bytes[1]]++;
966 reghisto[bytes[2]]++;
967 reghisto[bytes[3]]++;
968 reghisto[bytes[4]]++;
969 reghisto[bytes[5]]++;
970 reghisto[bytes[6]]++;
971 reghisto[bytes[7]]++;
972 }
973 word++;
974 }
975}
976
977// somehow this is missing on some platforms
978#ifndef INFINITY
979// from math.h
980#define INFINITY 1e50f
981#endif
982
983
984/* Helper function sigma as defined in
985 * "New cardinality estimation algorithms for HyperLogLog sketches"
986 * Otmar Ertl, arXiv:1702.01284 */
987double hllSigma(double x) {
988 if (x == 1.) return INFINITY;
989 double zPrime;
990 double y = 1;
991 double z = x;
992 do {
993 x *= x;
994 zPrime = z;
995 z += x * y;
996 y += y;
997 } while(zPrime != z);
998 return z;
999}
1000
1001/* Helper function tau as defined in
1002 * "New cardinality estimation algorithms for HyperLogLog sketches"
1003 * Otmar Ertl, arXiv:1702.01284 */
1004double hllTau(double x) {
1005 if (x == 0. || x == 1.) return 0.;
1006 double zPrime;
1007 double y = 1.0;
1008 double z = 1 - x;
1009 do {
1010 x = sqrt(x);
1011 zPrime = z;
1012 y *= 0.5;
1013 z -= pow(1 - x, 2)*y;
1014 } while(zPrime != z);
1015 return z / 3;
1016}
1017
1018/* Return the approximated cardinality of the set based on the harmonic
1019 * mean of the registers values. 'hdr' points to the start of the SDS
1020 * representing the String object holding the HLL representation.
1021 *
1022 * If the sparse representation of the HLL object is not valid, the integer
1023 * pointed by 'invalid' is set to non-zero, otherwise it is left untouched.
1024 *
1025 * hllCount() supports a special internal-only encoding of HLL_RAW, that
1026 * is, hdr->registers will point to an uint8_t array of HLL_REGISTERS element.
1027 * This is useful in order to speedup PFCOUNT when called against multiple
1028 * keys (no need to work with 6-bit integers encoding). */
1029uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
1030 double m = HLL_REGISTERS;
1031 double E;
1032 int j;
1033 int reghisto[HLL_Q+2] = {0};
1034
1035 /* Compute register histogram */
1036 if (hdr->encoding == HLL_DENSE) {
1037 hllDenseRegHisto(hdr->registers,reghisto);
1038 } else if (hdr->encoding == HLL_SPARSE) {
1039 hllSparseRegHisto(hdr->registers,
1040 sdslen((sds)hdr)-HLL_HDR_SIZE,invalid,reghisto);
1041 } else if (hdr->encoding == HLL_RAW) {
1042 hllRawRegHisto(hdr->registers,reghisto);
1043 } else {
1044 *invalid = 1;
1045 return 0;
1046 //serverPanic("Unknown HyperLogLog encoding in hllCount()");
1047 }
1048
1049 /* Estimate cardinality form register histogram. See:
1050 * "New cardinality estimation algorithms for HyperLogLog sketches"
1051 * Otmar Ertl, arXiv:1702.01284 */
1052 double z = m * hllTau((m-reghisto[HLL_Q+1])/(double)m);
1053 for (j = HLL_Q; j >= 1; --j) {
1054 z += reghisto[j];
1055 z *= 0.5;
1056 }
1057 z += m * hllSigma(reghisto[0]/(double)m);
1058 E = llroundl(HLL_ALPHA_INF*m*m/z);
1059
1060 return (uint64_t) E;
1061}
1062
1063/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
1064int hll_add(robj *o, unsigned char *ele, size_t elesize) {
1065 struct hllhdr *hdr = (struct hllhdr *) o->ptr;
1066 switch(hdr->encoding) {
1067 case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
1068 case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);
1069 default: return -1; /* Invalid representation. */
1070 }
1071}
1072
1073/* Merge by computing MAX(registers[i],hll[i]) the HyperLogLog 'hll'
1074 * with an array of uint8_t HLL_REGISTERS registers pointed by 'max'.
1075 *
1076 * The hll object must be already validated via isHLLObjectOrReply()
1077 * or in some other way.
1078 *
1079 * If the HyperLogLog is sparse and is found to be invalid, C_ERR
1080 * is returned, otherwise the function always succeeds. */
1081int hllMerge(uint8_t *max, robj *hll) {
1082 struct hllhdr *hdr = (struct hllhdr *) hll->ptr;
1083 int i;
1084
1085 if (hdr->encoding == HLL_DENSE) {
1086 uint8_t val;
1087
1088 for (i = 0; i < HLL_REGISTERS; i++) {
1089 HLL_DENSE_GET_REGISTER(val,hdr->registers,i);
1090 if (val > max[i]) max[i] = val;
1091 }
1092 } else {
1093 uint8_t *p = (uint8_t *) hll->ptr, *end = p + sdslen((sds) hll->ptr);
1094 long runlen, regval;
1095
1096 p += HLL_HDR_SIZE;
1097 i = 0;
1098 while(p < end) {
1099 if (HLL_SPARSE_IS_ZERO(p)) {
1100 runlen = HLL_SPARSE_ZERO_LEN(p);
1101 i += runlen;
1102 p++;
1103 } else if (HLL_SPARSE_IS_XZERO(p)) {
1104 runlen = HLL_SPARSE_XZERO_LEN(p);
1105 i += runlen;
1106 p += 2;
1107 } else {
1108 runlen = HLL_SPARSE_VAL_LEN(p);
1109 regval = HLL_SPARSE_VAL_VALUE(p);
1110 while(runlen--) {
1111 if (regval > max[i]) max[i] = regval;
1112 i++;
1113 }
1114 p++;
1115 }
1116 }
1117 if (i != HLL_REGISTERS) return C_ERR;
1118 }
1119 return C_OK;
1120}
1121
1122/* ========================== robj creation ========================== */
1123robj *createObject(void *ptr) {
1124 robj *result = (robj*) malloc(sizeof(robj));
1125 result->ptr = ptr;
1126 return result;
1127}
1128
1129void destroyObject(robj *obj) {
1130 free(obj);
1131}
1132
1133/* ========================== HyperLogLog commands ========================== */
1134
1135/* Create an HLL object. We always create the HLL using sparse encoding.
1136 * This will be upgraded to the dense representation as needed. */
1137robj *hll_create(void) {
1138 robj *o;
1139 struct hllhdr *hdr;
1140 sds s;
1141 uint8_t *p;
1142 int sparselen = HLL_HDR_SIZE +
1143 (((HLL_REGISTERS+(HLL_SPARSE_XZERO_MAX_LEN-1)) /
1144 HLL_SPARSE_XZERO_MAX_LEN)*2);
1145 int aux;
1146
1147 /* Populate the sparse representation with as many XZERO opcodes as
1148 * needed to represent all the registers. */
1149 aux = HLL_REGISTERS;
1150 s = sdsnewlen(NULL,sparselen);
1151 p = (uint8_t*)s + HLL_HDR_SIZE;
1152 while(aux) {
1153 int xzero = HLL_SPARSE_XZERO_MAX_LEN;
1154 if (xzero > aux) xzero = aux;
1155 HLL_SPARSE_XZERO_SET(p,xzero);
1156 p += 2;
1157 aux -= xzero;
1158 }
1159 assert((p-(uint8_t*)s) == sparselen);
1160
1161 /* Create the actual object. */
1162 o = createObject(s);
1163 hdr = (struct hllhdr *) o->ptr;
1164 memcpy(hdr->magic,"HYLL",4);
1165 hdr->encoding = HLL_SPARSE;
1166 return o;
1167}
1168
1169void hll_destroy(robj *obj) {
1170 if (!obj) {
1171 return;
1172 }
1173 sdsfree((sds) obj->ptr);
1174 destroyObject(obj);
1175}
1176
1177
1178
1179int hll_count(robj *o, size_t *result) {
1180 int invalid = 0;
1181 *result = hllCount((struct hllhdr*) o->ptr, &invalid);
1182 return invalid == 0 ? C_OK : C_ERR;
1183}
1184
1185robj *hll_merge(robj **hlls, size_t hll_count) {
1186 uint8_t max[HLL_REGISTERS];
1187 struct hllhdr *hdr;
1188 size_t j;
1189 /* Use dense representation as target? */
1190 int use_dense = 0;
1191
1192 /* Compute an HLL with M[i] = MAX(M[i]_j).
1193 * We store the maximum into the max array of registers. We'll write
1194 * it to the target variable later. */
1195 memset(max, 0, sizeof(max));
1196 for (j = 0; j < hll_count; j++) {
1197 /* Check type and size. */
1198 robj *o = hlls[j];
1199 if (o == NULL) continue; /* Assume empty HLL for non existing var. */
1200
1201 /* If at least one involved HLL is dense, use the dense representation
1202 * as target ASAP to save time and avoid the conversion step. */
1203 hdr = (struct hllhdr *) o->ptr;
1204 if (hdr->encoding == HLL_DENSE) use_dense = 1;
1205
1206 /* Merge with this HLL with our 'max' HHL by setting max[i]
1207 * to MAX(max[i],hll[i]). */
1208 if (hllMerge(max, o) == C_ERR) {
1209 return NULL;
1210 }
1211 }
1212
1213 /* Create the destination key's value. */
1214 robj *result = hll_create();
1215 if (!result) {
1216 return NULL;
1217 }
1218
1219 /* Convert the destination object to dense representation if at least
1220 * one of the inputs was dense. */
1221 if (use_dense && hllSparseToDense(result) == C_ERR) {
1222 hll_destroy(result);
1223 return NULL;
1224 }
1225
1226 /* Write the resulting HLL to the destination HLL registers and
1227 * invalidate the cached value. */
1228 for (j = 0; j < HLL_REGISTERS; j++) {
1229 if (max[j] == 0) continue;
1230 hdr = (struct hllhdr *) result->ptr;
1231 switch(hdr->encoding) {
1232 case HLL_DENSE: hllDenseSet(hdr->registers,j,max[j]); break;
1233 case HLL_SPARSE: hllSparseSet(result,j,max[j]); break;
1234 }
1235 }
1236 return result;
1237}
1238