ultra_log_log is an Elixir implementation of UltraLogLog (Ertl, VLDB 2024), a probabilistic data structure for approximate distinct counting — a more space-efficient successor to HyperLogLog. Same constant memory, constant-time inserts, and mergeable-as-a-CRDT property; 24–28% less memory at the same accuracy.
0.2 adds a lock-free concurrent insert path. UltraLogLog.Concurrent is backed by :atomics with a CAS loop — no GenServer, no lock, safe to insert into from any process or scheduler. snapshot/1 converts it back to the immutable form for estimation, merge, or serialization.
Example:
{:ok, c} = UltraLogLog.Concurrent.new(precision: 12)
1..1_000
|> Enum.chunk_every(100)
|> Enum.map(fn chunk ->
Task.async(fn -> Enum.each(chunk, &UltraLogLog.Concurrent.add(c, &1)) end)
end)
|> Task.await_many(:infinity)
sketch = UltraLogLog.Concurrent.snapshot(c)
{:ok, count} = UltraLogLog.cardinality(sketch)
Three estimators are available (FGRA, MLE, martingale), all
validated bit-for-bit against the Hash4j Java reference.
Hex: ultra_log_log | Hex
Docs: UltraLogLog v0.2.0 — Documentation
GitHub:
Full design notes, benchmarks, and validation methodology are in
the README and the docs. Feedback welcome.
