News for hackers. Stuff that matters.
Re:Show HN: HyperLogLog in Zig by extasia on Monday January 09, 2023 @01:44PM (#34314249)
Looks cool. What are some applications of a cardinality estimator?
Re:Show HN: HyperLogLog in Zig by zX41ZdbW on Monday January 09, 2023 @02:05PM (#34314518)
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 by jedisct1 on Monday January 09, 2023 @01:52PM (#34314344)
Rate-limiting is one.
Re:Show HN: HyperLogLog in Zig by anacrolix on Monday January 09, 2023 @09:07PM (#34319426)
Do you have an example?
Re:Show HN: HyperLogLog in Zig by avinassh on Monday January 09, 2023 @11:51PM (#34320666)
How does one use Hyperloglog for ratelimiting?
Re:Show HN: HyperLogLog in Zig by refset on Monday January 09, 2023 @02:43PM (#34314971)
Various aspects of query optimization like join planning and predicate selectivity estimation, e.g. as discussed in https://arxiv.org/abs/2010.00728
Re:Show HN: HyperLogLog in Zig by cnlwsu on Monday January 09, 2023 @08:57PM (#34319347)
For LSM trees to estimate effectiveness of a compaction
Re:Show HN: HyperLogLog in Zig by taepper on Tuesday January 10, 2023 @02:24AM (#34321600)
hashtable sizing for aggregation
Re:Show HN: HyperLogLog in Zig by eatonphil on Monday January 09, 2023 @02:03PM (#34314496)
Awesome! Does Axiom use Zig? Most of your projects seem to be in Go. Why did you choose to do this in Zig?
Re:Show HN: HyperLogLog in Zig by henry_viii on Monday January 09, 2023 @02:12PM (#34314594)
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 by seiflotfy on Monday January 09, 2023 @02:19PM (#34314684)
Author here, will publish my vlang take on it in the next couple of days.
Re:Show HN: HyperLogLog in Zig by henry_viii on Monday January 09, 2023 @02:27PM (#34314786)
Looking forward to it :).

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

Re:Show HN: HyperLogLog in Zig by shilldetector on Monday January 09, 2023 @04:10PM (#34316113)
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.
Re:Show HN: HyperLogLog in Zig by henry_viii on Tuesday January 10, 2023 @05:09AM (#34322658)
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.

Re:Show HN: HyperLogLog in Zig by dang on Wednesday January 11, 2023 @12:35AM (#34335366)
I agree that the criticism is unfair because you've posted about other things as well. However, it's true that you've posted in the programming language flamewar style in the past; we're trying to avoid that here, so please don't do that in the future.

https://news.ycombinator.com/newsguidelines.html

Re:Show HN: HyperLogLog in Zig by henry_viii on Wednesday January 11, 2023 @03:17AM (#34336291)
Thank you, Dan.

I meant to ask my question in the spirit of HN (intellectual curiosity). I have found this community insightful when it comes to programming languages. Examples:

Vale

https://news.ycombinator.com/item?id=31786487

Lobster

https://news.ycombinator.com/item?id=19567160

I think this question will also be raised eventually since there have been other examples of Zig ports of Go projects:

https://news.ycombinator.com/item?id=31993429#31994394

I'm looking forward to OP's update. I believe it will be objective and insightful (surprisingly Google returns 0 results of "vlang vs. zig").

Re:Show HN: HyperLogLog in Zig by pverghese on Wednesday January 11, 2023 @04:49AM (#34336774)
Come on. Give it up. If there is something interesting in Vlang, post it as a new thread so people can judge it on its merits. Otherwise stop popping up on other language threads to just say why not vlang? There has been enough of these language wars. It just casts a bad light on vlang that this is the method that is needed to promote the language.
Re:Show HN: HyperLogLog in Zig by henry_viii on Wednesday January 11, 2023 @06:05AM (#34337176)
Your account mostly exists to defend Zig. You've also spread lies about V:

https://news.ycombinator.com/item?id=31995339

And Rust:

https://news.ycombinator.com/item?id=31999093

I'm afraid I won't be able to have a civil discussion with you.

I'm looking forward to OP's update. Concrete numbers I would like to see:

1) How long it took to port the project to each language

2) How long it took to build the ported projects

3) How fast did each port perform

Re:Show HN: HyperLogLog in Zig by pverghese on Thursday January 12, 2023 @01:19AM (#34349884)
I've written code which is part of vlang's codebase so I don't know why you are trying to claim that I've spread lies. The comment you cite was about V's memory management being a mess. Autofree does not work and can lead to double free and use after frees currently. So when and if it is able to work I'll change my opinion. Until then, you need to stop behaving like a victim and promote vlang in a better way.
Re:Show HN: HyperLogLog in Zig by henry_viii on Thursday January 12, 2023 @05:32AM (#34351617)
> Autofree does not work and can lead to double free and use after frees currently

Unless you can give an example, I'm going to have to say you're still spreading lies.

The issues with autofree were fixed in June 2022. From V's homepage (https://vlang.io/):

> (June 9, 2022) As of today, programs built with the V compiler no longer leak memory by default.

Your previous comment was from July 2022:

https://news.ycombinator.com/item?id=31995339

I don't think HN is the place for football tribalism. We're discussing tools. Please don't get so emotionally attached to a tool.

I mentioned a language with a Go-like syntax in a discussion about a port of a Go project. I haven't been critical of Zig anywhere in the thread.

Re:Show HN: HyperLogLog in Zig by dang on Thursday January 12, 2023 @10:58PM (#34363780)
You did exactly what I asked you to stop doing, just after I asked you! This is a way to get banned here. Please don't do this in the future. It would be best to just avoid this topic and focus on other things you find interesting. I'm not going to ban you right now, because from your more recent posts it looks like you've started to do that instead, which is good.
Re:Show HN: HyperLogLog in Zig by dang on Thursday January 12, 2023 @11:00PM (#34363787)
Please do not do programming language flamewar on HN. Even if someone else's comments are provocative, or you feel they are, reacting this way only makes things worse, and is just what we're trying to avoid here.

https://news.ycombinator.com/newsguidelines.html

Re:Show HN: HyperLogLog in Zig by dang on Wednesday January 11, 2023 @12:34AM (#34335361)
It's true that users here should avoid programming language flamewar drama (or any flamewar drama), but you shouldn't be attacking another user like this. Between that and the name of the account, I think we have to ban this one.

https://news.ycombinator.com/newsguidelines.html

Re:Show HN: HyperLogLog in Zig by kristoff_it on Monday January 09, 2023 @02:27PM (#34314781)
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) |*s| s.* = 0;
                return s;
            }
        }
    }
The advantage to this API is that the user can choose where to place the HLL (stack, heap, global memory).

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 by kristoff_it on Monday January 09, 2023 @03:34PM (#34315613)
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...

Re:Show HN: HyperLogLog in Zig by seiflotfy on Monday January 09, 2023 @03:50PM (#34315829)
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?
Re:Show HN: HyperLogLog in Zig by kristoff_it on Monday January 09, 2023 @04:00PM (#34315996)
> doesn't this allocate 1<<p upfront though

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

Re:Show HN: HyperLogLog in Zig by Alifatisk on Tuesday January 10, 2023 @12:51AM (#34321019)
Why is Zigs syntax so … foreign to me? What’s the hype behind it?
Re:Show HN: HyperLogLog in Zig by int_19h on Tuesday January 10, 2023 @01:53AM (#34321414)
Take a look at Rust and you'll see where a lot of it is coming from.
Re:Show HN: HyperLogLog in Zig by seiflotfy on Tuesday January 10, 2023 @07:00AM (#34323483)
Actually i found zig easier to read than rust… something that i found more appealing!
Re:Show HN: HyperLogLog in Zig by Alifatisk on Tuesday January 10, 2023 @09:18AM (#34325159)
I used to hate Rusts syntax, but a YT channel in the name of ”No boilerplate” made me see the beauty in it.
Re:Show HN: HyperLogLog in Zig by kristoff_it on Tuesday January 10, 2023 @11:51AM (#34327686)
You're looking at a piece of code that's doing a type of metaprogramming mostly unique to Zig. Additionally I'm using a for loop capture syntax that is not common in other languages (closest thing I can think of are Ruby blocks).

You're just looking at a piece of code that is understandable for a newcomer to not find familiar.

Re:Show HN: HyperLogLog in Zig by VWWHFSfQ on Monday January 09, 2023 @06:49PM (#34318231)
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?
Re:Show HN: HyperLogLog in Zig by whimsicalism on Monday January 09, 2023 @07:37PM (#34318681)
It's C level speeds.
Re:Show HN: HyperLogLog in Zig by kjgkjhfkjf on Monday January 09, 2023 @11:20PM (#34320455)
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/bet...

Re:Show HN: HyperLogLog in Zig by nonsequitur on Wednesday January 11, 2023 @02:41PM (#34343459)
Re:Show HN: HyperLogLog in Zig by kjgkjhfkjf on Monday January 16, 2023 @09:42PM (#34408552)
Nice!