Metadata-Version: 2.4
Name: trieset
Version: 0.1.0a1
Summary: A sorted byte-string set backed by a threaded trie: a faster drop-in than sortedcontainers.SortedSet for build + prefix-scan + serialized-flush workloads.
Author-email: Daniel Benjamim <dangstan.gbr@gmail.com>
License-Expression: MIT
Keywords: trie,sorted-set,sortedcontainers,prefix,byte-string,ordered-set
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Operating System :: POSIX :: Linux
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# trieset

A sorted **byte-string** set backed by a threaded trie. A *faster drop-in* than
[`sortedcontainers.SortedSet`](https://grantjenks.com/docs/sortedcontainers/) for
one specific, common workload: you **build** a set of byte strings and then do
**prefix scans / counts** and/or a **serialized sorted flush**.

It is **not** a "faster sorted set" in general. The wins and the costs are both
stated honestly below, measured per-element against `SortedSet` (the fair drop-in
test), not in a bulk microbenchmark.

> Status: **public alpha (0.1.0a1).** First release is an **sdist** -- `pip install
> trieset` compiles the C-extension from source (needs a C++17 compiler; standard
> on Linux dev machines). Prebuilt binary (manylinux) wheels are a planned
> follow-up. The benchmark numbers below are measured on a quiesced 16-core Linux
> box; re-measure on your hardware before relying on a specific ratio.

## When to use it (and when not)

`SortedSet` is the de-facto answer for an ordered, mutable set with fast
membership + ordered iteration in pure Python. **Use `trieset` instead only when**
your keys are byte strings and your workload is dominated by ANY of:

- **autocomplete** -- `startsWith` / prefix scans: `startsWith` existence is
  ~9-15x faster than `SortedSet` at every prefix width; NARROW prefix collect (a
  prefix matching few keys) is a few x faster too. (WIDE prefix *collect* -- where
  you materialize a large fraction of the set -- favors `SortedSet`; see the cost
  section.)
- **prefix counting** -- `prefix_count(p)` is `O(prefix-length)` (per-node subtree
  counts), so it beats `SortedSet`'s bisect at EVERY width (~16-25x measured).
- **building** the set (lots of inserts) -- the fastest builder of any
  PREFIX-CAPABLE structure here (a plain hash set builds faster, but answers no
  prefix query),
- **serialized sorted flush** (persist / send on the wire / feed a C consumer).

**Do NOT reach for it** when your hot path is point membership at scale, or
exploding all keys back into a Python list, or you are memory-constrained -- see
the costs below.

## Measured drop-in verdict

Per-element, quiesced box, best-of-5, ratio = trie / `SortedSet` (`<1` = trie
faster). These core ops are unaffected by the prefix internals:

| operation | N=1k | N=10k | N=100k | verdict |
|-----------|------|-------|--------|---------|
| `add` (per-element build) | 0.13x | 0.12x | 0.15x | **trie WINS ~7x, every N** |
| `flush()` serialized       | 0.04x | 0.13x | 0.25x | **trie WINS 4-25x, every N** |
| `x in t` membership HIT    | 0.67x | 0.99x | 1.53x | wins small, **wash-to-~1.5x at scale** |
| `x in t` membership MISS   | 0.45x | 0.59x | 1.08x | wins to ~10k, ~wash at 100k |
| `tolist()` (C loop)        | 1.87x | 2.43x | 3.04x | **SS wins** (storage floor) |
| `list(t)` (per-elem iter)  | 2.20x | 3.46x | 4.39x | **SS wins** (use `tolist()`) |

### Prefix operations, by prefix width

Prefix performance depends on how WIDE the prefix is (how many keys it matches),
so a single ratio hides the story. Measured per query, N=100k, quiesced box,
clustered keys (us/query; lower is faster; **bold** = winner of trie vs `SortedSet`):

| prefix width | ~matches/query | `prefix_count`: trie / SS | `startsWith`: trie / SS | `prefix` collect: trie / SS |
|---|---|---|---|---|
| wide (1 char) | ~3850 | **0.06** / 1.51  (trie ~25x) | **0.10** / 1.48  (trie ~15x) | 175 / **53**  (SS ~3.3x) |
| medium (3)    | ~144  | **0.08** / 1.85  (trie ~23x) | **0.13** / 1.60  (trie ~12x) | 7.2 / **5.1**  (SS ~1.4x) |
| narrow (6)    | ~1    | **0.11** / 1.79  (trie ~16x) | **0.17** / 1.58  (trie ~9x)  | **0.26** / 1.32  (trie ~5x) |

Reading it:

- **`prefix_count` wins at every width (~16-25x).** It is `O(prefix-length)` -- a
  descend-and-read of a per-node subtree count, not a walk over matches -- so it
  beats `SortedSet`'s `O(log n)` bisect-difference even on wide prefixes. (Earlier
  releases walked the matches and LOST on wide prefixes; that is fixed.)
