Letters to the Editor

Multithreaded Programming

'Double-checked locking: Clever, but broken'

Brian Goetz

Will the use of temporary variables fix double-checked locking?

Brian,

Great article! Your suggested fix is a little harsh and involves changing a lot of my code! So, I was wondering if this is an effective way to sidestep the possible ordering problem of the constructor/allocation items: Use a temporary variable that is allocated on a thread stack for the resource's allocation and initialization. Then assign the resource with the temporary variable's value:

class SomeClass { 
         private Resource resource = null; 
         public Resource getResource() { 
                 if (resource == null) { 
                 synchronized { 
                         if (resource == null) {
                                 
Resource temp_constructed_resource = new
Resource()
   //At this point:
                                  
   //1. the temp resource is allocated, *and* constructed
                                 
   //2. the resource field is still null
                                 
resource = temp_constructed_resource;
   //At this point:
             
   //1. the resource field is now set and constructed.
                         }
                 } 
         } 
         return resource; 
}        

That is a fairly trivial addition to double-checked locking, but it seems that it would ensure integrity of the resource. The maintenance of the as-if-serial semantic seems much more assured.

Sean Woodward

Sean, Yes, my fix is harsh. And it's worth pointing out that your code

might

work without it; few JVMs actually implement the Java Memory Model correctly. But do you want to rely on that? Your suggested workaround is a common one, but it doesn't work. The compiler can freely optimize:

   Resource temp = new Resource();
   resource = temp;

to

   resource = new Resource();

without violating as-if-serial semantics. Now you're back in the same boat. Even in the absence of compiler optimization, bad things can happen. Let's say the constructor for the resource sets fields

a

and

b

of

Resource

to some values. The JVM inlines the constructor, so the above becomes:

   t = malloc(sizeof(Resource))
   t.a = something
   t.b = something
   resource = t

On a superscalar processor, initialization of

t.b

and

resource

might execute simultaneously, but the assignment of

t.b

could take longer (because of a cache miss or pipeline stall) and

resource

could be assigned first. A cache could introduce a similar appearance of reordering. None of those reorderings violate as-if-serial semantics, so they are allowed. But it could appear to another thread that things had executed differently. Brian

What about creating a second instance variable?

Brian,

I am a Java developer, but I never realized the subtleties that optimizations could cause. I enjoy a good test of my abilities and took the article as a challenge to find a solution. I am by no means an expert in the workings of microprocessors and optimizing compilers/JITs. However, I have come up with a technique that I would like you to comment on. It involves creating a second instance variable to hold the reference to the singleton. The call to getHelper() still checks to see if the helper instance variable reference is null. If it is, instead of instantiating a new Helper object, it calls a second synchronized method, getSingleton(), that has its own null check. That method then instantiates a helper() method and sets the singleton reference to it; the singleton is then returned.

The creation of the singleton object is done isolated within a synchronized class. Based on your article, that would seem to guarantee that only one instance is created. The part I'm unsure about is the possibility of returning a reference to a partially filled-in object. However, the reference return doesn't seem to be a problem either, since that would mean the single synchronized method could return a reference to a partially filled-in object as well.

I have attached a code sample that illustrates my technique:

// Single threaded version
 class Foo {
   private Helper helper = null;
   private Helper singleton = null;
   public Helper getHelper() {
     if (helper == null)
         helper = getSingleton();
     return helper;
     }
   private synchronized Helper getSingleton() {
       if (singleton == null) {
                singleton = new Helper();
            }
            return singleton;
   }
   // other functions and members...
   }

Thanks,

David Wegener

David, The technique you suggest is a variation of one that has been suggested many times before, but unfortunately, it still fails. Inlining

getSingleton()

(which the compiler can and should do) results in:

public Helper getHelper() {
   if (helper == null) {
     synchronized (Helper.class) {
       if (singleton == null)
         singleton = new Helper();
       helper = singleton;
     }
   }
   return helper;
}

Doesn't that look a lot like double-checked locking? You've introduced another variable, which looks like it

should

force the constructor to complete before

helper

is assigned, but it doesn't. The compiler/processor/cache can reorder statements as long as they adhere to as-if-serial semantics; the assignment to

helper

could complete (or appear to complete) before the constructor is finished. And even if you could force the constructor to complete, you're not completing a read barrier before examining

helper

to see if it's null. That could result in stale values of the

Helper

it references. Brian

Synchronized confusion

Brian,

Your article was good, but I still don't understand one thing: the fact that a thread (A) should be able to see a reference created by another thread (B) while the object referenced is still not complete.

Using the example in your article, if thread B creates an instance of SomeObject in a synchronized block -- with the reference variable in local memory -- thread A should not be able to see anything until thread B exits its synchronized block after flushing its local memory to the main memory.

I can't understand what I'm missing.

Hugues Ferland

Hugues, Say there are two threads: A and B. A is inside the synchronized block, has constructed a Resource, and is setting the field 'resource'. B is entering getResource() and executing the check "if (resource == null)". There are three sets of memory to consider: main memory and the local memories of threads A and B. Consider these two scenarios: Before A exits the synch block, data written to A's memory may not be moved to main memory, or it could be moved in an order different than the order in which it was written to A's memory. Also, some values may be written out slowly to main memory. But let's say that the reference to the new Resource is written out to main memory before the constructor finishes, which is certainly possible. If B goes to main memory to examine the reference, it may see the valid value of resource, but not the fields of resource (because it's still being constructed or those fields have not yet been written to main memory). That's bad; it sees a partially constructed Resource. Now, on to your question: You are right -- after A exits the synch block, all the values from A's memory have been flushed to main memory. But B might still see stale values in its own local memory, because it hasn't completed a read barrier that would force it to invalidate its local memory (cache) and refresh it from main memory. Entering a synch block triggers a read barrier. So B could still see stale values of resource's fields, even after A has left the synch block and written its data out to main memory. This is pretty complicated stuff, so don't worry if it wasn't obvious the first time. Synchronized actually has a rather complicated and nonobvious meaning -- unless you have a lot of experience either writing compilers or doing low-level multiprocessor stuff. Brian Goetz

