News for hackers. Stuff that matters.
Re:Advanced techniques to implement fast hash tables by gabeiscoding on Tuesday October 23, 2018 @10:23PM (#18289207)
The 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 by sametmax on Wednesday October 24, 2018 @03:44AM (#18290421)
How does that compare to the dict implementation of Python 3.6 ? It's supposed to be damned fast but I don't have the skills to make such comparisons.
Re:Advanced techniques to implement fast hash tables by woadwarrior01 on Wednesday October 24, 2018 @05:21AM (#18290871)
The split keys and values arrays in Python 3.6 dictionaries make it more compact than dictionaries from earlier versions of Python, which makes it more cache friendly. But Python dictionaries (and sets) use a variant of double hashing for collision resolution, which is less cache friendly than Robin Hood hashing's linear probing. It's certainly possible to combine both techniques to come up with a hybrid dictionary with the best aspects of both split keys and Robin Hood hashing.
Re:Advanced techniques to implement fast hash tables by rurban on Thursday October 25, 2018 @03:45AM (#18299203)
Python, ruby, php hash tables are roughly 2x slower. perl5's being the worst maybe 4x slower.

Damn fast is only relative. It's damn fast compared to the previous implementations. Wikipedia even dares to say that the worst hash tables of all, perl5, is one of the very best. Bias all over.

SIMD optimized hash tables, such as the Swiss tables tricks have the potential to be much faster than khash. And khash is not cache oblivious at all, with its double hashing scheme.

Re:Advanced techniques to implement fast hash tables by sametmax on Thursday October 25, 2018 @08:26AM (#18300336)
Does it preserves insertion order ?
Re:Advanced techniques to implement fast hash tables by rurban on Thursday October 25, 2018 @11:53AM (#18301861)
Of course not. hash table iteration should assume random order, otherwise it's a security risk or performance nightmare.
Re:Advanced techniques to implement fast hash tables by romed on Wednesday October 24, 2018 @01:51AM (#18290017)
Hrmm 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<int,int> is sort of niche.

https://abseil.io/blog/20180927-swisstables

Re:Advanced techniques to implement fast hash tables by jorangreef on Tuesday October 23, 2018 @01:10PM (#18285254)
I 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 by notatcomputer68 on Tuesday October 23, 2018 @02:07PM (#18285834)
Nit: 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 by attractivechaos on Tuesday October 23, 2018 @09:57PM (#18289081)
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 by abhishekjha on Wednesday October 24, 2018 @02:23AM (#18290131)
>addition instead of multiplication

What is the advantage of this?

Re:Advanced techniques to implement fast hash tables by amelius on Wednesday October 24, 2018 @02:38AM (#18290177)
Addition being cheaper than multiplication on many CPUs?
Re:Advanced techniques to implement fast hash tables by sametmax on Wednesday October 24, 2018 @03:44AM (#18290417)
ELI5: wouldn't it be the job of the compiler ?
Re:Advanced techniques to implement fast hash tables by amelius on Wednesday October 24, 2018 @03:46AM (#18290426)
Sort of, but there are no guarantees.
Re:Advanced techniques to implement fast hash tables by namibj on Tuesday October 23, 2018 @10:01PM (#18289095)
klib 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 by maxxxxx on Tuesday October 23, 2018 @10:22PM (#18289202)
I 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 by timClicks on Tuesday October 23, 2018 @11:11PM (#18289413)
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 by informatimago on Wednesday October 24, 2018 @08:12AM (#18291711)
Your choice: either you want to earn money to buy toys or feed a family, or you can have poetic fun with high level maths and algorithmics.
Re:Advanced techniques to implement fast hash tables by esotericn on Wednesday October 24, 2018 @11:42PM (#18298420)
Anyone who wants to.

That may mean wanting something else less.

If that's not acceptable, they didn't want to.

And that's fine.