Java Concurrency (&c)

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

Okay, so I lied about the contents of my next post. I bet no one even notices. Anyone even reading these? Yeah, right. I was asked a question about fairness. The notion of fairness is one where there are some number of individual entities trying to make progress (in our case, threads), and there is some level of guarantee that this will actually happen. Java has no meaningful fairness guarantee . A Java virtual machine is allowed to let a thread hog all of the CPU time. If I have: Thread 1: while (true); Thread 2: System.out.println("Hi there!"); There is no guarantee that Thread 2 will actually ever print its message. This is so that Java implementors can create cooperative implementations, where context switching only happens when Thread.yield is called, or when blocking occurs. (In point of fact, this applies almost exclusively to the Oracle Java server . The popular VM implementations from Sun and IBM are preemptive.) You could even have a wait loop: Thread 1: wh...

Another question from a viewer. We have this code: class C {   private int x;   public C(int v) {     this.x = v;   }   public synchronized int get() {     return this.x;   }   public synchronized void set(int v) {     this.x = v;   } } (For the actual question as it was worded, the short answer is, "yes") The question was one I get a lot. He asked how one thread can safely read the initial write of v to x. That is to say, if we have: Thread 1: globalRef = new C(5); Thread 2: C ref = globalRef; if (ref != null) {   int r1 = ref.x; } How can we change this code to guarantee that the read in Thread 2 will see the value 5 for x (assuming that ref is not null)? Let's back up for a minute, and talk about why, in the code as written, the read in Thread 2 will not see the value 5 for x . Under the Java memory model, for one thread to be guaranteed ...

The slides from the JMM talk are available here for people's perusal . Enjoy!

A question from a viewer. In my talk, I had a class that looked like this: class Future {  private volatile boolean ready;  private Obj data;  ...  public synchronized void setOnce(Obj o) {   if (ready) throw ...;   data = o;   ready = true;  }  public Object get() {   if (!ready)    return null;   return data;  } } The setOnce method is executed by one thread, and get is executed by another. The point of this example is to examine what difference the volatile modifier on ready makes. In this case, if ready is not marked volatile , the compiler can reorder the writes to data and ready . This has the result that the thread that invokes get can see the value true when it reads ready , even if data has not been set yet. Messy. The questioner asked why setOnce is synchronized. This is somewhat orthogonal to the example, which is why I didn't mention it in the talk. However, I...

This fellow is rather handsome, dashing and well-informed . If you would like a primer on the Java memory model, this is a good place to start. I was running out of time toward the end, though, so the last 15 minutes may be a little rushed. Perhaps I'll do a two-part followup at some point. One thing I forgot to say, at the very beginning: The Java memory model defines how threads interact through memory. That's why it's called the Java memory model. It has nothing to do with garbage collection or the object model (except where multithreading is important to those things). If the mood strikes, please feel free to ask questions about the memory model, or anything I said in the talk. I put a note in the talk to ask questions at: http://jeremymanson.blogspot.com/2007/03/jmm-questions-go-here.html .

It is important to read the documentation. Lots of people don't seem to do this, and they get bitten by it. The iterator for java.util.HashSet is documented as follows: Returns an iterator over the elements in this set. The elements are returned in no particular order. Of course, I've now seen code that ignores this, so I thought I would draw a few underlines for the kind of folks who miss it. I wish to state for the record that I did not write this code . It turns out that HashSets (and HashMaps) don't just use the user-defined hashCode as the hash value for objects they are passed. They rehash the number that method returns with their own hash function, to defend against poor quality hash functions. This makes a lot of sense, as many people write bad hash functions. Anyway, this means that when they change this function, objects will hash to different places. Then, when iterators visit these items, they will be visited in a different order. I wouldn't be posting...