6 ms·

Does this implementation stops on rehashing? We should stop considering seriously hash tables that stop for rehashing because they can be used only for a subset

Does this implementation stops on rehashing? We should stop considering seriously hash tables that stop for rehashing because they can be used only for a subset of problems, due to the latency. This is one of the main reasons I'm now in love with radix trees and trying to get rid of hash tables at every level in my code.

MaxBarraclough 8y ago
Are radix trees always better? I doubt it.
- thecompilr 8y ago
  Depending on implementation and usage, radix trees can get extremely segmented, slowing down significantly over time.
  - ztorkelson 8y ago
    Would you mind elaborating? I'm not quite sure what you mean by segmented here.
    - MaxBarraclough 8y ago
      I'm not thecompilr, but if I understand them correctly: In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no? I imagine this problem can be ameliorated with a custom allocator, though. Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
      - ztorkelson 8y ago
        Gotcha. Yes, while there are implementation techniques that can help (e.g. arena allocation, prefix compression, adaptive node sizes), the data structure is fundamentally a tree, and so one can expect a higher number of random memory accesses (when compared with suitably optimized hash tables, like those discussed in the article). In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees. Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.
        MaxBarraclough 8y ago
        Arena-allocation? As in (roughly speaking) a Stack<Node> data structure whose lifetime is bound to the lifetime of the tree, right? How could we support deletion of nodes?
        ztorkelson 8y ago
        Right. When you ask "how could we support deletion of nodes", am I right to assume you mean "how could we reclaim memory of deleted nodes"? Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.
        MaxBarraclough 8y ago
        Yes, exactly. It would of course be trivial to unlink a node without reclaiming it, but then you're leaking. Radix trees never rotate, right? Can that be leveraged to help with locality?
        stochastic_monk 8y ago
        This is getting deep into some wizardry, but if you used a custom pool-like allocator you could group contents close together in cache, and, if necessary/appropriate, even rearrange the elements in the container to be more cache-friendly for your purposes.
        thecompilr 8y ago
        You could, but the premise of using a tree was to avoid unpredictable rehashing latency, if you start compacting the tree every now and then, you basically pay the same price.
        MaxBarraclough 8y ago
        That approach tastes rather like a copying+compacting garbage-collector.
      - thecompilr 8y ago
        Thank you. Exactly. Even worse each node could live in a different page. Hash maps can span multiple pages, but the lookup should succeed in 1 or 2 tries for a good hash function.
- jandrewrogers 8y ago
  Not always better, but for most cases where people typically use a hash table it frequently is, assuming the radix tree design and implementation is excellent. There are still a few cases where well-designed hash tables are a better choice e.g. fixed size cache maps with unique keys. But to agree with the OP, there are very few hash tables in my software these days. The downside of radix trees is the space of algorithm designs is pretty exotic, especially high-performance implementations. It is much easier to write a good hash table implementation than a good radix tree implementation.
- utopcell 8y ago
  Not always, but take a look at this recent comparison between modern radix trees and hash maps [1]. [1] https://bigdata.uni-saarland.de/publications/ARCD15.pdf https://bigdata.uni-saarland.de/publications/ARCD15.pdf
- kwillets 8y ago
  Try these string keys: { i * "a" : i = 1 to n } (also great for breaking string sorts)
