trie-hard: a trie for small maps where most lookups miss

The use case, stated precisely

The title of the project is a joke that also describes it: don't just trie, trie hard. The readme's own summary is a novel implementation of a trie data structure optimised for small, sparse maps.

The optimisation target is more specific than that, and it is the sentence that follows: it is optimised for reading from small maps where a large number of misses are expected.

So there are three conditions, and all three have to hold for the crate to be the right answer. The map has to be small. It has to be sparse. And the lookups against it have to fail most of the time.

The production example tells you all three at once. The crate is used in Cloudflare's Pingora proxy to detect and remove specific headers from thirty million requests every second, before they are proxied to their final destinations.

That is a beautiful example, because it is the case where a hash map is at its worst. The set of headers to strip is small and fixed, and almost every request has none of them. So the work is: for each request, look up each header in a set of maybe a hundred entries, and find that it is almost never there. A hash map answers that question by hashing the whole string and comparing. A trie can answer it by looking at the first byte and ruling the key out immediately.

The readme is also explicit about the limits. This is still a work in progress in the sense that none of the other features you would expect to find in a trie are there, with prefix search given as the example. So the crate is not a trie in the general sense, it is one specific operation done very fast.

And the readme is unusually direct about who should not use it. There are several other trie implementations for Rust that are more full-featured, and the recommendation for a more careful tool is the radix trie crate, which the readme says seems to have the best features and performance. On the other hand, if you want raw speed and have the same narrow use case, you came to the right place.

The benchmark, and the number that decides everything

The performance section shows a chart of the time taken to read ten thousand entries from a map of one hundred and nineteen entries, where the keys contain only lower case characters, numbers, and a hyphen.

The shape of the result is the interesting part, not the absolute numbers. When the miss rate gets above fifty percent, the performance of trie-hard surpasses the standard hash map, and the improvement grows as the miss rate gets higher.

That is the whole thesis of the crate, expressed as a crossover point. Below half misses, a hash map is the better structure, and trie-hard is slower. Above half misses, a trie wins, and it wins by more the further you go.

The reason is the difference in what has to be examined. A hash map must hash the entire key, which means reading every byte of it, and then it does a comparison. A trie examines the first byte against the node's mask and can conclude the key is absent without looking at the second byte. When most lookups miss, the trie almost never has to look past the first byte, and the cost of a miss becomes proportional to the length of the common prefix with any key, which for a header name is usually one or two bytes.

The readme also notes that this is not a quirk of the implementation but a property of tries in general, and that the same trend appears in the radix trie's performance.

So the design of the crate is not to be fast in general. It is to be fast in the specific regime where the alternative is worst, and the benchmark is built to demonstrate exactly that regime rather than to produce a flattering average. The map in the benchmark is a hundred and nineteen entries of lower case text, which is a reasonable model of a set of HTTP header names, and the miss rate is swept so that you can see where the crossover is.

The second chart compares against the radix trie, and the readme's caption says what it shows: trie-hard reads faster, but it follows the same curve. So the two are the same shape of behaviour with a constant difference between them, and the constant is the implementation quality, not a different idea.

The honest comparison with the radix trie

The readme goes out of its way not to oversell, and the paragraph about the radix trie is the best example of that.

It says the difference in read performance between the two should not be interpreted as a reason to use trie-hard over radix-trie, because radix-trie is a full-featured trie that balances read performance with write performance. And then, for fairness, it gives the loading numbers side by side.

The table is short. Loading fifteen and a half thousand words takes eleven point nine two milliseconds in trie-hard and three point four nine milliseconds in the radix trie. And the summary is that for insertion the radix trie is about three times faster, and also supports incremental changes, whereas trie-hard is only designed for bulk loading.

That is a fair exchange rate and the readme states it plainly. You give up write performance and the ability to change the map after it is built, and you get read performance in the high miss rate regime.

The bulk loading constraint is the one that decides whether the crate is usable for a given workload, and it follows from the design rather than from a limitation of the implementation. The whole structure is laid out contiguously, which means the nodes are numbered in a fixed order and the child pointers are indices into that array. Adding a key after the fact would mean renumbering, or it would mean giving up the contiguity. So the crate does the former by not supporting it at all.

For the header filtering case that is exactly right, because the set of headers to strip is determined by configuration and does not change while the process runs. For a workload where the set changes, the radix trie is the better tool and the readme says so.

So the readme is doing something slightly unusual: it is presenting a case where its own crate is the right answer, in terms of a comparison it has already lost on one axis and has chosen not to hide.

How the structure works

The readme says trie-hard achieves its speed in two ways, and both are about memory rather than about algorithms.

The first is that all node and edge information is kept in contiguous regions on the heap. This prevents jumping around in memory during reads, and it maximises the chance that child nodes are already in the cache. That second clause is the important one, because a trie lookup is a chain of dependent memory accesses: you cannot know where the next node is until you have read the current one, so every step is a potential cache miss, and a layout that puts the likely next nodes next to each other is worth more than any instruction count optimisation.

The second is that relationships between nodes and edges are encoded into individual bits in unsigned integers.

The worked example makes the encoding concrete. The keys are the strings for and, ant, dad, do, and dot, and the construction is a single collect into the trie type.

let trie = ["and", "ant", "dad", "do", "dot"].into_iter().collect::<TrieHard<'_, _>>();

