4 ms·

Tries can be memory hogs and the techniques for level and path compression can add significant overhead. It would have been interesting to see memory usage. I'

Tries can be memory hogs and the techniques for level and path compression can add significant overhead. It would have been interesting to see memory usage. I've of the more interesting data structures for things like this are Ternary Search Trees after each subtree starts with a common prefix. That would have been an interesting comparison. https://en.m.wikipedia.org/wiki/Ternary_search_tree https://en.m.wikipedia.org/wiki/Ternary_search_tree

mtanski 10y ago
Overhead, fragmentation, pointer chasing, malloc() bound. It's one of those data structures that makes perfect sense in CS theory but is only applicable in a limited set of real world problems. For now we're beholden to implementation of our architectures, their quirks and side effects.
- jnordwick 10y ago
  You can fix some of that and techniques like a binary trie can give better cache performant/smaller levels, but while a trie sounds simple they are surprisingly difficult to get to perform better. The optimizations for hashes are far easier to implement IMHO
- blt 10y ago
  Using a memory arena helps a lot with the problems you mentioned.
  - wmu 10y ago
    That's true. Years ago I did some experiments with various trie representations and despite my effort, glibc malloc was reporting 40-50% of internal fragmentation. Once switched to memory arenas, I nearly rid off fragmentation.
- rocqua 10y ago
  Suffix tries are an even better example. Donald Knuth once heralded them as the greatest algorithmic break-through of the '70s but in practice, it doesn't quite perform. The point of suffix tries is finding substrings. I.e. build a suffix trie of all of Shakespear's works in linear time and memory (linear w.r.t. the total length of the string). And then, given a potential quote of length K, see if it is in Shakespear's work in O(K) time. The big draw there is that the complexity of string lookups does not depend on the length of the big text against which you are matching. This finds practical use in genome sequencing.
  - danieldk 10y ago
    Suffix arrays, on the other hand, have worse complexity in the typical implementation (O(n) construction, O(k + log(n)) search [1]). However, they work extremely well in practice, because they use (contiguous) arrays. [1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703000650 http://www.sciencedirect.com/science/article/pii/S1570866703...
    - rocqua 10y ago
      If I recall correctly, the linear search approach is based on constant time range minimal query on the suffix array. That feels rather likely to also be worse in real life applications. Heck, as far as I can tell, this approach is just another way of storing a tree.
  - jnordwick 10y ago
    Or Fibonacci trees. I have seen suffix tries used in the wild. I have yet to see a Fib tree. Shown to be optimal in a number of tree operations, horribly slow in practice..
danieldk 10y ago
There are still some interesting applications of tries (and dictionary automata). E.g., if you want to find all words given a prefix (wildcard searches). If the dictionary is static, you could use an array with binary search, however for dynamic dictionaries this gives you O(n) insertion. Ternary search trees are really great and relatively compact. A while ago, I compared memory use of storing a dictionary (the SOWPODS word list) in Rust using various tries (as measured with the heapsize crate): - Trie, using a HashMap to store edges: 691MB - Trie, using a sorted Vec to store edges: 44MB - Ternary search tree: 18MB A typical ternary search trie is even more compact, but I implemented randomized ternary search tries, which uses two extra member variables in each node for bookkeeping (in these measurements u16s).

mtanski 10y ago

Overhead, fragmentation, pointer chasing, malloc() bound. It's one of those data structures that makes perfect sense in CS theory but is only applicable in a limited set of real world problems. For now we're beholden to implementation of our architectures, their quirks and side effects.

jnordwick 10y ago
You can fix some of that and techniques like a binary trie can give better cache performant/smaller levels, but while a trie sounds simple they are surprisingly difficult to get to perform better. The optimizations for hashes are far easier to implement IMHO
blt 10y ago
Using a memory arena helps a lot with the problems you mentioned.
- wmu 10y ago
  That's true. Years ago I did some experiments with various trie representations and despite my effort, glibc malloc was reporting 40-50% of internal fragmentation. Once switched to memory arenas, I nearly rid off fragmentation.
rocqua 10y ago
Suffix tries are an even better example. Donald Knuth once heralded them as the greatest algorithmic break-through of the '70s but in practice, it doesn't quite perform. The point of suffix tries is finding substrings. I.e. build a suffix trie of all of Shakespear's works in linear time and memory (linear w.r.t. the total length of the string). And then, given a potential quote of length K, see if it is in Shakespear's work in O(K) time. The big draw there is that the complexity of string lookups does not depend on the length of the big text against which you are matching. This finds practical use in genome sequencing.
- danieldk 10y ago
  Suffix arrays, on the other hand, have worse complexity in the typical implementation (O(n) construction, O(k + log(n)) search [1]). However, they work extremely well in practice, because they use (contiguous) arrays. [1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703000650 http://www.sciencedirect.com/science/article/pii/S1570866703...
  - rocqua 10y ago
    If I recall correctly, the linear search approach is based on constant time range minimal query on the suffix array. That feels rather likely to also be worse in real life applications. Heck, as far as I can tell, this approach is just another way of storing a tree.
- jnordwick 10y ago
  Or Fibonacci trees. I have seen suffix tries used in the wild. I have yet to see a Fib tree. Shown to be optimal in a number of tree operations, horribly slow in practice..

danieldk 10y ago

There are still some interesting applications of tries (and dictionary automata). E.g., if you want to find all words given a prefix (wildcard searches). If the dictionary is static, you could use an array with binary search, however for dynamic dictionaries this gives you O(n) insertion. Ternary search trees are really great and relatively compact. A while ago, I compared memory use of storing a dictionary (the SOWPODS word list) in Rust using various tries (as measured with the heapsize crate): - Trie, using a HashMap to store edges: 691MB - Trie, using a sorted Vec to store edges: 44MB - Ternary search tree: 18MB A typical ternary search trie is even more compact, but I implemented randomized ternary search tries, which uses two extra member variables in each node for bookkeeping (in these measurements u16s).