6 ms·

Show HN: HyperLogLog in Zig

154 points by seiflotfy 4y ago

extasia 4y ago
Looks cool. What are some applications of a cardinality estimator?
- jedisct1 4y ago
  Rate-limiting is one.
  - anacrolix 4y ago
    Do you have an example?
  - avinassh 4y ago
    How does one use Hyperloglog for ratelimiting?
- zX41ZdbW 4y ago
  Memory bound alternative for the COUNT(DISTINCT ...) aggregate function in SQL. ClickHouse[1] has a few functions for that, with different tradeoffs in memory usage, precision, and performance: - uniqExact - the same as COUNT(DISTINCT ...) - the exact version, using a hash table; - uniqCombined - a combination of a linear array of small size in memory arena, a hash table, and a HyperLogLog - this data structure is similar to HyperLogLog++; the log2 of the number of cells is controllable by the user; - uniq - a cardinality estimator based on adaptive sampling by hash, lower quality to memory usage compared to HyperLogLog, but beats it in CPU efficiency; - uniqTheta - uses the Theta sketch algorithm, whatever it means; - uniqUpTo(N) - my favorite, uses a linear array to give the precise answer up to N, and always answers N + 1 when the number of distinct elements is larger than N; - groupBitmap - an exact calculation using Roaring Bitmaps, makes sense for dense integer sets; [1] https://github.com/ClickHouse/ClickHouse/ https://github.com/ClickHouse/ClickHouse/ What is often forgotten in designing a data structure for a cardinality estimator - is that it should work well not only for a few large states but also for a large number of small sets. For example, in a query like follows: SELECT URL, COUNT(DISTINCT UserID) FROM pageviews GROUP BY URL You should expect that there are a large number of URLs, but most of them will get just 1..2 unique UserIDs. Obviously, it's not practical to allocate even a 4 KB HyperLogLog for every resulting record. That's how complex combined data structures are justified. They should start with ~16..64 bytes of automatic memory in arena or stack, and only then upgrade to a HyperLogLog.
- refset 4y ago
  Various aspects of query optimization like join planning and predicate selectivity estimation, e.g. as discussed in https://arxiv.org/abs/2010.00728 https://arxiv.org/abs/2010.00728
- cnlwsu 4y ago
  For LSM trees to estimate effectiveness of a compaction
- taepper 4y ago
  hashtable sizing for aggregation
eatonphil 4y ago
Awesome! Does Axiom use Zig? Most of your projects seem to be in Go. Why did you choose to do this in Zig?
- henry_viii 4y ago
  I'm also very curious to know this. HyperLogLog is written in Go: https://github.com/axiomhq/hyperloglog https://github.com/axiomhq/hyperloglog I would expect V to be a more natural choice for a port than Zig.
  - seiflotfy 4y ago
    Author here, will publish my vlang take on it in the next couple of days.
    - henry_viii 4y ago
      Looking forward to it :). It seems the V port should be pretty straightforward (the repo is 880 LOC and doesn't have any dependencies).
  - shilldetector 4y ago
    As a notice to others reading this user's comments, they are a recently made account that seems to exist mostly to post about V and post negatively about Zig. Extremely suspect given the history of poor behavior from the V project.
    - henry_viii 4y ago
      You made this account just to insinuate I'm a shill? Not cool. I work professionally with Go and I follow news about V, yes. Also I'm interested in discussions involving Zig and V because even though there is an overlap of the design goals of the languages (e.g. zero-cost interoperability with C, high performance), there aren't many comparisons between them online. My advice is listen to the criticism of Zig to improve the language instead of making throwaway accounts to accuse people.
kristoff_it 4y ago
One change to make this library more idiomatic would be to make HyperLogLog avoid forcing heap allocation on the user. So from this (simplified code): pub fn HyperLogLog(comptime p: u8) type { return struct { dense: []u6, const Self = @This(); pub fn init(allocator: Allocator) !Self { return Self{ .dense = try allocator.alloc(u6, 0), }; } } } To this: pub fn HyperLogLog(comptime p: u8) type { return struct { dense: [1<<p]u6; const Self = @This(); pub fn init() Self { var s = Self{}; for (s.dense) |*x| x.* = 0; return s; } } } The advantage to this API is that the user can choose where to place the HLL (stack, heap, global memory). Also note how the new init can't fail anymore. That said, in the code that I've conveniently omitted there's one big complication: when the HLL has only few items in it, it doesn't use the dense representation and instead uses a `std.AutoHashMap` to keep counts. Unfortunately `std.AutoHashMap` is not a type that can be reasonably disentangled from allocation. I was about to drop my idea of commenting when I realized that a very neat solution would be to also provide the user with the choice (and admittedly extra responsibility) of when to switch from a hash map to a proper HLL. pub fn init(start: std.AutoHashMap) Self { var s = Self{}; for (s.dense) |*s| s.* = 0; self.addFromHashMap(start); return s; } There you go, allocation-free HyperLogLog :^) I've also come up with my own funky interface when I implemented Cuckoo Filters in Zig, for those who are interested: https://github.com/kristoff-it/zig-cuckoofilter https://github.com/kristoff-it/zig-cuckoofilter
- kristoff_it 4y ago
  Or alternatively one could make good use of the existing buffer and use that to encode the sparse representation, like Antirez did in Redis: https://github.com/redis/redis/blob/unstable/src/hyperloglog.c#L100-L180 https://github.com/redis/redis/blob/unstable/src/hyperloglog...
