I recently stumbled across a google tech talk video by a man named Cliff Click Jr. He works for a company named Azul, and he has a blog here This tech talk was all about a lock-free hash table that he’d invented for Azul. The video is here
Lock free hash table? Heck yeah I want a lock free hash table!
Sadly, Cliff’s implementation is Java-only, and relies on some Java memory semantics, but it’s on sourceforge if anyone’s interested.
So, as I began reading up on the subject, I discovered that he’s not the only one interested. In fact, there’s another fellow who has a C-based library here. Only problem? IT’S NOT ACTUALLY LOCK FREE!!! At least, not yet. At the moment it’s a pthread/mutex-based hash table that happens to have all the pthreads stuff ifdef’d out (joy). There are other people out there who talk about it. A fellow from IBM named Maged M. Michael has a paper about how to do lock-free hash tables, and he even has a patent on his particular method, but no implementations appear to be available. Chris Purcell wrote a paper on the topic, which contains pseudocode, but yet again, no implementation.
So it would appear that if I want a lock-free hash table, I’m going to have to implement it myself. But boy, it gets me giddy just thinking about it. :) Pthreads, you’re going down!
Comments (3)
The problem you are up against is the lack of a memory model for C. Hence any C code you write will only be guaranteed to work on such machines (and compilers) and you verify yourself. A different machine & C compiler... and all bets are off.
E.g., IA64's loose memory model will surely break any lock-free hashtable without lots of memory fences... which are utterly redundant (and very slow!) on a more conservative X86 or Sparc.
Same with the compiler: what works with "gcc -O2" on your desktop might utterly fail with MSC's compiler. There's no way in the C language to express the required memory orderings. Even library calls do not make ordering guarantees (although in practice a slow enough call will simply end up taking so long that all memory ops settle out).
Good luck!
Cliff
Posted by Cliff Click | September 20, 2007 4:29 PM
Posted on September 20, 2007 16:29
Well, certainly I can't do it in pure C—I'll need assembly for each platform to do the CAS, which will obviously make it unworkable on some platform/compiler combinations (e.g. Intel's compiler on Xeon cpu's doesn't accept hand-coded assembly), but I don't quite understand what you mean about the memory model (forgive me, I'm hardly a veteran in the lock-free field). As long as we have a CAS, implemented however, we can get a static-size lock-free hash table, which I think is the first step. Right? Without worrying about resizing (for the moment), I don't understand how this will be a problem, though perhaps I need to review your tech-talk again.
Posted by Kyle Wheeler | September 21, 2007 11:38 AM
Posted on September 21, 2007 11:38
I just found this page while searching for a lock-free hash table and would like to bring this to your attention: http://code.google.com/p/nbds/ and some discussion about it: http://groups.google.com/group/comp.programming.threads/browse_thread/thread/702aedc141b34fa1
Posted by Ralph Mengen | September 3, 2010 3:36 PM
Posted on September 3, 2010 15:36