Show HN: Simple Hash Table Implementation for C
github.com
github.com
Performance-wise, my single-threaded test runs about 6 times faster than the equivalent JS, which puts it in the C ballpark.
I was really pleased about the performance under multi-threading. With 4+ threads, it's near to being 4 times faster, and the bucket lock only spins occasionally (prints a few '.' but still works).
I'll check out sys/queue.h
Suddenly, the C preprocessor doesn't seem quite as far distant from C++ templates as I'd thought...
Also worth checking out is uthash[1], which has been around for ever. It's a single header file include, full featured, and pretty bulletproof.
Definitely interested to see how other people handle some of issues with threading, hash-collisions etc., and also how to best build code that'll run out of a single header file.
Thanks.
* The copystring() function looks like you re-implemented strdup() from string.h.
* The call to malloc() followed by a call to memset() to zero it can be replaced with a call to calloc(). This is faster on some platforms, and makes for cleaner code.
https://github.com/troydhanson/uthash
You can compare performance with it and other C hash table implementations.
I'll just add, any sane implementation of make should already define $(CC) for you.
If you're dealing with integers or strings on a key-by-key basis and can statically predict as a function of key whether it's an integer or a string, you shouldn't be using a hash table, you should be using a struct or two hash tables, one with the integers and one with the strings.
If you're dealing with integers or strings on a key-by-key basis and can't statically predict whether it's an integer or string, you'll need some mechanism for ascertaining that and the best way is for the hash table to store and expose that information, because you'd be storing it elsewhere anyway. You could expose the underlying tagged union.
If you're not dealing with integers or strings on a key-by-key basis (I guess you're dealing it on a table-by-table basis, which is a more likely usage, I hope), you just want to avoid duplicating code. There's little harm in having a tag and doing a run-time check anyway. Also, if you don't want to do that, you can make one underlying implementation, and then wrap it in types "struct hash_string_int" and "struct hash_string_string," and the like, and permit only the right kind of methods to be called on the right structure type.
It's never the right thing to do to make needlessly risky code -- if that's how you like to code, then you shouldn't be writing C.