The first thing the construction does is find all of the bytes used in the entries and assign each one a unique single-bit mask. For that set of keys there are five distinct bytes, and the readme gives the table: a is one bit, d is two, n is four, o is eight, and t is sixteen.

The number of masks required then determines the integer type used to hold the mask. Five bits means the underlying type is a single byte. The implication is that needing a bit for each unique byte means you could need a two hundred and fifty-six bit integer, so the crate provides an implementation of that type.

The next step is to build the graph, starting from the bytes that appear first in the input strings. Only a and d appear in the first position, so the node for the first byte, which is also the root of the trie, gets a mask saying only a and d are allowed.

let root = Node {
    // a (0b00001) + d (0b00010) = 0b00011
    mask: 0b11,
    // ..
}

And the readme draws the conclusion: if a byte other than a or d appears in the first position, the key being tested does not appear in the trie.

That is the whole trick, and the readme states its value plainly. This ability to make an exclusion decision at every step is what makes tries more appealing than even hash maps in some cases, because searching for a string in a hash map requires hashing the entire string, whereas a trie can potentially determine that a string is not part of a set within a single byte.

The child arrays, and the final layout

The readme then explains the child storage, and there is a note at the end that changes the picture.

All of the nodes in the graph are stored in a contiguous vector, with the root node at index zero. Each node contains the information about where its children appear in that array of nodes. In the example, the root points to the nodes at indexes one and two, where one is the node for keys starting with a and two is the node for keys starting with d. And the children are ordered by their corresponding byte, which is what makes the lookup a sequence of bit tests rather than a search.

The initial illustration of that has the children as a vector in the node itself.

let root = Node {
    mask: 0b11,
    // 1 -> keys that start with b'a'
    // 2 -> keys that start with b'd'
    children: vec![1, 2],
    // ..
}

And then the note changes it. In the final map, the child indices are not stored in per-node vectors. They are instead stored in a central vector, and only the index into that vector corresponding with this node is stored in the node.

That is a significant change and it is the right one. A per-node vector is a separate heap allocation per node, and an allocation is worse than an inline array for cache purposes and for allocation cost. A central vector of child indices means the children of every node are packed together, and the node holds a single offset and a length. The readme's first implementation section says the same thing from the other direction, that all node and edge information is kept in contiguous regions on the heap, and the note is the concrete detail of how the edges are arranged.

So the final layout has two contiguous regions, the nodes and the child indices, and the children of a node are ordered by byte so that the mask test selects one directly. The mask says which bytes are possible, the ordering says which index each byte corresponds to, and the contiguous layout means the fetch of the next node is likely to be a cache hit.

That is the whole design in three properties: a bit mask per node, an ordering by byte, and a layout in which the nodes you are likely to need next are near the ones you are already looking at.

The wide integer, the byte limit, and the repository

One detail in the readme deserves its own paragraph, because it is the kind of thing that is easy to read past and expensive to discover later.

The mask type is chosen by the number of distinct bytes in the keys, and in the worst case that is every possible byte, which would need a two hundred and fifty-six bit integer. So the crate provides an implementation of that type. And then the note: it should not be used directly, it only implements and tests the few operations needed to work with the crate.

Then the real constraint. The use case the crate was designed for needs to support at most thirty-seven unique bytes, and in practice only thirty unique bytes appear in the stored map. Which means the tree information is stored in single-word integers, four bytes wide.

So the crate carries a very wide integer type for a case it will never hit in practice. That is a defensible engineering choice and an unusual one, and the readme is upfront about it. The alternative would be to restrict the crate to fewer than two hundred and fifty-six distinct bytes and fail at construction, and the chosen approach is to make the general case work while documenting that the fast path is the narrow one.

The repository layout matches a crate that is mostly one library with a lot of measurement around it. There is a source directory, a build script, a data directory with what is presumably the benchmark data, a resources directory holding the two benchmark charts, a benches directory, a formatting configuration, and an unusual file called a bleep configuration at the root.

The manifest shows the measurement setup in detail, and it is thorough in a way that tells you the claims were checked rather than asserted. There are two benchmark harnesses, and both are declared with the harness disabled, which is what you do when the benchmark framework provides its own timing rather than using the standard test harness. One is a criterion bench and one is a divan bench, so the results can be produced in two formats and compared across tools.

The development dependencies include the radix trie itself, which is the point: the crate benchmarks itself against the alternative it recommends to other people. There is also the perfect hash library, both as a dependency and as a build dependency, and the build dependency is the code generator, which is how a compiled lookup table is produced at build time. The testing stack includes a parameterised test framework and a macro for writing cases.

The crate version is zero point two, the edition is a recent one, and it is published with a data structures category and keywords for trie and prefix search, which is a small mismatch with what the crate actually does, and a small thing to notice if you are searching for it.

Editorial conclusion

trie-hard fits a workload with a small fixed set of keys, a high proportion of lookups that will not be found, and a hot path where the difference between a hash and a mask matters, such as filtering a header on every request. It does not fit a workload that needs prefix search, incremental insertion, or a general purpose map, because the crate deliberately does not implement them. Verify first that your miss rate is high enough for the curve in the benchmarks to apply, since below half the crate is slower than the standard hash map, that the set of keys is small, because the advantage comes from the map being small, and that bulk loading is acceptable, since the design does not support changing the map after it is built.

Frequently asked questions

Official sources

1. cloudflare/trie-hard on GitHub
2. Issues
3. License: Apache-2.0
4. README