Zero-allocation Trie Traversal | Hacker News Reader

Zero-allocation Trie Traversal

nullprogram.com

112 pointsingve12 comments

This is pretty neat! A couple of thoughts spinning off from this:

In the breadth-first traversal example, it looks like the resulting linked list is completely static. By that I mean that you could pre-compute the traversal order and store it into the linked list of 'p' pointers. Then you can traverse as many times as you want just by following the pointers. In fact, as long as you aren't editing the tree, these traversals should even be reentrant and thread-safe.

I feel like you could do the same sort of thing with depth-first search, or any other scan order really: Do one "expensive" (ie, allocating) traversal to build a linked list, then lots of (comparatively) cheap linked-list-following. Or you could even build the linked list along with the trie, and update both when you add/remove elements (if that's much rarer than traversals). For the latter you'd probably want to use a doubly-linked-list so you don't have to do another search to find the "previous" element.

If you are able to allocate extra memory, or can structure the memory layout appropriately, it might even make sense to (re-)pack the trie nodes in traversal order in memory, so that the memory accesses during a traversal are nice and linear. Again, depends a lot on how you're using the trie and what your constraints are.

Solution to no allocation during trie traversal is to pre-allocate the necessary data along with each node.

Nice, general solution that could apply for many other problems but hardly zero-allocation.

Thanks for the post!

> hardly zero-allocation

Read the article to the end.

What did I miss? He adds fields onto each node to help with traversal.

You missed the last paragraph, I think:

> For a production implementation it may be worth packing i into the flags field since it only needs a few bits, even with larger alphabets. Also, I bet, as in Deutsch-Schorr-Waite, the p field could be eliminated and instead one of the child pointers is temporarily reversed. With these changes, this technique would fit into the original struct trie without changes, eliminating the extra memory usage.

Thanks buddy! I did miss that.

I think you are misreading it, some. Think of it more as "zero allocation during traversal." The point is not "free traversal of a Trie" but another trade off to look at in creating a program. (Granted, one that is at a level most of us are not writing at.)

This is similar, in some ways, to allocation free depth first searches of tree structures. (That is, without a stack.) It is hardly "free" since you have to take care in constructing the tree. However, if you have a tree you will construct once and then want to make sure you can do a DFS without worrying about stack storage, probably a very valuable technique to have in your belt.

Interesting. How would you use one of these implementations to persist a large trie beyond what physical memory can support?

mmap?

Yes. But, the trie implementation would need to somehow allocate mmap file address space. Depending on supported size of the trie, may require multiple mmap files. The addressing scheme would need to consider that. If you want the trie distributed, how would you do that? Would you distribute by some function on the key, essentially resulting in N tries?

Also, if you want to support all 256 values in a byte for each byte of the string to be entered into the trie, the whole idea of using a list structure seems inefficient. On average, to find the next byte in the trie would require 128 comparison operations.

You could write your own memory allocator, overload malloc/alloca etc. and/or `operator new[]` along with `delete`.

http://en.cppreference.com/w/cpp/memory/new/operator_new

In a "typical" case with lots of words with relatively short length, I think simply allocating a stack will outperform this "zero-allocation" scheme, because this algorithm will overwrite every memory page.

I think this algorithm might be a win if the trie contains a huge word (say, 1GB).

Reply on news.ycombinator.com