bluestreak 8y ago
It does rehash when full. Presumably it would rehash less often than most because it remains stable at very high load factor. https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree looks like a funky structure for _very_ specific work loads.
ztorkelson 8y ago
I've found myself reaching for radix trees more and more for the same reason you listed: competitive and predictable performance. That said, I can see two counter-arguments: 1. Rehashing can be avoided if the table size is known in advance. 2. Rehashing is immaterial if the data structure is write-once, read-many. In those cases, we might reasonably expect a hash table to perform better.
- usefulcat 8y ago
  > 1. Rehashing can be avoided if the table size is known in advance With an open addressing implementation (Google's dense_hash_map, for example) this is only true if you rarely or never need to remove items from the map.
- wahern 8y ago
  If the use case is write-once, read-many, you can simply build a perfect hash table. Using techniques like CHD the cost is IME usually in the range of 1x (no cost) to 3x, depending on how compact you want the table, how large it is, and how much time you want to spend up front. Examples from my own small library (http://25thandclement.com/~william/projects/phf.html http://25thandclement.com/~william/projects/phf.html), using 1 million random integers: 80% load -> 0.47s 85% load -> 0.56s 90% load -> 0.74s 95% load -> 1.10s 98% load -> 1.35s 99% load -> 1.68s If I hash the items as C++ string objects rather than uint32 scalars then the time is doubled, presumably because of the dynamic allocation. Which goes to show the "perfect" in perfect hash table doesn't need to be the dominate cost. That said, 90% of the time I just use a simple red-black tree--a so-called intrusive implementation. It makes memory management much easier in C, and rare is the situation where a hash table (let alone a perfect hash table) can make a real difference relative to focusing on all the other inefficiencies.
wrsh07 8y ago
It's a bit funny to write off a hash table that is by design competing with another hash table by saying "it's not a different data structure, so I'm not interested." Moreover, this kind of optimization only makes sense if (1) latency, not throughput, is your bottleneck or (2) if you're really concerned about parallel accesses. A reasonable default in general is to use a hash table + mutex until that is your bottleneck. (I've yet to encounter a scenario where switching from a hash map would provide significant gains in performance-relevant code) Disclosure: I work at Google and use the fancy hash map discussed by Matt. I didn't work on it, though.
- ztorkelson 8y ago
  That's not a very charitable interpretation of the GP. He's not criticizing hash tables because they aren't radix trees. He's criticizing this and other hash table implementations because they have undesirable performance characteristics with respect to his needs, and noting an alternative data structure which he has found to be more suitable. I think that's fair game. Note that there exist hash table implementations which support incremental resizing. I do agree, though, that it's a leap to go from "hash tables with this property are inappropriate under these constraints" to "hash tables with this property should not be considered further", precisely because there is such a broad spectrum of data structure requirements across the industry.
  - stochastic_monk 8y ago
    Additionally, a hash table could be implemented in such a way that it could be updated during resizing. As long as you set up locks in the right places, you could spend the extra memory to do an out-of-place rehash and allow both concurrent writers and your rehashing thread to write to the new table. It's doable, if difficult and error-prone.
  - eternalban 8y ago
    > Note that there exist hash table implementations which support incremental resizing. Rather, there exist hash table algorithms that support incremental resizing. http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/cours...

MaxBarraclough 8y ago

Are radix trees always better? I doubt it.

thecompilr 8y ago
Depending on implementation and usage, radix trees can get extremely segmented, slowing down significantly over time.
- ztorkelson 8y ago
  Would you mind elaborating? I'm not quite sure what you mean by segmented here.
  - MaxBarraclough 8y ago
    I'm not thecompilr, but if I understand them correctly: In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no? I imagine this problem can be ameliorated with a custom allocator, though. Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
    - ztorkelson 8y ago
      Gotcha. Yes, while there are implementation techniques that can help (e.g. arena allocation, prefix compression, adaptive node sizes), the data structure is fundamentally a tree, and so one can expect a higher number of random memory accesses (when compared with suitably optimized hash tables, like those discussed in the article). In some scenarios, radix trees can overcome that with better space efficiency (i.e. implicit key storage), but I think it's fair to say that there are many scenarios (if not most!) where hash tables outperform radix trees. Of course, that all hinges on how you measure performance. As Salvatore pointed out, if you're looking to minimize variance, hash tables might not be suitable due to their growth characteristics. Radix trees also give you efficient sorting and range scans out of the box, and are a viable immutable persistent data structure as well. If none of those are meaningful to your use cases, then hash tables could certainly be a better fit.
      - MaxBarraclough 8y ago
        Arena-allocation? As in (roughly speaking) a Stack<Node> data structure whose lifetime is bound to the lifetime of the tree, right? How could we support deletion of nodes?
        ztorkelson 8y ago
        Right. When you ask "how could we support deletion of nodes", am I right to assume you mean "how could we reclaim memory of deleted nodes"? Conventionally, a free list would be used, though admittedly that sacrifices locality which was one of the original motivating factors. To the extent that deletion is a significant component of the workload, then yeah, this doesn't help.
        MaxBarraclough 8y ago
        Yes, exactly. It would of course be trivial to unlink a node without reclaiming it, but then you're leaking. Radix trees never rotate, right? Can that be leveraged to help with locality?
        stochastic_monk 8y ago
        This is getting deep into some wizardry, but if you used a custom pool-like allocator you could group contents close together in cache, and, if necessary/appropriate, even rearrange the elements in the container to be more cache-friendly for your purposes.
        thecompilr 8y ago
        You could, but the premise of using a tree was to avoid unpredictable rehashing latency, if you start compacting the tree every now and then, you basically pay the same price.
        MaxBarraclough 8y ago
        That approach tastes rather like a copying+compacting garbage-collector.
    - thecompilr 8y ago
      Thank you. Exactly. Even worse each node could live in a different page. Hash maps can span multiple pages, but the lookup should succeed in 1 or 2 tries for a good hash function.
jandrewrogers 8y ago
Not always better, but for most cases where people typically use a hash table it frequently is, assuming the radix tree design and implementation is excellent. There are still a few cases where well-designed hash tables are a better choice e.g. fixed size cache maps with unique keys. But to agree with the OP, there are very few hash tables in my software these days. The downside of radix trees is the space of algorithm designs is pretty exotic, especially high-performance implementations. It is much easier to write a good hash table implementation than a good radix tree implementation.
utopcell 8y ago
Not always, but take a look at this recent comparison between modern radix trees and hash maps [1]. [1] https://bigdata.uni-saarland.de/publications/ARCD15.pdf https://bigdata.uni-saarland.de/publications/ARCD15.pdf
kwillets 8y ago
Try these string keys: { i * "a" : i = 1 to n } (also great for breaking string sorts)

bluestreak 8y ago

It does rehash when full. Presumably it would rehash less often than most because it remains stable at very high load factor. https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree looks like a funky structure for _very_ specific work loads.

ztorkelson 8y ago

I've found myself reaching for radix trees more and more for the same reason you listed: competitive and predictable performance. That said, I can see two counter-arguments: 1. Rehashing can be avoided if the table size is known in advance. 2. Rehashing is immaterial if the data structure is write-once, read-many. In those cases, we might reasonably expect a hash table to perform better.

usefulcat 8y ago
> 1. Rehashing can be avoided if the table size is known in advance With an open addressing implementation (Google's dense_hash_map, for example) this is only true if you rarely or never need to remove items from the map.
wahern 8y ago
If the use case is write-once, read-many, you can simply build a perfect hash table. Using techniques like CHD the cost is IME usually in the range of 1x (no cost) to 3x, depending on how compact you want the table, how large it is, and how much time you want to spend up front. Examples from my own small library (http://25thandclement.com/~william/projects/phf.html http://25thandclement.com/~william/projects/phf.html), using 1 million random integers: 80% load -> 0.47s 85% load -> 0.56s 90% load -> 0.74s 95% load -> 1.10s 98% load -> 1.35s 99% load -> 1.68s If I hash the items as C++ string objects rather than uint32 scalars then the time is doubled, presumably because of the dynamic allocation. Which goes to show the "perfect" in perfect hash table doesn't need to be the dominate cost. That said, 90% of the time I just use a simple red-black tree--a so-called intrusive implementation. It makes memory management much easier in C, and rare is the situation where a hash table (let alone a perfect hash table) can make a real difference relative to focusing on all the other inefficiencies.

wrsh07 8y ago

It's a bit funny to write off a hash table that is by design competing with another hash table by saying "it's not a different data structure, so I'm not interested." Moreover, this kind of optimization only makes sense if (1) latency, not throughput, is your bottleneck or (2) if you're really concerned about parallel accesses. A reasonable default in general is to use a hash table + mutex until that is your bottleneck. (I've yet to encounter a scenario where switching from a hash map would provide significant gains in performance-relevant code) Disclosure: I work at Google and use the fancy hash map discussed by Matt. I didn't work on it, though.

ztorkelson 8y ago
That's not a very charitable interpretation of the GP. He's not criticizing hash tables because they aren't radix trees. He's criticizing this and other hash table implementations because they have undesirable performance characteristics with respect to his needs, and noting an alternative data structure which he has found to be more suitable. I think that's fair game. Note that there exist hash table implementations which support incremental resizing. I do agree, though, that it's a leap to go from "hash tables with this property are inappropriate under these constraints" to "hash tables with this property should not be considered further", precisely because there is such a broad spectrum of data structure requirements across the industry.
- stochastic_monk 8y ago
  Additionally, a hash table could be implemented in such a way that it could be updated during resizing. As long as you set up locks in the right places, you could spend the extra memory to do an out-of-place rehash and allow both concurrent writers and your rehashing thread to write to the new table. It's doable, if difficult and error-prone.
- eternalban 8y ago
  > Note that there exist hash table implementations which support incremental resizing. Rather, there exist hash table algorithms that support incremental resizing. http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/cours...