I know this is pretty simple, but I never ever did at any point implement a hash table, just went more or less straight to programming in Assembler in a semi-mature system, then to MFC on Windows since about 1998.
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).
* 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.
Because strdup() is not standard enough to rely on. You have to test all sorts of magic values to pull it in, then you have define it yourself for those cases where it isn't defined. Why bother? Just write you own equivalent.
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.
It's funny, because while I remember I was forced to implement one back in my CS days, I questioned the point and practicality of it (as I did with other things like in the OS class). But I am thankful now for having been put through the exercise (as well as competitive grading, based on the average runtime with random hashtables constructed). Knowing how a hash table is implemented allows you to understand why it's an efficient structure.
I'm currently using https://github.com/attractivechaos/klib/blob/master/khash.h in professional projects. I know it's pretty much full of macro "magic" (well it's readable so not really..) so that makes some people scared. I really like these header file "libraries" and am also a big fan of BSD's sys/queue.h
It seems like all the hash implementations I've seen have an insertion rate of ~Million/sec. I wonder if it's possible to get at least an order of magnitude faster (single threaded). Are we close to the input string parsing at this rate? Would sorting/caching help a lot?
It is bad that you can insert an integer and then if you try to read the value back as a string, it'll happily interpret the integer value as a char *.
[First of all, what's the deal with the anonymous upvoters bringing my previous comment, which is against the guidelines for Show HN, back into the black? Bad comments should go to the hell where they belong!]
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.
If you're looking for zero cost c containers, I'd recommend an approach which uses intrusive data structures. http://www.agottem.com/libcontainer has one such implementation of common container types.
28 comments
[ 3.1 ms ] story [ 59.5 ms ] threadPerformance-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).
* 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.
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.
[1]https://troydhanson.github.io/uthash/
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.
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...
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.