Java Commentary

'Java: It's a good thing'

Erwin Vervaet

Are you sure Java's a good thing?

Erwin,

I am a software developer working on the Java platform, but the market for Java is not good. The situation is not what it was expected to be. What is the future of Java? Will Microsoft's C# beat Java in the market?

AV

AV, I don't think C# will beat Java in general. It might beat Java in the Windows desktop application market eventually, but that's to be expected. Before that occurs, C# must overcome some serious hurdles. C# is 5 years behind Java. Java is available, stable, and ready to be used. C# is still in development, so it will have play catch-up. Also, think back to Java 1.0, which wasn't very useful at the time. C# will probably end up a Windows-only language. Java will still be available for the server side and all other platforms. Further, I think the Java market is very sound at the moment, so I'm not sure why you're doubting Java's current state of affairs. Erwin Vervaet

GUI Framework

'Become a programming Picasso with JHotDraw'

Wolfram Kaiser

Does JModeller follow the Model-View-Controller paradigm?

Wolfram,

I just devoured your article; I commend you on an excellent piece of work.

I am investigating the possibility of building a distributed, collaborative CASE tool, and JHotDraw seems like an ideal fit for my UI requirements. However, I do have one doubt: In the example you provide in the article, I don't think the relationship between ClassFigure and JModellerClass is Model-View-Controller (MVC). I always understood MVC to require a controller to make user-specified modifications to a UI-independent model. Then the model updates the various views using Observer. That is not the case in JModeller.

Take, for example, the creation of a new JModellerClass. You complete that by cloning a ClassFigure, rather than cloning a JModellerClass and having it notify all UI observers so they will create whatever view is required.

Also, consider the block of code beginning at ClassFigure.java:97 in your article. That updates the view and the model simultaneously. Should it just update the model and let the view update via notification? The current code sends a mixed message about MVC -- it is used between drawing and drawing views, but not between models (i.e., JModellerClass) and model views (i.e., ClassFigure).

So, do you have any guidance on how to best achieve total use of MVC with JHotDraw? Does the framework provide any help in this area -- maybe in the form of listeners and notifiers, or some interfaces or base classes from which to inherit my (data) models?