- **`startsWith` / prefix existence wins at every width (~9-15x).** An
  `O(prefix-length)` descent vs a bisect + `startswith` compare, flat in the match
  count. This is the most robust prefix win.
- **`prefix` collect (materializing the matching keys) is split:** the trie wins
  NARROW (~5x -- few keys to build), but `SortedSet` wins WIDE (a contiguous slice
  of `PyBytes` it already holds, vs the trie allocating each key). If your prefixes
  routinely return a large fraction of the set, `SortedSet` collect is faster.

## What WINS (the drop-in claim)

- **build / `add`: ~5x faster** than `SortedSet` at every N (and the fastest
  builder of every PREFIX-CAPABLE structure benchmarked; a plain hash set builds
  ~5x faster than `trieset` but answers no prefix query) -- per-element insert
  beats `SortedSet`'s bisect + list-insert, with no relocation and no declared
  alphabet.
- **`startsWith` / prefix existence: ~9-15x faster** than `SortedSet`, every width.
- **`prefix_count`: ~16-25x faster** than `SortedSet`, every width (`O(prefix-len)`).
- **NARROW prefix collect** (autocomplete -- a prefix matching few keys): a few x
  faster than `SortedSet`, and 5-60x faster than every other Python trie.
- **serialized sorted flush (`flush`): 3-14x faster** -- one contiguous C pass vs
  per-element Python serialization.
- **prefix-walk (ancestors): `O(word-length)`.** `shortest_prefix(word)` /
  `longest_prefix(word)` / `prefixes(word)` return the stored keys that are
  PREFIXES OF `word` (the dual of `prefix()`) in a single descent -- the natural
  "is any stored key a prefix of X" / "shortest dictionary root of X" query.
  (Honest caveat: on the whole *replace-words* style problem a plain `set` still
  wins end-to-end because build cost dominates -- this primitive closes the gap
  versus other tries, not a new headline versus a hash set.)

## What does NOT win (stated up front)

- **Point membership (`x in t`)** is a **wash at small N and a wash-to-slight-loss
  at scale** (measured ~1.0-1.5x SortedSet at N=100k, depending on the query mix).
  `SortedSet`'s bisect is `O(log n)` over contiguous, cache-friendly arrays; the
  trie does `O(k)` pointer-chasing across arena-scattered nodes (a cache miss per
  level), so it does not WIN membership and a hash set beats both. **Do not pick
  `trieset` for a membership-heavy workload** -- but it is the fastest *trie* here.
- **WIDE prefix collect** (materializing a large fraction of the set) is **slower**
  than `SortedSet`'s contiguous slice -- see the by-width table. (Only the COUNT is
  width-independent; collecting the keys is not.)
- **Listing all keys** is **slower** -- the storage-model floor: `SortedSet`
  already holds the `PyBytes`, while the trie must `malloc` + `memcpy` a `bytes`
  per key. `tolist()` (one C loop) is ~2-3x slower; the per-element `list(t)` is
  ~2-4x slower. Use `tolist()` to materialize and `for k in t` to stream /
  early-exit; do not use `list(t)`.
- **Memory: modestly higher (~1.1-1.5x, measurement-sensitive).** TrieSet's
  structure is ~73 B/key (exact arena); `SortedSet` measures ~50-70 B/key by RSS
  (it stores the `PyBytes` plus index pointers), so a like-for-like build-peak RSS
  comparison is ~1.1x and an RSS-delta comparison ~1.4x (an older optimistic
  SortedSet estimate gave ~1.8x). Either way it uses more than `SortedSet`, and far
  more than `marisa-trie`'s succinct ~18 B/key loaded. (Was ~3-7x before the
  leaf-tagging + inline-key shrink; +4% back from the per-node subtree counts that
  make `prefix_count` `O(prefix-len)`.)

In one sentence: *the fastest structure here to BUILD a mutable byte-string
dictionary and do AUTOCOMPLETE on it (`startsWith` + `prefix_count` + narrow
prefix suggestions) and SERIALIZED FLUSH; WIDE prefix collect and point membership
favor `SortedSet`; ~2-4x slower to list all keys; modestly more memory (~1.1-1.5x).*

## Versus compiled tries (datrie, marisa-trie)

`SortedSet` is pure Python; the honest next question is how `trieset` sits among
*compiled* trie libraries. Measured (lowercase-ascii keys, quiesced; peers:
`datrie`, `marisa-trie`, `pygtrie`, `pyahocorasick`):

- **Build:** `trieset` is the fastest -- **~2.9x** faster than `pyahocorasick`,
  **~3.4x** faster than `marisa-trie`'s bulk build, **~18x** faster than `pygtrie`,
  and orders of magnitude faster than `datrie` (~80x even pre-sorted, hundreds of x
  in random order -- its double-array relocates on incremental insert).
