C++ macros to write a hashtable implementation
cs.mcgill.ca
C++ macros to write a hashtable implementation
1–10 of 15 posts
Re: C++ macros to write a hashtable implementation
#2Neat/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.
Re: C++ macros to write a hashtable implementation
#3Neat/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.
For some _real_ CPP abuse, check out klib’s hash table implementation: https://github.com/attractivechaos/klib/blob/master/khash.h
Re: C++ macros to write a hashtable implementation
#4How is this a hashtable implementation?
Re: C++ macros to write a hashtable implementation
#5Neat/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.
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.
Re: C++ macros to write a hashtable implementation
#6Earlier quoted context omitted.
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…
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
#7How is this a hashtable implementation?
int 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_
Re: C++ macros to write a hashtable implementation
#8I've happily used uthash [1] in embedded-system software written in C and C++.
Re: C++ macros to write a hashtable implementation
#9Eveything could be written under name "RING". Then you would not need TO/To/tO
Re: C++ macros to write a hashtable implementation
#10Earlier quoted context omitted.
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…
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.