12 ms·

In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve m

In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremely useful - they're compact and fast - but they're unlikely to match a hash table for raw performance.

jules 17y ago
Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup... http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf
- AlisdairO 17y ago
  Thanks for the link! I'll be interested to take a look.
- angstrom 17y ago
  Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.
  - jules 17y ago
    Interesting. How much space saving do you see? DAWGs work for sets, but can it work for key-value maps? (I don't see how, because a final leaf can belong to multiple key prefixes, and therefore multiple associated values).
elblanco 17y ago
I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is. The difference though is on average around 20-30% faster if both implementations are well optimized. But they come with lots of downsides that need to managed well, tries explode into memory very quickly requiring all kinds of memory optimizations to the naive tries to keep the tree depth short (usually with a small hash on the leaves). I remember building an in-memory trie library once in Perl that outperformed a native C hash library by 70%. The development team's jaws dropped when my code was running, they were insisting it wasn't actually doing anything at all and I was faking the output. "There is no way Perl code can outperform our C." It was an interesting learning experience all around. Suffix trees likewise are insane for full text searching. Hashes on the other hand have a few benefits, they are more compact in memory, on average have fast lookups (though if you try and constrain the hash table growth algorithm too much the can spend a lot of time on both collisions and on table growth operations) and have many many more high quality implementations in most standard libraries, including many very good and very fast on-disk hashes that only consume another few percentage points (single digits usually) off of speed. The problem with tries is not that they are fast, there really isn't anything faster (in memory) that I'm aware of for lookup and retrieval problems. But tries are like sports cars, really fast, but lots of downsides. Hashes are like an upper end practical family car. If you try and put the trie on disk, you end up with all sorts of problems that you don't really see in modern on-disk hash implementations. Coming off of disk, hashes tend to be the better option (in fact many of the on-disk trie interfaces I've seen actually just use hashes for the on-disk portion and optimize for tree depth in memory to keep things small). So it depends, if the set of things you want to use for lookups is relatively small and you can cram it all into memory in a raw trie, it'll be a bit faster. If the set is big, and you want to use it off of disk, go with a hash. Also, if the values you wish to store don't map well to a trie, like floating point numbers, you pretty much have to go with a hash. Fortunately, the hash function in that case is really easy ;)
- doty 17y ago
  I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is. Do you have any insight on why this would be? It's not very intuitive to me. A hash-table with low load has relatively small hash buckets and so touches fairly little memory, and string keys are fairly local, so I would have expected memory costs to dominate. Insertion and deletion from a hash table should require fewer allocations than insertion and deletion from a trie.
Dellort 17y ago
If I do recall correctly if you do not require dynamic insertion/removal; That is, you can make do with a one time construction. You will not need to traverse pointers but can put the trie into one contiguous block of memory.
- AlisdairO 17y ago
  That is absolutely true - it's been done with B+Trees, for example, as CSS-Trees. This does make finds faster (because you eliminate the space in the cache that pointers would require), but you're still going to be doing a lot of nonsequential access when performing finds.
signa11 17y ago
what about judy-arrays[http://judy.sourceforge.net/ http://judy.sourceforge.net/] ? they seem to be pretty seriously cache-optimized...
- AlisdairO 17y ago
  I've not encountered them before, but yes, they do seem to be very heavily optimised. I guess with relatively large nodes the quantity of cache misses is relatively low.

jules 17y ago

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup... http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf

AlisdairO 17y ago
Thanks for the link! I'll be interested to take a look.
angstrom 17y ago
Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.
- jules 17y ago
  Interesting. How much space saving do you see? DAWGs work for sets, but can it work for key-value maps? (I don't see how, because a final leaf can belong to multiple key prefixes, and therefore multiple associated values).

elblanco 17y ago

I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is. The difference though is on average around 20-30% faster if both implementations are well optimized. But they come with lots of downsides that need to managed well, tries explode into memory very quickly requiring all kinds of memory optimizations to the naive tries to keep the tree depth short (usually with a small hash on the leaves). I remember building an in-memory trie library once in Perl that outperformed a native C hash library by 70%. The development team's jaws dropped when my code was running, they were insisting it wasn't actually doing anything at all and I was faking the output. "There is no way Perl code can outperform our C." It was an interesting learning experience all around. Suffix trees likewise are insane for full text searching. Hashes on the other hand have a few benefits, they are more compact in memory, on average have fast lookups (though if you try and constrain the hash table growth algorithm too much the can spend a lot of time on both collisions and on table growth operations) and have many many more high quality implementations in most standard libraries, including many very good and very fast on-disk hashes that only consume another few percentage points (single digits usually) off of speed. The problem with tries is not that they are fast, there really isn't anything faster (in memory) that I'm aware of for lookup and retrieval problems. But tries are like sports cars, really fast, but lots of downsides. Hashes are like an upper end practical family car. If you try and put the trie on disk, you end up with all sorts of problems that you don't really see in modern on-disk hash implementations. Coming off of disk, hashes tend to be the better option (in fact many of the on-disk trie interfaces I've seen actually just use hashes for the on-disk portion and optimize for tree depth in memory to keep things small). So it depends, if the set of things you want to use for lookups is relatively small and you can cram it all into memory in a raw trie, it'll be a bit faster. If the set is big, and you want to use it off of disk, go with a hash. Also, if the values you wish to store don't map well to a trie, like floating point numbers, you pretty much have to go with a hash. Fortunately, the hash function in that case is really easy ;)

doty 17y ago
I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is. Do you have any insight on why this would be? It's not very intuitive to me. A hash-table with low load has relatively small hash buckets and so touches fairly little memory, and string keys are fairly local, so I would have expected memory costs to dominate. Insertion and deletion from a hash table should require fewer allocations than insertion and deletion from a trie.

Dellort 17y ago

If I do recall correctly if you do not require dynamic insertion/removal; That is, you can make do with a one time construction. You will not need to traverse pointers but can put the trie into one contiguous block of memory.

AlisdairO 17y ago
That is absolutely true - it's been done with B+Trees, for example, as CSS-Trees. This does make finds faster (because you eliminate the space in the cache that pointers would require), but you're still going to be doing a lot of nonsequential access when performing finds.

signa11 17y ago

what about judy-arrays[http://judy.sourceforge.net/ http://judy.sourceforge.net/] ? they seem to be pretty seriously cache-optimized...

AlisdairO 17y ago
I've not encountered them before, but yes, they do seem to be very heavily optimised. I guess with relatively large nodes the quantity of cache misses is relatively low.