4 ms·
C++ macros to write a hashtable implementation
- stevemk14ebr 9y agoNeat/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.
- Xophmeister 9y agoFor some _real_ CPP abuse, check out klib’s hash table implementation: https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h
- stochastic_monk 9y agoI'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.
- CyberDildonics 9y agoThe 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.
- maxlybbert 9y agoOn top of the performance guarantees, the API explicitly mentions buckets (e.g., http://en.cppreference.com/w/cpp/container/unordered_map/max_bucket_count http://en.cppreference.com/w/cpp/container/unordered_map/max... , http://en.cppreference.com/w/cpp/container/unordered_map/bucket http://en.cppreference.com/w/cpp/container/unordered_map/buc... ).
- stochastic_monk 9y agoWell, even khash uses buckets. It’s just that you skip over your “correct” bucket for insertion if it’s full when using open addressing.
- ComputerGuru 9y agoFwiw 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.
- stochastic_monk 9y agoThanks 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.
- khc 9y agoHow is this a hashtable implementation?
- stevemk14ebr 9y agoint i = HashTable::hash(r) table[i].push_back(r); they hash the data and use that as an index. So by def. That said it's pretty bare and missing _ALOT_
- tytytytytytytyt 9y agoIt's not, if you can tell the difference between implementing something and using/instantiating something.
- mkempe 9y agoI've happily used uthash [1] in embedded-system software written in C and C++. [1] https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/
- altaibayar 9y agoEveything could be written under name "RING". Then you would not need TO/To/tO
- gowld 9y agoPale imitation of http://www.underhanded-c.org/ http://www.underhanded-c.org/ and https://www.ioccc.org/ https://www.ioccc.org/ (Obfuscated C Competition) where you find the true rings of power.