As an aside, it would be nice if JHotDraw used the Command pattern to react to user events; for example, if the user clicks this button, this command is executed. That allows nifty things like record and replay of user activity to aid testing. It also lets random command generation aid in testing.

Mike Hogan

Mike, Thank you for your interest in the article and your useful comments. I agree that JModeller -- and, in fact, JHotDraw -- is not MVC at its purest. In JHotDraw, you manipulate graphical objects in your view with the help of tools -- which partly play the role of a controller. Changes in the view should then be propagated to the model. As you pointed out, you would ideally modify the model that notifies the view of changes. While JHotDraw is not pure in that respect, it still separates model, view, and controller -- thus, I call it MVC. The separation of model, view, and controller is often not very distinct in practice. Unless you define tools that manipulate the model directly, there are no further mechanisms in JHotDraw that you can use out-of-the-box to purify the MVC approach. Java already provides concepts like event notification that you can use to introduce some dependencies in the model and the view. In fact, the relationship between model and view is almost left open in JHotDraw. It could be interesting to investigate how such a relationship/dependency mechanism could be introduced without posing too many restrictions on the model. The Command pattern is already used for some high-level operations, like cut-and-paste, grouping, and deleting, but it could be utilized further. Please have a look at CH.ifa.draw.util.Command. Wolfram Kaiser

Design Patterns

'When is a singleton not a singleton?'

Joshua Fox

Another singleton pitfall to add to the pile

Joshua,

Thanks for the interesting article on singletons. I recently had a related problem. As usual, the problem is obvious in retrospect, but was not obvious enough ahead of time to prevent its occurrence!

I have a multithreaded application with a number of singletons. That short description alone almost gives away the source of the problem. Consider the following code:

Class A

