3 ms·

Aside: I'm admittedly grumpy about the commit history, which is filled with entries such as "Add files via upload" and "Update README.md". That, together with

by vitus 6y ago

Aside: I'm admittedly grumpy about the commit history, which is filled with entries such as "Add files via upload" and "Update README.md". That, together with the lack of documentation, makes it much more difficult to figure out what's special about this implementation.

vitus 6y ago
https://github.com/redis/redis/blob/unstable/src/hyperloglog.c 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).
- vitus 6y ago
  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 https://pastebin.com/T520dzWV It would be nice to have comments pointing out specifically what changes are important / why they were made.
rurban 6y ago
Yeah, WangYi only updates via some git gui. Same for his hash and prng. But those two set already the new standards, and the hll should be in the same league. Top of the class.

by vitus 6y ago

vitus 6y ago

https://github.com/redis/redis/blob/unstable/src/hyperloglog.c 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).

vitus 6y ago
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 https://pastebin.com/T520dzWV It would be nice to have comments pointing out specifically what changes are important / why they were made.

rurban 6y ago

Yeah, WangYi only updates via some git gui. Same for his hash and prng. But those two set already the new standards, and the hll should be in the same league. Top of the class.