Hacker News Reader

Comment by stevemk14ebr | Hacker News Reader

Neat/Funny i guess but not really technically impressive. They took normal C++ code and hid it behind a macro with some names. The actual implementation isn't even there, Hashtable::hash and the 'table' member for example.

I was totally hoping for some fancy templates and macro tricks to compile time gen all the code for a working hashtable implementation.

View on HN

For some _real_ CPP abuse, check out klib’s hash table implementation: https://github.com/attractivechaos/klib/blob/master/khash.h

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.

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.

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.

Reply on news.ycombinator.com