4 ms·

This is a nice write-up of the available sensible trie implementations - thanks Bhavin! One thing I'd add is that if you aren't exploiting the ordered nature o

This is a nice write-up of the available sensible trie implementations - thanks Bhavin! One thing I'd add is that if you aren't exploiting the ordered nature of the keys within a trie - i.e. if your keys have no underlying substructure or you aren't doing linear scans through the key space - then you don't want a trie at all and you'd be better off with a hash table. A hash table will be faster and use less memory if your keys are unstructured (imagine for a minute choosing random integers for your keys - then mod N is a good hash function for those keys, so it is obvious a hash table will work well for them, whereas a trie will waste space trying to find common prefixes between random keys.) If you are accessing completely randomly, then the cache utilisation will be similar between a good trie and a hash table. If you are accessing some things more than others, then you should use a move-to-front hash table to be competitive.

joe_the_user 16y ago
Excellent point Further, the article is only an announcement that some benchmarking would be happening later... But (linked directly from the wikipedia article), this article gives benchmarking and a good argument that a "Judy array" is a rather over-engineered solution: http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/ (and that article is linked to the wikipedia article).
jallmann 16y ago
True, but some types of tries sidestep this problem completely -- I'm a big fan of the radix/Patricia tree (mentioned in the article). It uses less space than a hash table, and has a similar asymptotic runtime when you consider the cost of hashing the string itself.
geocar 16y ago
> so it is obvious a hash table will work well for them, whereas a trie will waste space trying to find common prefixes between random keys.) It is obvious, but it is wrong. I observed Judy beating out many hash tables in specifically this situation, and comparing favorably to google's sparsehash. Given its much smaller code size and fewer dependencies this has demonstrated itself a huge win at my organization. Link to my benchmark: http://reddit.com/r/programming/comments/bhxwh/hash_table_benchmarks_google_sparsedense_hash_map/c0mw7hm http://reddit.com/r/programming/comments/bhxwh/hash_table_be...
- jongraehl 16y ago
  If you're talking about performance, you should compare to the dense hash part of the sparsehash package.
  - geocar 16y ago
    I did.
- Robin_Message 16y ago
  Benchmarking beats random ideas, no doubt about that! Thanks for pointing out my mistake with integers. However, I would say Judy doesn't look so hot for string keys - slower at most things and similar memory requirements. I'd be interested to see 10 million 64-bit integers in Judy and DenseHash though. Since ten million is 0.2% of 2^32, in some sense lots of the potential key space is actually in use, so I'd expect a lot of sharing to be possible and a sparse trie to perform well. Is there a 64-bit integer key Judy array you could test on?
  - geocar 16y ago
    > Is there a 64-bit integer key Judy array you could test on? Simply using the 64-bit integer as a 8-byte key is what I use. Treating the 32-bit integer as 4-byte keys performs similarly to using the integer-API directly. > I'd be interested to see 10 million 64-bit integers in Judy and DenseHash though It's easy enough to check :)
bhavintu79 16y ago
thanks robin. i have however noticed in general that a hash table invariably has performance issues in comparison to a trie when storing a large dataset of strings. i guess this is because a trie does guarantee constant time lookup given that in normal circumstances the max length of the string is fixed. a hash table on the other hand does not guarantee constant time lookup due to collisions. another advantage with an optimized trie is that the key does not have to be duplicated. so if there are two keys - "bhavin" and "bhatia" - the first 3 characters do not need to be stored twice making the structure relatively more compact (offcourse this only applies to one of the space-optimized trie structures. in a regular trie since each node would store 26 buckets the total space consumed may actually be considerably higher). lastly i would assume since hash tables are sparse by nature they would take up extra space that tries and trees otherwise do not - Bhavin

joe_the_user 16y ago

Excellent point Further, the article is only an announcement that some benchmarking would be happening later... But (linked directly from the wikipedia article), this article gives benchmarking and a good argument that a "Judy array" is a rather over-engineered solution: http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/ (and that article is linked to the wikipedia article).

jallmann 16y ago

True, but some types of tries sidestep this problem completely -- I'm a big fan of the radix/Patricia tree (mentioned in the article). It uses less space than a hash table, and has a similar asymptotic runtime when you consider the cost of hashing the string itself.

geocar 16y ago

> so it is obvious a hash table will work well for them, whereas a trie will waste space trying to find common prefixes between random keys.) It is obvious, but it is wrong. I observed Judy beating out many hash tables in specifically this situation, and comparing favorably to google's sparsehash. Given its much smaller code size and fewer dependencies this has demonstrated itself a huge win at my organization. Link to my benchmark: http://reddit.com/r/programming/comments/bhxwh/hash_table_benchmarks_google_sparsedense_hash_map/c0mw7hm http://reddit.com/r/programming/comments/bhxwh/hash_table_be...

jongraehl 16y ago
If you're talking about performance, you should compare to the dense hash part of the sparsehash package.
- geocar 16y ago
  I did.
Robin_Message 16y ago
Benchmarking beats random ideas, no doubt about that! Thanks for pointing out my mistake with integers. However, I would say Judy doesn't look so hot for string keys - slower at most things and similar memory requirements. I'd be interested to see 10 million 64-bit integers in Judy and DenseHash though. Since ten million is 0.2% of 2^32, in some sense lots of the potential key space is actually in use, so I'd expect a lot of sharing to be possible and a sparse trie to perform well. Is there a 64-bit integer key Judy array you could test on?
- geocar 16y ago
  > Is there a 64-bit integer key Judy array you could test on? Simply using the 64-bit integer as a 8-byte key is what I use. Treating the 32-bit integer as 4-byte keys performs similarly to using the integer-API directly. > I'd be interested to see 10 million 64-bit integers in Judy and DenseHash though It's easy enough to check :)

bhavintu79 16y ago

thanks robin. i have however noticed in general that a hash table invariably has performance issues in comparison to a trie when storing a large dataset of strings. i guess this is because a trie does guarantee constant time lookup given that in normal circumstances the max length of the string is fixed. a hash table on the other hand does not guarantee constant time lookup due to collisions. another advantage with an optimized trie is that the key does not have to be duplicated. so if there are two keys - "bhavin" and "bhatia" - the first 3 characters do not need to be stored twice making the structure relatively more compact (offcourse this only applies to one of the space-optimized trie structures. in a regular trie since each node would store 26 buckets the total space consumed may actually be considerably higher). lastly i would assume since hash tables are sparse by nature they would take up extra space that tries and trees otherwise do not - Bhavin