{
   private B b = B.getInstance();
   private static A a;
   private A()
      { // whatever...  }
   public static getInstance()
   {
      if ( a == null )
      {
         a = new A();
      }
      return a;
   }
   public doWork()
   {
      // b is used here
   }
}

Class B

{
   private A a = A.getInstance();
   private static B b;
   private B()
      { // whatever...  }
   public static getInstance()
   {
      if ( b == null )
      {
         b = new B();
      }
      return b;
   }
   public workHard()
   {
      // a is used here
   }
}

The problem is readily apparent. If you try to call A.getInstance(), the constructor A() cannot return without calling B.getInstance(). Likewise, the constructor B() cannot return without calling A.getInstance(). The result is an infinite recursive, which will eventually overflow your stack and crash the program. Of course, the situation can become even more confusing if multiple threads are involved, along with instruction reordering and/or improper synchronization. I had three singletons, so A used B, B used C. I caused the problem when I added a simple feature so that C used A. Surprise!

Of course, the fix is simple: singletons should not hold instance variables that are references to other singletons. The fixed version is as follows:

Class A

{
   private static A a;
   private A()
      { // whatever...  }
   public static getInstance()
   {
      if ( a == null )
      {
         a = new A();
      }
      return a;
   }
   public doWork()
   {
      B b = B.getInstance();
      // b is used here
   }
}

Class B

{
   private static B b;
   private B()
      { // whatever...  }
   public static getInstance()
   {
      if ( b == null )
      {
         b = new B();
      }
      return b;
   }
   public workHard()
   {
      A a = A.getInstance();
      // a is used here
   }
}

The instance variables were only present in the first place so I could have a convenient reference available for use in the methods doWork(), workHard(), etc. It doesn't cost much in either code or execution time to convert the instance variables to method variables, which breaks the infinite recursion cycle in the singleton constructors.

So that is one more item to add to the list of things one shouldn't do.

Alan Thompson

Alan, Thanks for that great example. Yes, I can see the problem. Perhaps that relates to the principle of not replicating state in separate places. The Singleton class or other singleton factory is the single point of access to the singleton; you should always rely on it to produce the singleton reference. Who knows, the factory may be giving you different objects every time you call it, even if, from your perspective, it is the same object (as can happen with entity Enterprise JavaBeans). The trouble is that every time you want to call the method foobar(), you can end up with wordy code like SingletonFactory().getInstance().getSingletonInstance().foobar() (when the SingletonFactory is itself a singleton), but I think it's worth it. Joshua Fox

XML Tutorial

'XML document processing in Java using XPath and XSLT'

André Tost

What is the purpose of locations sets?

André,

Currently I am working on XPath. I have gone through some issues on XPointer. The primary difference between XPointer and XPath is that XPointer refers to location sets, not node sets. A location is either a node, a point, or a range. The tests and predicates from XPath are also extended to handle points and ranges.

I don't understand the purpose of location sets. As I understand it, XPath will solve most of the problems. Please enlighten me. N.V. Sairam

N.V., Those are good questions. Clearly, there are differences between XPath and XPointer, as you mentioned. XPointer is built on top of XPath, but allows you to select areas of an XML document that a pure XPath could not address. That is where the ranges come in. A range, for example, can be part of a text element, like a substring. XPath cannot address such a substring; it can only point to an entire node. Now, given all that, the XPointer standard is not finalized yet, and I am not sure how widely implemented it is. If you can solve all your problems with XPath, I see nothing wrong with using it. In fact, you could argue about the value of being able to work with ranges and points. You should usually be able to define the structure of the target XML document so that XPath will always suffice. Finally, since XPointer is built on top of XPath, you're set for the future should XPointer become necessary for you. Hope this helps. André Tost

Java Servlets

'Take control of the servlet environment'

Part 1: Invisibly extend the functionality of the servlet API

Part 2: Alternatives to servlet session management

Part 3: Beware of the cookie monster

Thomas Davis and Craig Walker

Thomas or Craig,

I was wondering why setting a cookie on the top-level domain -- using Cookie.setDomain() -- is not a good solution. Why shouldn't the cookie be set for the whole of the rudiment.net domain, thereby ensuring that all its subdomains see the cookie?

Sudhakar

Sudhakar, You are correct to think that the

Cookie.setDomain()

record would be a good solution for the cookie domain problem we encountered. The problem is that a cookie's domain attribute is optional, so the functionality required for the

setDomain()

and

getDomain()

methods is not necessarily implemented by the Web server, browser, or servlet engine. We came across that problem during our development (the

setDomain()

and

getDomain()

methods simply didn't do anything!), so we came up with the idea of prepending the domain to the name of the cookie as a workaround. For your reference, we are using:

  • Allaire JRun 2.3.3
  • Microsoft IIS 4
  • MS Internet Explorer 5 / Netscape 4

If you come across a combination of servers and clients that support cookie domains, please let us know. Craig Walker

Beginner Java

'Calculating Java dates'

Robert Nielsen

No daylight savings in Java

Robert,

Your article describing date manipulations was interesting, but it left out a real humdinger of a bug. If you're not in the US, the standard Date in JDK 1.1 and 1.2 doesn't understand daylight savings time. That can put your times (and dates, around midnight) off by one hour. The only solution I have found is to initialize the DateFormat with a SimpleTimeZone thus:

   // set up date format
   // Timezone with zero offset from GMT
   SimpleTimeZone tz = new SimpleTimeZone(0, "GMT");
   // Offset by one hour on the last sunday in March at 2:00am, clocks
go back one hour
   tz.setStartRule(Calendar.MARCH, -1, Calendar.SUNDAY, 2*60*60*1000);
   // Change clocks back on the last sunday in October at 2:00am, clocks
go forward (i.e. GMT again).
   tz.setEndRule(Calendar.OCTOBER, -1, Calendar.SUNDAY, 2*60*60*1000);
   DateFormat df = DateFormat.getDateTimeInstance(DateFormat.SHORT,
DateFormat.SHORT);
   df.setTimeZone(tz);

I don't know if this is fixed in JDK 1.3 yet.

Nick

Nick, Very interesting. I will have to look closely at the point you raised. I found an error in Sun's code in the version of Java (1.2.1) I was using. It seems that if you add months to dates that are B.C., the year actually goes backward. Sun's Website indicated that the bug had been fixed in a later 1.2 version. I think it is easier to make mistakes in computer code that deals with dates and time than in code that deals with other stuff. Whether that is just my impression or actually the case, I don't know, but your example supports my suspicions. Robert Nielsen