TrieHard

A fast, memory-efficient trie (prefix tree) for Elixir with autocomplete, implemented as a Rust NIF via Rustler.

Features

Fast: sub-microsecond lookups, prefix checks and 10-result autocompletes
Compact: path-compressed (radix) layout by default, ~50 bytes per key in the benchmark below
Deterministic: auto_complete returns keys in lexicographic (codepoint) order
Unicode: keys are UTF-8 strings, including emoji and combining characters
Any value: store any Erlang term
Scheduler-friendly: concurrent readers; long or contended operations move to dirty schedulers

Performance

Measured with bench/trie_bench.exs (release build) on an Apple M4 Max, macOS, Elixir 1.20.0 / OTP 29.1.1, against a trie of 100,000 "word_<n>_suffix" keys:

Operation	`:radix` (default)	`:sorted`
`fetch/2` (hit)	0.17 µs	0.14 µs
`prefix?/2`	0.13 µs	0.10 µs
`delete/2` + `insert/3`	0.33 µs	0.50 µs
`auto_complete/3`, 10 results	0.61 µs	0.95 µs
`auto_complete/3`, 100 results	2.6 µs	6.0 µs
`count_prefix/2`, 111 matches	0.26 µs	0.99 µs
`count_prefix/2`, 11,112 matches	27 µs	142 µs
`insert/3`, per key (1,000 into a new trie)	0.16 µs	0.43 µs
`insert_many/2`, per key	0.16 µs	0.41 µs
`add_word_list/2`, per key	0.10 µs	0.38 µs

Memory per key (RSS delta for 200,000 keys, fresh VM per layout):

Keys	`:radix`	`:sorted`
`"word_<n>_suffix"`	47–53 B	592–618 B
`"https://example.com/users/<n>/profile/settings"`	37–54 B	1,622–1,639 B

Ranges are the spread over repeated runs (small RSS deltas are noisy).

Run it yourself:

MIX_ENV=bench TRIE_HARD_BUILD=true mix run bench/trie_bench.exs

Installation

def deps do
  [
    {:trie_hard, "~> 0.3.0"}
  ]
end

Precompiled NIFs are downloaded for these targets: aarch64-apple-darwin, x86_64-apple-darwin, aarch64-unknown-linux-gnu, x86_64-unknown-linux-gnu, aarch64-unknown-linux-musl, x86_64-unknown-linux-musl, x86_64-pc-windows-gnu (NIF versions 2.16 and 2.17). On any other target, set TRIE_HARD_BUILD=true to compile the NIF from the bundled sources; this needs Rust 1.91 or newer and the optional {:rustler, "~> 0.37"} dependency in your project.

Documentation: https://hexdocs.pm/trie_hard.

Requirements

Elixir 1.18+ (CI covers OTP 26 through 29)
Building from source only: stable Rust ≥ 1.91 (the repository pins 1.97.1 in rust-toolchain.toml)

Quick Start

trie = TrieHard.new()

:ok = TrieHard.insert(trie, "cat", "feline")
:ok = TrieHard.insert_many(trie, [{"car", %{wheels: 4}}, {"card", {:payment, :plastic}}])

{:ok, "feline"} = TrieHard.fetch(trie, "cat")
{:error, :not_found} = TrieHard.fetch(trie, "dog")
"feline" = TrieHard.get(trie, "cat")
nil = TrieHard.get(trie, "dog")
:none = TrieHard.get(trie, "dog", :none)

# Lexicographic order; the limit keeps the first matches in that order
["car", "card", "cat"] = TrieHard.auto_complete(trie, "ca", 10)
["car", "card"] = TrieHard.auto_complete(trie, "ca", 2)

true = TrieHard.prefix?(trie, "ca")
false = TrieHard.prefix?(trie, "xyz")

3 = TrieHard.count_prefix(trie, "ca")

:ok = TrieHard.delete(trie, "cat")
{:error, :not_found} = TrieHard.delete(trie, "cat")

# Each word is stored with itself as the value
:ok = TrieHard.add_word_list(trie, ["apple", "application", "apply"])
"apple" = TrieHard.get(trie, "apple")

# One node per key byte instead of path compression; same results for every operation
sorted = TrieHard.new(layout: :sorted)
:ok = TrieHard.insert(sorted, "card", 1)

