Beating hash tables with trees? The ART-ful radix trie
the-paper-trail.org
Beating hash tables with trees? The ART-ful radix trie
1–10 of 42 posts
Re: Beating hash tables with trees? The ART-ful radix trie
#2I had to implement a trie for an Aho-Corasick implementation a while back, and I just used a std::unordered_set> to store the children (this was Objective-C++, so I was using UTF-16 characters taken from an NSString). Worked well enough for the effort I put into it.
Re: Beating hash tables with trees? The ART-ful radix trie
#3I had to implement a trie for an Aho-Corasick implementation a while back, and I just used a std::unordered_set > to store the children (this was Objective-C++, so I was using UTF-16 characters taken from an NSString). Worked well enough for the effort I put into it.
So you ended up using a tree to hold your tree nodes. I guess that was good enough for your purpose, but the article is discussing an optimized implementation.
Re: Beating hash tables with trees? The ART-ful radix trie
#4I had to implement a trie for an Aho-Corasick implementation a while back, and I just used a std::unordered_set > to store the children (this was Objective-C++, so I was using UTF-16 characters taken from an NSString). Worked well enough for the effort I put into it.
So you ended up using a tree to hold your tree nodes. I guess that was good enough for your purpose, but the article is discussing an optimized implementation.
std::unordered_map is general a hash table, is it not?
Re: Beating hash tables with trees? The ART-ful radix trie
#5A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path compression, and even a LUT accelerator for reaching the Nth level, but hardly could be implemented using a vector.
[1] https://github.com/faragon/libsrt/blob/master/src/saux/stree...
[2] I'm implementing a key-value hash table that will be added to the same library as [1] with "srt_hmap" type, in one continuous allocation. Being able to use hash tables allocated both in the heap and in the stack (e.g. you could use a int32-int32 hash table allocated in the stack for computing the color frequency of a bitmap image). Being the HT performance 4 to 5x the performance of the RB-trees, including cost of rehashing - rehash implementation using techniques for avoiding moving all the data- (rehashing only available for the heap case).
Re: Beating hash tables with trees? The ART-ful radix trie
#6Earlier quoted context omitted.
So you ended up using a tree to hold your tree nodes. I guess that was good enough for your purpose, but the article is discussing an optimized implementation.
std::unordered_map is general a hash table, is it not?
Sorry, I switched set and unordered set in my mind. Still, a generic hash table isn't going to match a tailored data structure.
Re: Beating hash tables with trees? The ART-ful radix trie
#7Earlier quoted context omitted.
std::unordered_map is general a hash table, is it not?
Sorry, I switched set and unordered set in my mind. Still, a generic hash table isn't going to match a tailored data structure.
I mean, it might. I only had to construct one trie, and I used it hundreds of millions of times, so O(1) child (hash) lookup ended up being faster than the O(log(n)) binary search lookup, at best, from the data structure described in the article. And since the data structure in the article wastes some space as well, I may have even used a similar amount of storage.
Re: Beating hash tables with trees? The ART-ful radix trie
#8A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path…
You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.
Re: Beating hash tables with trees? The ART-ful radix trie
#9A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path…
You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.
You can consider the entire virtual memory space to be a big vector, where a pointer is just an index into it!
Re: Beating hash tables with trees? The ART-ful radix trie
#10A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path…
You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.
Yes, that's how works the RB-tree example I linked. However, it is much harder doing that for implementing tries, except if you work only with the full node case, which would imply wasting a huge amount of space. At least, from my experience.