Thursday, March 6, 2008

Is synchronisation expensive? Is that the right question?

Sometimes I find that I come across a lot of pieces of information which together end up pointing in a certain direction. If you've ever read "The celestine prophecy" you might term this "synchronicity", which, by coincidence (or synchronicity), fits very well with the current topic :-).

The trigger point for this post was that a colleague of mine got into a discussion with a speaker at jFokus about what happens when you "synchronize" (the speaker even blogged a bit about it). Now I know that my colleague usually knows what he is talking about, so what is it? Is synchronization expensive or not?

When I asked my colleague he said that grabbing an uncontended lock is on the order of 10-8 seconds. As I had been benchmarking a hash set implementation, I had everything set up to test (and confirm) this. On my machine the overhead for grabbing an uncontended lock (putting the synchronized keyword on a method) was 70ns. Now that sounds pretty cheap, doesn't it? (I have subsequently found out that there are strange issues when running benchmarks. Running again in a supposedly more correct way, the cost of synchrnization would seem to be more like 7ns, or rather, with other noise involved, between 1 and 30, mostly under 10. So my colleague was dead on.)

Well, considering that I'd just been very happy about reducing the execution time of the method from 30ns to 20ns, the prospect of adding a 70ns overhead was not appealing. So synchronization is expensive, then?

Turning it around again, how much does it cost you to get stale data in some threads (the data may actually never be updated for some threads)? How much does it cost you if your object gets into an inconsistent state? In that perspective synchronization is usually very cheap.

Swing tries to do without synchronization by mandating that all access to display state needs to be done from the EDT. I sometimes see this expressed as all modifications need to be done on the EDT, but because how the java memory model publishes modifications, I am fairly sure that even querying the state of components needs to be done on the EDT. I'm beginning to think that the Swing threading model causes a viral spread of things to be done on the EDT which can only be broken by having synchronization at some point. This model is perhaps so subtly difficult to handle that it should be considered broken.The conclusion must be that you have to do what you have to do to protect yourself against the bad effects of unprotected access to shared mutable state and asking whether synchronization is expensive does not necessarily lead you in the right direction. A better question to ask would be "Can I do this in some other way than by accessing shared mutable state?"

Accessing shared mutable state is really the issue to look at (and where my synchronicity is leading me) and it is fraught with more dangers than just avoiding race conditions. Spot the bug (and I don't mean the obvious one that the access to lineNumber isn't protected):

final int[] lineNumber = new int[1];
while (in.hasNextLine())
{
final String line = in.nextLine();
lineNumber[0]++;
EventQueue.invokeLater(new Runnable()
{
public void run()
{
statusLine.setText("" + lineNumber[0]);
textArea.append(line);
textArea.append("\n");
}
});
}
(Background to this example). An example of avoiding access to shared mutable state can be found in my first blog post.

1 comment:

Daniel Spiewak said...

The bug is that lineNumber[0] may not necessarily be at the proper increment when invokeLater is invoked (because it is non-blocking). Assuming this sort of algorithm is *absolutely* necessary, there are two solutions. Number one, create a final field within the while scope which is assigned to the value of the counter on each loop. Alternatively, invokeAndWait may be used. Stylistically, I tend to prefer the final inner field, but either will work.