- seiflotfy 4y ago
  This is awesome... question though: ```pub fn HyperLogLog(comptime p: u8) type { return struct { dense: [1<<p]u6; const Self = @This(); pub fn init() Self { var s = Self{}; for (s.dense) |*x| x.* = 0; return s; } } }``` doesn't this allocate 1<<p upfront though. If yes then the HLL of size 16384 bytes upfront which kinda beats the purpose of having a sparse representation no?
VWWHFSfQ 4y ago
What is the point of Zig? I mean, this looks approximately like code I would write in about a dozen other languages. So, what is this?
- whimsicalism 4y ago
  It's C level speeds.
kjgkjhfkjf 4y ago
Is it possible to use a single fn to replace the beta4..beta18 fns[0], so that the polynomial expressions are generated at comptime instead of being hand-written? [0] https://github.com/axiomhq/zig-hyperloglog/blob/main/src/beta.zig https://github.com/axiomhq/zig-hyperloglog/blob/main/src/bet...
- nonsequitur 4y ago
  Yes: https://zigbin.io/771ac5 https://zigbin.io/771ac5
  - kjgkjhfkjf 4y ago
    Nice!

154 points by seiflotfy 4y ago

extasia 4y ago

Looks cool. What are some applications of a cardinality estimator?

jedisct1 4y ago
Rate-limiting is one.
- anacrolix 4y ago
  Do you have an example?
- avinassh 4y ago
  How does one use Hyperloglog for ratelimiting?
zX41ZdbW 4y ago
Memory bound alternative for the COUNT(DISTINCT ...) aggregate function in SQL. ClickHouse[1] has a few functions for that, with different tradeoffs in memory usage, precision, and performance: - uniqExact - the same as COUNT(DISTINCT ...) - the exact version, using a hash table; - uniqCombined - a combination of a linear array of small size in memory arena, a hash table, and a HyperLogLog - this data structure is similar to HyperLogLog++; the log2 of the number of cells is controllable by the user; - uniq - a cardinality estimator based on adaptive sampling by hash, lower quality to memory usage compared to HyperLogLog, but beats it in CPU efficiency; - uniqTheta - uses the Theta sketch algorithm, whatever it means; - uniqUpTo(N) - my favorite, uses a linear array to give the precise answer up to N, and always answers N + 1 when the number of distinct elements is larger than N; - groupBitmap - an exact calculation using Roaring Bitmaps, makes sense for dense integer sets; [1] https://github.com/ClickHouse/ClickHouse/ https://github.com/ClickHouse/ClickHouse/ What is often forgotten in designing a data structure for a cardinality estimator - is that it should work well not only for a few large states but also for a large number of small sets. For example, in a query like follows: SELECT URL, COUNT(DISTINCT UserID) FROM pageviews GROUP BY URL You should expect that there are a large number of URLs, but most of them will get just 1..2 unique UserIDs. Obviously, it's not practical to allocate even a 4 KB HyperLogLog for every resulting record. That's how complex combined data structures are justified. They should start with ~16..64 bytes of automatic memory in arena or stack, and only then upgrade to a HyperLogLog.
refset 4y ago
Various aspects of query optimization like join planning and predicate selectivity estimation, e.g. as discussed in https://arxiv.org/abs/2010.00728 https://arxiv.org/abs/2010.00728
cnlwsu 4y ago
For LSM trees to estimate effectiveness of a compaction
taepper 4y ago
hashtable sizing for aggregation

