C++ macros to write a hashtable implementation (opens in new tab)

(cs.mcgill.ca)

58 pointsmohamedmansour8y ago14 comments

14 comments

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.

Xophmeister8y ago

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

stochastic_monk8y ago

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.

2 more replies

mkempe8y ago

I've happily used uthash [1] in embedded-system software written in C and C++.

[1] https://troydhanson.github.io/uthash/

gowld8y ago

Pale imitation of http://www.underhanded-c.org/ and https://www.ioccc.org/ (Obfuscated C Competition) where you find the true rings of power.

altaibayar8y ago

Eveything could be written under name "RING". Then you would not need TO/To/tO

khc8y ago

How is this a hashtable implementation?

tytytytytytytyt8y ago

It's not, if you can tell the difference between implementing something and using/instantiating something.

stevemk14ebr8y ago

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_

j / k navigate · click thread line to collapse

14 comments

stevemk14ebr8y ago

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

Xophmeister8y ago

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

stochastic_monk8y ago

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.

2 more replies

mkempe8y ago

I've happily used uthash [1] in embedded-system software written in C and C++.

[1] https://troydhanson.github.io/uthash/

gowld8y ago

Pale imitation of http://www.underhanded-c.org/ and https://www.ioccc.org/ (Obfuscated C Competition) where you find the true rings of power.

altaibayar8y ago

Eveything could be written under name "RING". Then you would not need TO/To/tO

khc8y ago

How is this a hashtable implementation?

tytytytytytytyt8y ago

It's not, if you can tell the difference between implementing something and using/instantiating something.

stevemk14ebr8y ago

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_

j / k navigate · click thread line to collapse