Skip to content

A Tree Made of Types

Edit source

A word lookup the compiler builds letter by letter, and why it lost the race.

Part 33 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. This one is a word list the compiler turns into a tree: ctrie.

Think of how you find a word in a paper dictionary. You do not read it from the first page. You open to the P section, then look for PO, then POS, and each letter throws away most of the book. A trie (pronounced “try”, from retrieval) is that idea as a data structure: a tree where every step down is one letter, and words that start the same way share the same path for as long as they agree.

Programs often look words up in a fixed list known before they run: an HTTP server asking whether a request is GET, POST or PUT, a query language checking its reserved words. Since the list never changes, the compiler can do the work once, at build time.

ctrie does that. You hand it the words, and it gives back an object whose find() returns each word’s position in your list, or ctrie::npos (a special “not found” value) for anything else:

// The trie is built while compiling; these checks run in the compiler too.
constexpr auto methods = ctrie::build("GET"_cword, "POST"_cword, "PUT"_cword);
static_assert(methods.find("POST") == 1);
static_assert(methods.find("PATCH") == ctrie::npos);

A static_assert is a check the compiler performs while building. If either line were wrong, the program would not compile. The same find() works at run time on a string a user typed.

Most tries live in memory: nodes allocated on the heap, pointers from parent to child. ctrie keeps none of that. Every node is a C++ type, the kind of thing the compiler tracks the way it tracks int or std::string, and the tree is those types nested inside each other. For the three words above, the shape the compiler builds looks like this:

root
├─ G ─ E ─ T ─ (end) = 0
└─ P ─┬─ O ─ S ─ T ─ (end) = 1
└─ U ─ T ─ (end) = 2

POST and PUT share the P node and split after it. Each word also gets an invisible end marker, and the word’s position is stored there, so PO walks two letters, finds no end marker, and comes back as not found. A prefix is not a word, and neither is POSTS; the tests check both.

The _cword suffix is what makes this possible. It is a literal operator, a small function that the compiler calls on a string literal, and this particular form hands the function the string’s characters one by one as compile-time values. That is how "GET" becomes three letters the type system can arrange into a tree. When the program runs, the tree is gone. What is left is the code that walks it: compare the next character, step into the matching child, repeat. No tables, no allocation, nothing to initialize at startup.

The perfect hash from earlier in this chapter solves the same problem a different way. It turns the word into a number with a hash function, then jumps straight to that number’s slot, a fixed handful of arithmetic no matter how many words there are. A trie cannot jump. At every letter it tries the children one after another until one matches, so at the root of a list of 570 English stop words it may compare the first letter against many candidates before it takes a single step.

The constexpr-phf benchmarks time ctrie beside the perfect hash and the standard containers on two real word sets: Xapiand’s 192 field-type names, looked up 200,000 times with half of them misses, and the 570 stop words filtered out of the whole text of The Count of Monte Cristo. Here is the perfect hash with its membership check, ctrie, and std::unordered_set (the standard library’s hash table), on an Apple M4 Pro and an Intel Core i9:

ContenderNames, M4 (ns)Names, i9 (ns)Stop words, M4 (ms)Stop words, i9 (ms)
Perfect hash, verified14.121.44.536.74
ctrie19.830.97.6012.1
std::unordered_set20.040.97.0715.7

The perfect hash wins every column. ctrie takes about 1.4 times as long on the names and 1.7 to 1.8 times as long on the stop words. Against the standard hash table it is a tie on the M4 and clearly ahead on the Intel machine, which is respectable for a structure with no hash function at all.

So when does a tree of types beat a perfect hash? Not on speed, in any of these runs. Its advantages are of a different kind. It needs no hash function, so there is no choice of hash to tune and no chance of two words colliding. It is always exact: the perfect hash’s fastest mode skips the final string comparison and can mistake a stranger for a member whose hash it shares, while ctrie compares every letter and cannot. And a miss can end at the first letter that no word in the set starts with. Those make it a clear, honest reference, and the right yardstick to keep the faster thing truthful.

Three things bite, and all three come from living inside the compiler.

Every word costs build time. Building the tree is the compiler instantiating types, one step per word and one node per new letter, so a bigger list means a slower build, paid on every compile. The steps also nest, one inside the last, and compilers cap how deep that nesting may go. The 570 stop words fit under the default; a list of many thousands is the wrong job for this tool.

The literal operator is not standard C++. The form of _cword that receives a string’s characters is an extension that Clang and GCC accept and MSVC rejects, and Clang warns about it. The header silences that warning around the one line that needs it. For a while it switched the warning off and never switched it back on, so every file that included ctrie had the warning quietly disabled for its own code too, like a “do not disturb” sign left on a door after the meeting ended. The header now restores the setting right after the operator.

Release builds deleted the tests. The run-time checks were plain asserts, which a Release build removes. With them gone, one test variable was left unused, the warnings-as-errors build failed, and in any case nothing was being checked. The test now forces its asserts on in every build type, so Debug and Release both run every lookup.

Xapiand does not call ctrie today. Its keyword dispatch runs on constexpr-phf, and ctrie lives on as the contender in that library’s benchmarks, where it keeps the perfect hash honest. It is one C++17 header with no dependencies, tested in CI on Linux, macOS and FreeBSD.

Reach for it when you want the simplest exact answer to “which of these few words is this?”, checkable in a static_assert, with no hash to pick, or as a readable reference for how a type-level trie works. Skip it for production dispatch, where the perfect hash is faster on every measured set, for large word lists, and for MSVC.