Lock-Free Hash Tables

I forgot to post about this at the time. Cliff Click gave a talk about his lock-free hashtable at Google; it is definitely worth a peek. Available here.

There is a very funny thread on the concurrency-interest mailing list this week about "lock-free mania". Apparently, software engineers are going to start choosing "trendy" lock-free data structures for no valid reason, resulting in lots of fragile code. In related news, recursion, memoization and every data structure more complicated than a hash table just started laughing their arses off. B+ Trees were quoted as saying, "I can't count the number of times some database-implementing hack has thrown together a cheap and poorly tested implementation of me because he thinks it is 'trendy' to put together an indexing mechanism. Oh, wait. Zero is a number. Never mind!"

In all seriousness, I have actually stopped someone from using a lock-free algorithm where a lock would have been more readable, and had the same performance impact. So, as with every other programming technique on the planet, you have to be careful about where you use it.

Personally, I see the complexity of lock-free algorithms as a hack that just needs to hold us over until hardware atomicity is supported for more than 1 word at a time. I actually asked Cliff about this in the talk, because he controls his hardware (I start laughing, he stares at me for a bit, and then I ask that question, which was not the question I was imagining.) He only did it in the way he did because he wanted his hash table to be useful for other Java implementations. That's community spirit for you!

Comments

Double Checked Locking

I still get a lot of questions about whether double-checked locking works in Java, and I should probably post something to clear it up. And I'll plug Josh Bloch's new book, too. Double Checked Locking is this idiom: // Broken -- Do Not Use! class Foo { private Helper helper = null; public Helper getHelper() { if (helper == null) { synchronized(this) { if (helper == null) { helper = new Helper(); } } } return helper; } The point of this code is to avoid synchronization when the object has already been constructed. This code doesn't work in Java. The basic principle is that compiler transformations (this includes the JIT, which is the optimizer that the JVM uses...

What Volatile Means in Java

Today, I'm going to talk about what volatile means in Java. I've sort-of covered this in other posts, such as my posting on the ++ operator , my post on double-checked locking and the like, but I've never really addressed it directly. First, you have to understand a little something about the Java memory model. I've struggled a bit over the years to explain it briefly and well. As of today, the best way I can think of to describe it is if you imagine it this way: Each thread in Java takes place in a separate memory space (this is clearly untrue, so bear with me on this one). You need to use special mechanisms to guarantee that communication happens between these threads, as you would on a message passing system. Memory writes that happen in one thread can "leak through" and be seen by another thread, but this is by no means guaranteed. Without explicit communication, you can't guarantee which writes get seen by other threads, or even the order in whic...

Atomicity, Visibility and Ordering

(Note: I've cribbed this from my doctoral dissertation. I tried to edit it heavily to ease up on the mangled academic syntax required by thesis committees, but I may have missed some / badly edited in places. Let me know if there is something confusingly written or just plain confusing, and I'll try to untangle it.) There are these three concepts, you see. And they are fundamental to correct concurrent programming. When a concurrent program is not correctly written, the errors tend to fall into one of the three categories: atomicity , visibility , or ordering . Atomicity deals with which actions and sets of actions have indivisible effects. This is the aspect of concurrency most familiar to programmers: it is usually thought of in terms of mutual exclusion. Visibility determines when the effects of one thread can be seen by another. Ordering determines when actions in one thread can be seen to occur out of order with respect to another. Let's talk about t...

Java Concurrency (&c)

Search This Blog