- **Prefix COUNT + COLLECT:** `trieset` beats every compiled trie at **every width**
  -- it **counts** in `O(prefix-len)` without building Python objects (the peers
  must materialize and count: ~600-8000x slower on wide prefixes) and **collects**
  ~3-60x faster.
- **Prefix EXISTENCE (`startsWith`):** `trieset` does **not** lead here. `datrie`
  and `pyahocorasick` (a compiled Aho-Corasick automaton) answer `startsWith`
  ~1.5-2.5x faster than `trieset` at every width (their compiled lookup beats the
  trie's Seek-first-element). `trieset` still beats `marisa`/`pygtrie` on existence,
  and beats `SortedSet` ~9-15x.
- **Membership:** `trieset` is the fastest *trie* (beats `datrie`, `marisa`,
  `pyahocorasick`), though still a wash-to-slight-loss versus `SortedSet`'s bisect.
- **Memory:** `marisa-trie` is **far smaller** (succinct: ~4.4 B/key image, ~18 B/key
  loaded vs ~73) and serializes/loads a real queryable index almost for free -- but
  it is **read-only** (no `add`/`delete`). `pyahocorasick` is heavier than `trieset`;
  `datrie` needs a fixed alphabet declared up front and builds pathologically slowly.
  (`hat-trie` does not build on Python 3.11+ and was not tested.)

So the niche is a **mutable, arbitrary-byte, no-declared-alphabet** set you
**build incrementally** and **prefix count / collect / autocomplete** -- where
`trieset` is the fastest of the Python tries. If you only need `startsWith`
existence on a near-static set, `datrie` or `pyahocorasick` answer that one op
faster; for a static set where memory is paramount, prefer `marisa-trie`.

## Install

```sh
pip install trieset
```

The first release is a source distribution, so `pip` compiles the CPython
C-extension (`trieset.tt_trieset`) from the binding plus the bundled trie core.
You need a **C++17 compiler** (`g++`/`clang++`; standard on Linux dev machines).
**Portability:** the build uses `-O3` and **not** `-march=native`. The core's SIMD
child-lookup is `__SSE2__`-guarded and SSE2 is the x86-64 baseline, so the build is
correct on every x86-64 CPU (and falls back to a scalar path elsewhere). Prebuilt
binary wheels (no compiler needed) are a planned follow-up.

## Quickstart

```python
from trieset import TrieSet

t = TrieSet([b"apple", b"apricot", b"banana"])
t.add(b"avocado")
t.update([b"cherry", b"apple"])     # set semantics: duplicate is a no-op

b"banana" in t                       # True  (membership: O(len key))
len(t)                               # 5

list(t.prefix(b"ap"))                # [b'apple', b'apricot']  (sorted)
t.prefix_count(b"a")                 # 3                       (O(prefix-len), counted in C)

t.shortest_prefix(b"applesauce")     # b'apple'   (shortest stored key that prefixes the word)
t.longest_prefix(b"applesauce")      # b'apple'
list(t.prefixes(b"applesauce"))      # [b'apple']  (all stored keys that prefix the word)

t.tolist()                           # all keys, sorted (one C loop)
for k in t:                          # stream sorted keys, O(1) peak memory
    ...
t.first(), t.last()                  # (b'apple', b'cherry')

blob = t.flush()                     # all keys, sorted, length-framed bytes:
                                     #   repeated [u32-le len][key bytes]
```

## API and honest limitations

- **Keys are byte strings only.** Any buffer-protocol object
  (`bytes` / `bytearray` / `memoryview`) is accepted on input; every returned key
  is `bytes`. **`str` raises `TypeError`** -- by design (this is a byte-string set).
- **No random `remove` / `discard`.** The core supports only "drain the smallest",
  not delete-by-key, so it is not exposed (avoids an `O(n)` emulation). This is the
  build-then-query / sorted-flush niche; a delete-heavy set is not the target.
- **No multiplicity.** It is a set: a key is present 0 or 1 times.
- **Not thread-safe for concurrent writes** (single-writer core). The GIL is held
  throughout, so concurrent Python threads are serialized correctly.

Type hints ship with the package (`py.typed` + `trieset/__init__.pyi`).

## Prior art (not novel, not first)

The structure is not novel: prior art includes `marisa-trie`, `datrie`, the Cuckoo
Trie, and the Patricia-trie memtables in ToplingDB / TerarkDB. The contribution
here is the **clean from-scratch derivation** plus the **packaged
build + prefix + sorted-flush combination** with honest, measured numbers --
something `SortedSet` and the existing trie packages do not jointly offer. The
shared trie core also backs a RocksDB `MemTableRep` plugin (a separate project).

## License

MIT. See [LICENSE](LICENSE).
