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.
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:
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).