Learning 02 · what ds4 actually uses them for
We went looking because an earlier note claimed “ds4's tokenizer uses a radix tree.” Reading the code, that turned out to be wrong — and untangling it is a good excuse to learn what a radix tree actually is and when you'd reach for one.
Failed Star ds4.c). The radix tree does exist in ds4 — but it lives in the
server's agent memory (ds4_server.c), a completely separate job.
Start from a plain trie
A radix tree (a.k.a. radix trie, or compact prefix
tree) stores strings as keys: the path from the root down to a node
spells out the key. Its defining trick is edge compression. To see it,
start from a plain trie — one character per edge — storing
"tea", "team", "ten":
(root)
└─ t ── e ── a ── m "team"
└ ● "tea"
└ n ── ● "ten"Every node branches up to N ways (one per possible next byte). The
waste: a long run with no branching still costs one node per character.
"tokenizer" would be a 9-node single-file chain — bad for both memory and
pointer-chasing.
The radix-tree fix: collapse any chain of single-child nodes into one edge labeled with the whole substring. Nodes appear only where keys diverge:
"te" is stored once; the tree branches only where the keys
actually split — after te (a vs n), and after
tea (end vs m). Edges are labeled with sequences,
not single symbols — that's the “radix” idea.Why you'd reach for one:
foo”, longest-prefix matching, ordered iteration.How it stacks up
| Hash table | Radix tree | Sorted array + binary search | |
|---|---|---|---|
| Exact lookup | ~O(1) after hashing | O(key length) walk | O(key length × log n) |
| Ordered iteration | ✗ | ✓ (lexicographic) | ✓ |
| Prefix / range queries | ✗ | ✓ (the whole point) | partial |
| Shares memory across common prefixes | ✗ | ✓ | ✗ |
| Cache behavior | one hash, random probe | many small pointer hops | good (contiguous) |
Two structures, two jobs
Two separate data structures, two separate jobs — and the radix tree is not the one in the tokenizer.
ds4's byte-level BPE does repeated exact lookups: “is this exact byte string a known token, and what's its id?” and “what's the merge rank of this exact pair?” No prefixes, no ordering — so an open-addressing hash table fits:
str_i32_table — ds4.c:20689 (power-of-two capacity,
hash_bytes + linear probing).token_to_id / merge_rank — ds4.c:20791.table_get in the BPE inner loop — e.g. ds4.c:21016.antirez's rax library is
compiled into ds4, but it powers the built-in agent's tool-memory store,
not the tokenizer:
m->by_id = raxNew(); and m->by_block = raxNew();
— ds4_server.c:7764.raxInsert / raxFind, ~ds4_server.c:7808).The radix tree is a sensible fit here: memories are keyed by strings you want
ordered and prefix-addressable access to — exactly its strength. (Redis,
also antirez, uses the same rax for stream IDs for the same reasons.)
The takeaway
ds4.c); ds4's agent memory is
the second (radix tree, ds4_server.c). A radix tree can tokenize (handy
for greedy longest-match schemes like WordPiece/Unigram), but byte-level BPE doesn't need it.
Follow ds4's actual design: a hash map
(HashMap<Vec<u8>, u32> for token→id, plus merge ranks) is all
byte-level BPE needs. Reach for a trie/radix structure only if we later add a
longest-match tokenizer that benefits from prefix walking.
HashMap for token→id and merge ranks.rax.c/rax.h
(the radix library) used by ds4_server.c; the tokenizer hash table lives in
ds4.c.rax library, used there for stream IDs.docs/learnings/02-radix-tree.md.