Advanced techniques to implement fast hash tables
attractivechaos.wordpress.com
Advanced techniques to implement fast hash tables
1–10 of 22 posts
Re: Advanced techniques to implement fast hash tables
#2I recently wrote https://github.com/ronomon/hash-table for Node.js, which has a few more design tips listed in the Readme, specifically around optimizing a cuckoo hash table by reducing cache misses.
Re: Advanced techniques to implement fast hash tables
#3Nit: You should implement quadratic probing with triangular numbers by addition for a slight speedup. I.e. x+= i, rather than x = ... × ...
Re: Advanced techniques to implement fast hash tables
#4Nit: You should implement quadratic probing with triangular numbers by addition for a slight speedup. I.e. x+= i, rather than x = ... × ...
Of course. Notable libraries implementing quadratic probing all use addition instead of multiplication. The example in the blog post is just for demonstration purpose.
Re: Advanced techniques to implement fast hash tables
#5klib could do with a bit more documentation for what the abbpreviated argument and function names do.
Apart from that, I just have praise for this. It's succinct, performance-oriented and comparatively portable. From what I reversed for the purpose of grasping the effect of parameters, I like the interface/API, but the scope over which I am speaking is pretty much limited to basic kbtree, due to the lack of documentation.
Re: Advanced techniques to implement fast hash tables
#6I love this stuff but how many of us really get to (have the privilege) to doing this kind of work?
Re: Advanced techniques to implement fast hash tables
#7The author of this post wrote klib/khash, and uses it in his very popular cpu-intensive bioinformatics programs such as bwa (short read alignment against the human ref genome).
I've been learning rust recently. As a learning exercise, I compared the robin-hood hashing of std::collections::HashMap in rust to his klib/khash he mentions in this article , and then tried various hash functions to try and match his performance:
https://github.com/gaberudy/hash_test
No dice, his hash table is smaller and faster.
My next step is to try and implement his data structure and hashing functions directly in rust and see if I can get it to near-C performance...
Re: Advanced techniques to implement fast hash tables
#8I love this stuff but how many of us really get to (have the privilege) to doing this kind of work?
If you're writing code in C/C++/Rust/... then your code will benefit from understanding hash function performance because the choice of function can be another parameter to tune.
Re: Advanced techniques to implement fast hash tables
#9Hrmm this is the first I’ve heard that Google has opened swisstable[1]. Strangely the three submissions to HN of this attracted no comments. This blog is interesting but a write-only benchmark of a hash is sort of niche.
Re: Advanced techniques to implement fast hash tables
#10Nit: You should implement quadratic probing with triangular numbers by addition for a slight speedup. I.e. x+= i, rather than x = ... × ...
Of course. Notable libraries implementing quadratic probing all use addition instead of multiplication. The example in the blog post is just for demonstration purpose.
>addition instead of multiplication
What is the advantage of this?