Re:C++ macros to write a hashtable implementation
by Xophmeister on Saturday March 10, 2018 @04:36PM
(#16560282)
For some _real_ CPP abuse, check out klib’s hash table implementation: https://github.com/attractivechaos/klib/blob/master/khash.h
[ Parent
| on HN ]
Re:C++ macros to write a hashtable implementation
by stochastic_monk on Saturday March 10, 2018 @05:06PM
(#16560412)
I've had real world applications where the full program's performance increased by a factor of 10 when switching to khash over std::unordered_map. I've seen papers which have them performing rather comparably, but whenever I've compared the two, khash has always soared over std::unordered_map. I use std::unordered_map for typical, average use cases (where speed doesn't matter as much and I'm feeling lazy), but khash for inner loops/core functionality.
I wonder if part of the reason is that, by nature of the standard, std::unordered_map has to resolve its collisions by linear chaining, while khash is able to use quadratic probing.
Re:C++ macros to write a hashtable implementation
by CyberDildonics on Saturday March 10, 2018 @05:24PM
(#16560481)
The standard dictates performance characteristics that imply the use of buckets, so there is more pointer hopping. A hash map that uses flat memory will end up being better. I would guess robin hood hashing + flat memory would be one of the most competitive techniques.
Re:C++ macros to write a hashtable implementation
by maxlybbert on Saturday March 10, 2018 @08:55PM
(#16561281)
On top of the performance guarantees, the API explicitly mentions buckets (e.g., http://en.cppreference.com/w/cpp/container/unordered_map/max... , http://en.cppreference.com/w/cpp/container/unordered_map/buc... ).
Re:C++ macros to write a hashtable implementation
by stochastic_monk on Sunday March 11, 2018 @02:24PM
(#16564115)
Well, even khash uses buckets. It’s just that you skip over your “correct” bucket for insertion if it’s full when using open addressing.
Re:C++ macros to write a hashtable implementation
by ComputerGuru on Saturday March 10, 2018 @08:14PM
(#16561128)
Fwiw quadratic hashing was only added to khash in 2013. Depending on when you first tested it, that may not be the reason it was faster.
Re:C++ macros to write a hashtable implementation
by stochastic_monk on Saturday March 10, 2018 @10:07PM
(#16561507)
Thanks for the tip. This testing was 2015, so it would have been after that point. You're right, though -- even linear probing would probably have better locality than chaining.