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),
};
}
}
}
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;
}
}
}
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;
}
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/redis/redis/blob/unstable/src/hyperloglog...
You're just looking at a piece of code that is understandable for a newcomer to not find familiar.
const Self = @This();
pub fn init() Self {
var s = Self{};
for (s.dense) |*x| x.* = 0;
return s;
}
}
}```
Yes, it does. The idea (see the last code snipped in that post), is that the user delays the creation of the HLL until they are ready to switch to a dense representation. Before then, they just use a std.AutoHashMap directly.
Or, alternatively, the HLL could use the same buffer for both dense and sparse representation (see the Redis code).
https://github.com/axiomhq/hyperloglog
I would expect V to be a more natural choice for a port than Zig.
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;
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
[0] https://github.com/axiomhq/zig-hyperloglog/blob/main/src/bet...