Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: HyperLogLog in Zig

github.com

Post reply on HN
Print view View original

1–10 of 38 posts

Re: Show HN: HyperLogLog in Zig

#5

Post by zX41ZdbW »

extasia wrote: post #2

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

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/

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.

Re: Show HN: HyperLogLog in Zig

#6

Post by henry_viii »

eatonphil wrote: post #4

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

I'm also very curious to know this. HyperLogLog is written in Go:

https://github.com/axiomhq/hyperloglog

I would expect V to be a more natural choice for a port than Zig.

Re: Show HN: HyperLogLog in Zig

#7

Post by seiflotfy »

henry_viii wrote: post #6
eatonphil wrote: post #4

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

I'm also very curious to know this. HyperLogLog is written in Go: https://github.com/axiomhq/hyperloglog I would expect V to be a more natural choice for a port than Zig.

Author here, will publish my vlang take on it in the next couple of days.

Re: Show HN: HyperLogLog in Zig

#8

Post by kristoff_it »

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
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

Re: Show HN: HyperLogLog in Zig

#9

Post by henry_viii »

seiflotfy wrote: post #7
henry_viii wrote: post #6

Earlier quoted context omitted.

I'm also very curious to know this. HyperLogLog is written in Go: https://github.com/axiomhq/hyperloglog I would expect V to be a more natural choice for a port than Zig.

Author here, will publish my vlang take on it in the next couple of days.

Looking forward to it :).

It seems the V port should be pretty straightforward (the repo is 880 LOC and doesn't have any dependencies).

Post reply on HN