21–30 of 36 posts
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
Can bidirectional linear probing be used for any key type? Or do the keys need to be of some integral type?
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
Worth pointing out that this can depend a lot more on fiddly details than you might expect. In particular, you're dealing with a small fixed width allowing the hash to be stored in the table instead of the key. The article emphasizes variable-length keys, and I don't see any specialization on key sizes (if 4- and 8-byte keys aren't common then this makes sense; if they are then I'd expect dedicated table code for tho…
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
Can bidirectional linear probing be used for any key type? Or do the keys need to be of some integral type?
Earlier quoted context omitted.
Worth pointing out that this can depend a lot more on fiddly details than you might expect. In particular, you're dealing with a small fixed width allowing the hash to be stored in the table instead of the key. The article emphasizes variable-length keys, and I don't see any specialization on key sizes (if 4- and 8-byte keys aren't common then this makes sense; if they are then I'd expect dedicated table code for tho…
Thanks for the links; the BQN impl looks really interesting. I believe TFA deals with only hash codes and offsets in the hash table proper (keys and values are stored separately in a dynamic array), so fixed-width keys/values still apply. It's true that you can't use keys interchangeably with hash codes for variable-length keys like I do for integer keys, but I don't expect that to affect the relative performance of…
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
A QuestDB engineer here: These are cool benchmarks! The idea to try Robin Hood probing came to me after receiving some feedback on Reddit. I ran initial experiments, and the results were promising, leading to its integration into our codebase. Thank you so much for sharing your repository. Perhaps one day we'll explore bidirectional probing as well! A snapshot of my happiness after running first experiments with Robi…
I made the initial suggestion to look into Robin Hood hashing when it was first posted on Reddit.
Glad to see it make its way into the repo!
Earlier quoted context omitted.
A QuestDB engineer here: These are cool benchmarks! The idea to try Robin Hood probing came to me after receiving some feedback on Reddit. I ran initial experiments, and the results were promising, leading to its integration into our codebase. Thank you so much for sharing your repository. Perhaps one day we'll explore bidirectional probing as well! A snapshot of my happiness after running first experiments with Robi…
Hi there! I made the initial suggestion to look into Robin Hood hashing when it was first posted on Reddit. Glad to see it make its way into the repo!
Serious question, if performance is the lynchpin, why write it in Java? Especially considering they use unsafe "heavily", for big joins they could easily just call out to some native code if the surrounding code reaaaaally must be Java (again, why?). It's the worst of both worlds using unsafe Java: you don't get native speed, there's loads of memory overhead from everything being an Object (besides the rest of the VM…
Interestingly I recently saw an MQ broker written in Java and it seemed to have some pretty impressive performance. I'm not a huge fan of Java's DX but I have to admit, that's some serious performance. Can't remember the name but it was on the homepage this week I believe.
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
Research results from the last five years shows that Robin Hood hashing performs better than the other approaches under the right conditions. See this eval paper:
https://15721.courses.cs.cmu.edu/spring2023/papers/11-hashjo...
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
> just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks Research results from the last five years shows that Robin Hood hashing performs better than the other approaches under the right conditions. See this eval paper: https://15721.courses.cs.cmu.edu/spring2023/papers/11-hashjo...
> For example, we could already start searching for elements at the slot with expected (average) displacement from their perfect slot and probe bidirectional from there. In practice, this is not very efficient due to high branch misprediction rates and/or unfriendly access pattern.
I think this indicates a regular Robin Hood insertion and modified search, which doesn't sound that similar to Amble and Knuth's method. And anyway the relative costs of mispredictions and cache misses vary wildly based on workflow (paper studies 8-byte keys only). The paper also doesn't present Robin Hood as a clear winner, which is how I interpreted your comment. It's shown as one of five suggestions in the decision graph at the end, and only recommended for load factors between 50% and 80% among other conditions.
Edit: And the paper is from 2015, not the last five years. Is this the right link?