Re:WyHLL: The most accurate 3-bits HyperLogLog
by vitus on Sunday March 14, 2021 @01:45PM
(#26457153)
https://github.com/redis/redis/blob/unstable/src/hyperloglog... seems to be the starting point, given a number of identical comments (complete with typos, e.g. "Estimate cardinality form register histogram"), function names, macros. Copyright isn't preserved, which is troubling in itself. There's a brief mention of Redis's HLL implementation in the README, which is a hint re: the code's origins.
The first divergence I see is in hllSparseToDense, although it seems more like a tweak to the input/output (passing in o->ptr instead of o, returning hdr instead of C_OK / C_ERR), than an algorithmic difference.
Line 550 contains a looser check:
if (span == 0) return -1;
omitting the check that p >= end.And... the only meaningful algorithmic change I found is in hllAdd, wherein we invalidate the cache if hllDenseAdd() returns 1.
There might be something else, but a lot of the details look to be standard (e.g. impl of murmurhash64a).
Re:WyHLL: The most accurate 3-bits HyperLogLog
by vitus on Monday March 15, 2021 @05:49PM
(#26469626)
Anyways, if anyone else wants to look at it: I've stripped the comments, clang-formatted both implementations, and uploaded the diff (sans newline differences) to pastebin.
It would be nice to have comments pointing out specifically what changes are important / why they were made.
That, together with the lack of documentation, makes it much more difficult to figure out what's special about this implementation.