« Superscript-One | Main | Come *on*, Apple »

I wish I had a C-based lock-free hash table...

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!


TrackBack URL for this entry:

Comments (3)

Cliff Click:

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!

Kyle Wheeler:

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.

Ralph Mengen:

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

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


This page contains a single entry from the blog posted on September 20, 2007 2:46 PM.

The previous post in this blog was Superscript-One.

The next post in this blog is Come *on*, Apple.

Many more can be found on the main index page or by looking through the archives.

Creative Commons License
This weblog is licensed under a Creative Commons License.
Powered by
Movable Type 3.34