API

Function	Returns
`new/1`	an opaque trie (`TrieHard.t()`); option `layout: :radix` (default) or `:sorted`
`insert/3`	`:ok`
`insert_many/2`	`:ok` — inserts `{key, value}` pairs from any enumerable
`fetch/2`	`{:ok, value}` or `{:error, :not_found}`
`get/3`	the value, or `default` (`nil`) when missing — like `Map.get/3`
`delete/2`	`:ok`, or `{:error, :not_found}` when the key was absent
`prefix?/2`	`boolean` — whether any key starts with the prefix
`auto_complete/3`	up to `max_results` (default 10) keys, in lexicographic order
`count_prefix/2`	exact number of keys with the prefix
`add_word_list/2`	`:ok` — inserts each word with itself as the value

Keys must be UTF-8 binaries. Single-key functions raise FunctionClauseError for a non-binary key; insert_many/2 and add_word_list/2 raise ArgumentError for any invalid element; invalid UTF-8 always raises ArgumentError.

Concurrency

A trie can be shared between processes. Reads run concurrently; writes are exclusive. Every operation first runs on the calling scheduler without blocking:

if the key is longer than 4 KiB, the value larger than 64 KiB, or the operation would visit more than 10,000 nodes or copy more than 64 KiB of key bytes (results, or a :radix edge split/merge), it is retried on a dirty CPU scheduler;
if the lock is taken (by a writer, or by anyone for writes), the calling process yields and retries, so waiting doesn't occupy the dirty schedulers a bulk writer needs. Reads keep retrying with 1 ms sleeps for about 50 ms; writes stop after a few yields. Either then waits on a dirty scheduler.

Normal schedulers are never blocked.

add_word_list/2 and insert_many/2 always run on a dirty scheduler and send their input in chunks of at most 1,000 entries or 1 MiB, so readers interleave with large bulk loads. They are not atomic: an invalid element raises ArgumentError; earlier chunks remain inserted, while entries in the invalid element's chunk (including those before it) are not inserted.

Bound key lengths for untrusted input: one huge key makes its own write long.

Memory

A trie lives in native memory and is freed when its last reference is garbage collected, on the scheduler thread that runs that collection. Freeing a trie with millions of keys takes correspondingly long on that thread.

Development

mix deps.get
TRIE_HARD_BUILD=true mix test
cargo test --manifest-path native/trie_hard_native/Cargo.toml

bin/test.sh runs the same checks as CI (formatting, tests, clippy, cargo test). The Rust toolchain is pinned in rust-toolchain.toml; rustup installs it automatically.

Releasing

Push a version tag; GitHub Actions does the rest:

git tag v0.3.0 && git push origin v0.3.0

The Precomp NIFs workflow builds and attests the NIFs for every target, publishes them as a GitHub release, commits the checksum file and the version bump (mix.exs, Cargo.toml, Cargo.lock) to master, and checks that the package compiles with the downloaded NIF. The tag sets the version. GitHub Actions must be allowed to push to master.

Publishing to Hex:

With a HEX_API_KEY repository secret, the workflow publishes the tagged source itself.

Without it, publish from your machine once the workflow is green, using your Hex login (mix hex.user auth once):

git switch master && git pull   # picks up the "Release v0.3.0: checksum file and version" commit
unset TRIE_HARD_BUILD           # use the precompiled NIFs, checked against the new checksums
mix hex.publish

Architecture

Elixir (lib/trie_hard.ex): public API; encodes values with :erlang.term_to_binary/1 and decodes them with :erlang.binary_to_term/2 (:safe), so large terms are handled by yielding BIFs instead of inside the NIF.
NIF (native/trie_hard_native/src/lib.rs): a RwLock-protected trie in a Rustler resource; fast/dirty NIF pairs as described under Concurrency.
Tries (native/trie_hard_native/src/): radix.rs (path-compressed edges) and sorted.rs (one node per byte, sorted child arrays), dispatched by store.rs. All traversals and frees are iterative, so very long keys cannot overflow the stack.

Contributing

Fork the repository
Create your feature branch
Add tests for new functionality
Ensure bin/test.sh passes
Submit a pull request

License

Apache-2.0