HyperLogLog in mojo

Community Showcase
1

:fire: HyperLogLog in Mojo – let’s make it fly

TL;DR
I’ve implemented HyperLogLog in Mojo to stress-test the language on bit-twiddly, SIMD-friendly code.
Repo → GitHub - axiomhq/mojo-hyperloglog
I need fresh eyes on perf hotspots, API feel, and a solid benchmark story.

What’s inside

  • HLL core in ~300 LOC Mojo (precision 4–16)
  • LogLog-Beta bias correction :white_check_mark:
  • Sparse ⇆ dense switch for tiny vs. huge sets
  • Merge-ready registers for sharded counts
  • Raw-byte serde
  • Unit tests + micro-bench skeleton (benchmark_hyperloglog.mojo)

Code stays vanilla for readabilit - plenty of low-hanging fruit for optimisation.

Why Mojo?

  • Python vibes, LLVM muscle
  • First-class SIMD intrinsics
  • Predictable memory layout (cache-friendly)
  • Compile-time generics incoming - perfect for prob-DS hacks

Where I need help

Area Current state What would be awesome
Hashing plain murmur3_64 Swap in XXH3/Metro64 - compare speed + collision
Bit maths naïve loops vector[i] = max(vector[i], r) via 128/256-bit SIMD
Benchmarks single-thread micro Repeatable harness vs. CPython, Go (axiomhq/hyperloglog), Rust
Docs tiny README Diagrams / blog-style walkthrough

(Bias correction is done - no estimator bikeshedding right now.)

How to run

# Needs Mojo SDK ≥ 0.7.0
git clone https://github.com/axiomhq/mojo-hyperloglog
cd mojo-hyperloglog
mojo run test_hyperloglog.mojo        # all green
mojo run benchmark_hyperloglog.mojo   # ops/s + error stats

Contributing

  • PRs / discussions for micro-opts, API tweaks, benchmark scripts (Go, Rust, C++… bring ’em).
  • Faster and clean? :100:
  • MIT licence.

Roadmap (up for debate)

  1. Vectorised add_hash (AVX-512 / Neon flag)
  2. Streaming memory-profiler hook
  3. Blog post: Mojo vs. Go HLL - war stories & numbers

Big thanks in advance - curious what the Mojo crew can squeeze out!

3 Likes
2

Good job!
Is there a reason for directly calling __setitem__ like:

self.registers.__setitem__(bucket, zeros)

rather than using syntax sugar:

self.registers[bucket] = zeros

Magic methods are not meant to be called directly; that’s why they’re ugly.

3

good call! changing it… or if you want you can create a PR :folded_hands:

4

Hey Seif,

nice idea, it’s actually first time that I heard of HyperLogLog (shame on me :grinning_face:) and it seems like a very interesting and cool data structure.

From the first glance I would suggest to convert p (the precision) into a type parameter. This way you can turn many run time vars into compile time aliases. e.g max_zeros, alpha‎ and multiple instances of m. The get_beta function should also get precision as comp time argument so you can add @parameter in front of the if/else cascade, so that the compiler will emit only the specialised computation and you will eliminate the branching completely. For the computation of the alpha in init method of HyperLogLog you would use the same trick. Similar trick can be applied in cardinality method. You can annotate the for i in range(m): with @parameter as m would be compile time known and this will inline the loop. Those are micro optimisations, so I am not sure how much benefit they will provide, but those are the things that are unique to Mojo.

I also see that you implemented murmur3_64 in the unit test. I would suggest to use the hash function shipped with standard library. The nightly default implementation uses AHash as hashing function which should be faster and provided better quality hash values.

You are also welcome to implement Murmur3_64 as a Hasher and compare it against AHasher. The hash function in stdlib allows swapping of the hashing algorithm.

I would also recommend to think about using the SIMD type in order to vectorise some computations. If it is ok with you I could also create a PR at some point.

1 Like
5

I’d love a PR. Thank you so much for the suggestions :smiley:

6

Hello, thanks that is awesome.
I too did not knew about this very useful HyperLogLog,
also learned about harmonic average on the way :+1: