Talan.LinearCounter (talan v1.0.0)

Linear probabilistic counter implementation with safe concurrent access, powered by the :atomics module for cardinality estimation.

Cardinality is the count of unique elements.

For more information about linear probabilistic counting: linear probabilistic counting

Summary

Functions

cardinality(linear_counter)

Returns the estimated cardinality for the given %Talan.LinearCounter{} struct.

clear(counter)

Clears every bit in counter and returns the same counter.

new(expected_cardinality, options \\ [])

Returns a new %Talan.LinearCounter{} struct.

put(linear_counter, term)

Hashes term and sets a bit to record that the term has been seen.

Types

option()

@type option() :: {:hash_function, Talan.hash_function()}

options()

@type options() :: [option()]

t()

@type t() :: %Talan.LinearCounter{
  atomics_ref: reference(),
  filter_length: pos_integer(),
  hash_function: Talan.hash_function()
}

Functions

cardinality(linear_counter)

@spec cardinality(t()) :: non_neg_integer()

Returns the estimated cardinality for the given %Talan.LinearCounter{} struct.

A saturated counter has no unset bits, so its cardinality cannot be estimated reliably; in that case this function returns the counter's filter length.

Examples

iex> c = Talan.LinearCounter.new(10_000)
iex> c |> Talan.LinearCounter.put(["you", :can, Hash, {"any", "elixir", "term"}])
iex> c |> Talan.LinearCounter.put(["you", :can, Hash, {"any", "elixir", "term"}])
iex> c |> Talan.LinearCounter.cardinality()
1
iex> c |> Talan.LinearCounter.put("more")
iex> c |> Talan.LinearCounter.cardinality()
2

clear(counter)

@spec clear(t()) :: t()

Clears every bit in counter and returns the same counter.

The counter is reset in place without reallocating its atomics reference. Clearing individual atomic words is safe during concurrent access, but the counter is not cleared as one atomic operation. Concurrent cardinality reads may observe a partially cleared counter, and concurrent writes may be cleared or remain set depending on their timing.

Examples

iex> counter = Talan.LinearCounter.new(1000)
iex> Talan.LinearCounter.put(counter, "Barna")
iex> Talan.LinearCounter.clear(counter) == counter
true
iex> Talan.LinearCounter.cardinality(counter)
0

new(expected_cardinality, options \\ [])

@spec new(pos_integer(), options()) :: t()

Returns a new %Talan.LinearCounter{} struct.

expected_cardinality is the maximum number of unique items the counter will handle with an approximately 1% error rate.

Raises ArgumentError if expected_cardinality or any option is invalid.

Options

:hash_function - a function that accepts a term and returns a non-negative integer, defaults to Murmur.hash_x64_128/1

Examples

iex> c = Talan.LinearCounter.new(10_000)
iex> c |> Talan.LinearCounter.put(["you", :can, Hash, {"any", "elixir", "term"}])
iex> c |> Talan.LinearCounter.put("more")
iex> c |> Talan.LinearCounter.put("another")
iex> c |> Talan.LinearCounter.cardinality()
3

put(linear_counter, term)

@spec put(t(), any()) :: :ok

Hashes term and sets a bit to record that the term has been seen.

Doesn't store the term so it's space-efficient. Uses :atomics so it's mutable and highly concurrent.

Returns :ok.

Examples

iex> c = Talan.LinearCounter.new(10_000)
iex> c |> Talan.LinearCounter.put(["you", :can, Hash, {"any", "elixir", "term"}])
:ok