There was a period of about a decade when tries were one of my low-level data structure secret weapons. Constant lookup time for a given key length with none of the rebucketing issues of a hashtable, and for some reason few people seemed to have ever learned about them so they had the added bonus of being a cool new thing I could show people.

But then CPU caches got faster and faster, and low-level data structure performance started to be dominated by cache locality. “Constant number of instructions” and “constant execution time” became somewhat decoupled.

The last time I reached for tries was when I was on the infrastructure team at a large web company circa 2008. We were using memcached and I’d looked at profiling data and discovered that it was spending a nontrivial amount of time computing key hashes.

Aha, I thought, I know how to change this so no hashing is required, and it’ll be super quick to prototype! So I spent a couple hours replacing the hashtables with tries. The profiler confirmed that my implementation needed significantly fewer instructions to look up and insert values.

But it was 4-5x slower in wall time because it was jumping from cache miss to cache miss walking the trie instead of doing a hash computation completely in the L1 cache and only hitting main memory a few times to do the hashtable access. After that, I never touched tries again.

Nerd snipped myself into writing a Go version:

type Trie struct {
	children map[byte]*Trie
}

func NewTrie() *Trie {
	return &Trie{make(map[byte]*Trie)}
}

func (t *Trie) Insert(word string) {
	for _, c := range []byte(word) {
		if t.children[c] == nil {
			t.children[c] = NewTrie()
		}
		t = t.children[c]
	}
	t.children['\x00'] = nil
}

func (t *Trie) wordsWith(prefix string, yield func(string)) {
	for c, t := range t.children {
		if c == '\x00' {
			yield(prefix)
		} else {
			t.wordsWith(prefix+string([]byte{c}), yield)
		}
	}
}

func (t *Trie) Autocomplete(prefix string) []string {
	for _, c := range []byte(prefix) {
		t = t.children[c]
		if t == nil {
			return nil
		}
	}
	var words []string
	t.wordsWith(prefix, func(word string) {
		words = append(words, word)
	})

	return words
}

P.S. Please don’t talk to me about types and dataclasses, I will ridicule you to no end :-)

My man!

P.S. Please don’t talk to me about types and dataclasses, I will ridicule you to no end :-)

What does this mean, @isagalaev?

    def autocomplete(self, prefix):
        for char in prefix:
            self = self.children.get(char)
            if not self:
                return []
        return list(self.words_with(prefix))

? One line shorter, one indent less, we are being specific which expression can KeyError, and we still do only a single dict lookup

For a Ruby example of a Trie, Hanami’s router engine uses one.