How is this a hashtable implementation?
It's not, if you can tell the difference between implementing something and using/instantiating something.
C++ macros to write a hashtable implementation
11–15 of 15 posts
Re: C++ macros to write a hashtable implementation
#12Pale imitation of http://www.underhanded-c.org/
and https://www.ioccc.org/ (Obfuscated C Competition)
where you find the true rings of power.
Re: C++ macros to write a hashtable implementation
#13Earlier quoted context omitted.
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…
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.
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
#14Earlier quoted context omitted.
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…
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.
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.
Re: C++ macros to write a hashtable implementation
#15Earlier quoted context omitted.
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.
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... ).
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.