5 ms·

Show HN: Simple Hash Table Implementation for C

42 points by watmough 11y ago

watmough 11y ago
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).
pjscott 11y ago
Looks fun. A couple of minor comments: * 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.
- infradig 11y ago
  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.
  - cperciva 11y ago
    If you're not running on POSIX.1-2001, you're not likely to have pthreads or GCC builtin functions.
    - infradig 11y ago
      If you specify -std=c11 you won't get strdup().
- watmough 11y ago
  Cool, thanks for the comments.
necessity 11y ago
I use uthash: https://github.com/troydhanson/uthash https://github.com/troydhanson/uthash You can compare performance with it and other C hash table implementations.
AntiRush 11y ago
Cool! Hashtables make for a fun project, to be sure. 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/ https://troydhanson.github.io/uthash/
- watmough 11y ago
  Ahhh, thanks for that. I will take a look. 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.
  - watmough 11y ago
    Yes, there's definitely some stuff in there I hadn't thought of like how to handle strings as char[xxx] vs string ptrs. Thanks.
- jasonjei 11y ago
  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.
aninteger 11y ago
I'm currently using https://github.com/attractivechaos/klib/blob/master/khash.h 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
- watmough 11y ago
  Yeah thanks, I'm on OS X, and stuff like timersub is coded in sys/time.h I'll check out sys/queue.h
  - watmough 11y ago
    Thanks a bunch for that, khash looks really interesting, and it does what I kinda wanted to do, but didn't really realize was possible. Suddenly, the C preprocessor doesn't seem quite as far distant from C++ templates as I'd thought...
ryanmarsh 11y ago
I've never implemented one but the origin of Ruby's won me over with nostalgia. https://github.com/ruby/ruby/blob/trunk/include/ruby/st.h https://github.com/ruby/ruby/blob/trunk/include/ruby/st.h
AaronIG 11y ago
Nice. I'll just add, any sane implementation of make should already define $(CC) for you.
- watmough 11y ago
  There's some issues on my copy of OS X with getting a working gdb, which I needed on something else I was working on ... hence the manual def.
dopeboy 11y ago
Very cool. Reminds me of my grad school days when I was implementing cuckoo hashing on a cell processor.
roye 11y ago
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?
accatyyc 11y ago
Neat looking code! I've been looking for something like this. Will try it! I find it a lot more readable than the usual "header-libs"
perdunov 11y ago
Would be nice to see a comparison with std::unordered_map<>, both on the performance and usability side.
SamReidHughes 11y ago
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 *.
- cperciva 11y ago
  Not really. If you don't know if you're dealing with integers or strings, you shouldn't be writing C anyway.
  - deleted 11y ago
    [deleted]
  - SamReidHughes 11y ago
    [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.
joepvd 11y ago
That is an excellent documentation in the README. Even though I do not know C, I immediately have a clue of how to use this lib.
tapirl 11y ago
repost: http://www.reddit.com/r/programming/comments/3692g7/simple_hash_table_implementation_for_c/ http://www.reddit.com/r/programming/comments/3692g7/simple_h...
agottem 11y ago
If you're looking for zero cost c containers, I'd recommend an approach which uses intrusive data structures. http://www.agottem.com/libcontainer http://www.agottem.com/libcontainer has one such implementation of common container types.

42 points by watmough 11y ago

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).

pjscott 11y ago

Looks fun. A couple of minor comments: * 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.

infradig 11y ago
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.
- cperciva 11y ago
  If you're not running on POSIX.1-2001, you're not likely to have pthreads or GCC builtin functions.
  - infradig 11y ago
    If you specify -std=c11 you won't get strdup().
watmough 11y ago
Cool, thanks for the comments.

necessity 11y ago

I use uthash: https://github.com/troydhanson/uthash https://github.com/troydhanson/uthash You can compare performance with it and other C hash table implementations.

AntiRush 11y ago

Cool! Hashtables make for a fun project, to be sure. 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/ https://troydhanson.github.io/uthash/

watmough 11y ago
Ahhh, thanks for that. I will take a look. 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.
- watmough 11y ago
  Yes, there's definitely some stuff in there I hadn't thought of like how to handle strings as char[xxx] vs string ptrs. Thanks.
jasonjei 11y ago
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.

aninteger 11y ago

I'm currently using https://github.com/attractivechaos/klib/blob/master/khash.h 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

watmough 11y ago
Yeah thanks, I'm on OS X, and stuff like timersub is coded in sys/time.h I'll check out sys/queue.h
- watmough 11y ago
  Thanks a bunch for that, khash looks really interesting, and it does what I kinda wanted to do, but didn't really realize was possible. Suddenly, the C preprocessor doesn't seem quite as far distant from C++ templates as I'd thought...

ryanmarsh 11y ago

I've never implemented one but the origin of Ruby's won me over with nostalgia. https://github.com/ruby/ruby/blob/trunk/include/ruby/st.h https://github.com/ruby/ruby/blob/trunk/include/ruby/st.h

AaronIG 11y ago

Nice. I'll just add, any sane implementation of make should already define $(CC) for you.

watmough 11y ago
There's some issues on my copy of OS X with getting a working gdb, which I needed on something else I was working on ... hence the manual def.

dopeboy 11y ago

Very cool. Reminds me of my grad school days when I was implementing cuckoo hashing on a cell processor.

roye 11y ago

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?

accatyyc 11y ago

Neat looking code! I've been looking for something like this. Will try it! I find it a lot more readable than the usual "header-libs"

perdunov 11y ago

Would be nice to see a comparison with std::unordered_map<>, both on the performance and usability side.

SamReidHughes 11y ago

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 *.

cperciva 11y ago
Not really. If you don't know if you're dealing with integers or strings, you shouldn't be writing C anyway.
- deleted 11y ago
  [deleted]
- SamReidHughes 11y ago
  [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.

joepvd 11y ago

That is an excellent documentation in the README. Even though I do not know C, I immediately have a clue of how to use this lib.

tapirl 11y ago

repost: http://www.reddit.com/r/programming/comments/3692g7/simple_hash_table_implementation_for_c/ http://www.reddit.com/r/programming/comments/3692g7/simple_h...

agottem 11y ago

If you're looking for zero cost c containers, I'd recommend an approach which uses intrusive data structures. http://www.agottem.com/libcontainer http://www.agottem.com/libcontainer has one such implementation of common container types.