News for hackers. Stuff that matters.
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.

https://pastebin.com/T520dzWV

It would be nice to have comments pointing out specifically what changes are important / why they were made.