eatonphil 4y ago

Awesome! Does Axiom use Zig? Most of your projects seem to be in Go. Why did you choose to do this in Zig?

henry_viii 4y ago
I'm also very curious to know this. HyperLogLog is written in Go: https://github.com/axiomhq/hyperloglog https://github.com/axiomhq/hyperloglog I would expect V to be a more natural choice for a port than Zig.
- seiflotfy 4y ago
  Author here, will publish my vlang take on it in the next couple of days.
  - henry_viii 4y ago
    Looking forward to it :). It seems the V port should be pretty straightforward (the repo is 880 LOC and doesn't have any dependencies).
- shilldetector 4y ago
  As a notice to others reading this user's comments, they are a recently made account that seems to exist mostly to post about V and post negatively about Zig. Extremely suspect given the history of poor behavior from the V project.
  - henry_viii 4y ago
    You made this account just to insinuate I'm a shill? Not cool. I work professionally with Go and I follow news about V, yes. Also I'm interested in discussions involving Zig and V because even though there is an overlap of the design goals of the languages (e.g. zero-cost interoperability with C, high performance), there aren't many comparisons between them online. My advice is listen to the criticism of Zig to improve the language instead of making throwaway accounts to accuse people.

kristoff_it 4y ago

One change to make this library more idiomatic would be to make HyperLogLog avoid forcing heap allocation on the user. So from this (simplified code): pub fn HyperLogLog(comptime p: u8) type { return struct { dense: []u6, const Self = @This(); pub fn init(allocator: Allocator) !Self { return Self{ .dense = try allocator.alloc(u6, 0), }; } } } To this: pub fn HyperLogLog(comptime p: u8) type { return struct { dense: [1<<p]u6; const Self = @This(); pub fn init() Self { var s = Self{}; for (s.dense) |*x| x.* = 0; return s; } } } The advantage to this API is that the user can choose where to place the HLL (stack, heap, global memory). Also note how the new init can't fail anymore. That said, in the code that I've conveniently omitted there's one big complication: when the HLL has only few items in it, it doesn't use the dense representation and instead uses a `std.AutoHashMap` to keep counts. Unfortunately `std.AutoHashMap` is not a type that can be reasonably disentangled from allocation. I was about to drop my idea of commenting when I realized that a very neat solution would be to also provide the user with the choice (and admittedly extra responsibility) of when to switch from a hash map to a proper HLL. pub fn init(start: std.AutoHashMap) Self { var s = Self{}; for (s.dense) |*s| s.* = 0; self.addFromHashMap(start); return s; } There you go, allocation-free HyperLogLog :^) I've also come up with my own funky interface when I implemented Cuckoo Filters in Zig, for those who are interested: https://github.com/kristoff-it/zig-cuckoofilter https://github.com/kristoff-it/zig-cuckoofilter

kristoff_it 4y ago
Or alternatively one could make good use of the existing buffer and use that to encode the sparse representation, like Antirez did in Redis: https://github.com/redis/redis/blob/unstable/src/hyperloglog.c#L100-L180 https://github.com/redis/redis/blob/unstable/src/hyperloglog...
seiflotfy 4y ago
This is awesome... question though: ```pub fn HyperLogLog(comptime p: u8) type { return struct { dense: [1<<p]u6; const Self = @This(); pub fn init() Self { var s = Self{}; for (s.dense) |*x| x.* = 0; return s; } } }``` doesn't this allocate 1<<p upfront though. If yes then the HLL of size 16384 bytes upfront which kinda beats the purpose of having a sparse representation no?

VWWHFSfQ 4y ago

What is the point of Zig? I mean, this looks approximately like code I would write in about a dozen other languages. So, what is this?

whimsicalism 4y ago
It's C level speeds.

kjgkjhfkjf 4y ago

Is it possible to use a single fn to replace the beta4..beta18 fns[0], so that the polynomial expressions are generated at comptime instead of being hand-written? [0] https://github.com/axiomhq/zig-hyperloglog/blob/main/src/beta.zig https://github.com/axiomhq/zig-hyperloglog/blob/main/src/bet...

nonsequitur 4y ago
Yes: https://zigbin.io/771ac5 https://zigbin.io/771ac5
- kjgkjhfkjf 4y ago
  Nice!