Double-Check Idiom using booleans

Question

Take the following java code:

public class SomeClass {
  private boolean initialized = false;
  private final List<String> someList; 

  public SomeClass() {
    someList = new ConcurrentLinkedQueue<String>();
  }

  public void doSomeProcessing() {
    // do some stuff...
    // check if the list has been initialized
    if (!initialized) {
      synchronized(this) {
        if (!initialized) {
          // invoke a webservice that takes a lot of time
          final List<String> wsResult = invokeWebService();
          someList.addAll(wsResult);
          initialized = true;
        }
      } 
    }
    // list is initialized        
    for (final String s : someList) {
      // do more stuff...
    }
  }
}

The trick is that doSomeProcessing gets invoked only under certain conditions. Initializing the list is a very expensive procedure and it might not be needed at all.

I have read articles on why the double-check idiom is broken and I was a bit skeptic when I saw this code. However, the control variable in this example is a boolean, so a simple write instruction is needed, as far as I know.

Also, please notice that someList has been declared as final and keeps a reference to a concurrent list, whose writes happen-before reads; if instead of a ConcurrentLinkedQueue the list were a simple ArrayList or LinkedList, even though it has been declared as final, the writes don't require to happen-before the reads.

So, is the code given above free of data races?

Answer 1

Ok, let's get the Java Language Specification. Section 17.4.5 defines happens-before as follows:

Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second. If we have two actions x and y, we write hb(x, y) to indicate that x happens-before y.

• If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).
• There is a happens-before edge from the end of a constructor of an object to the start of a finalizer (§12.6) for that object.
• If an action x synchronizes-with a following action y, then we also have hb(x, y).
• If hb(x, y) and hb(y, z), then hb(x, z).

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

It then goes on two discuss:

More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-before relationship. Writes in one thread that are in a data race with reads in another thread may, for example, appear to occur out of order to those reads.

In your instance, the thread checking

if (!initialized)

may see the new value for initialized before it sees all writes that added to someList and hence work with a partially filled list.

Note that your argument

Also, please notice that someList has been declared as final and keeps a reference to a concurrent list, whose writes happen-before reads

is irrelavant. Yes, if the thread read a value from the list, we could conclude that he also sees anything that happens-before that the write of that value. But what if it doesn't read a value? What if the list appears empty? And even if it read a value, it doesn't mean that subsequent writes have been performed, and hence the list may appear incomplete.

Answer 2

First, it's the wrong use of the concurrent queue. It's intended for the situation where multiple threads are putting to and polling from a queue. What you want is something that's initialized once, then remains readonly afterwards. A simple list impl would do.

volatile ArrayList<String> list = null;

public void doSomeProcessing() {
    // double checked locking on list
    ...

Suppose, for the sole purpose of brain exercise, we want to achieve thread safety through the concurrent queue:

static final String END_MARK = "some string that can never be a valid result";

final ConcurrentLinkedQueue<String> queue = new ...

public void doSomeProcessing() 
    if(!queue.contains(END_MARK)) // expensive to check!
         synchronized(this)
            if(!queue.contains(END_MARK))
                  result = ...
                  queue.addAll(result);
                  // happens-before contains(END_MARK)==true
                  queue.add( END_MARK );

     //when we are here, contains(END_MARK)==true

     for(String s : queue)
         // remember to ignore the last one, the END_MARK

Note, when declaring the variable, I used the full class type, instead of some interface. If someone argues that it should be declared interface List, so that "I can change it to any List impl, and I have only one place to change", he is too naive.

Answer 3

Wikipedia suggests that you should use the volatile keyword.

Answer 4

Use of ConcurrentLinkedQueue doesn't guarantee absence of data race in this case. Its javadoc says:

As with other concurrent collections, actions in a thread prior to placing an object into a ConcurrentLinkedQueue happen-before actions subsequent to the access or removal of that element from the ConcurrentLinkedQueue in another thread.

That is, it guarantees consistency in the following case:

// Thread 1
x = 42;
someList.add(someObject);

// Thread 2
if (someList.peek() == someObject) {
    System.out.println(x); // Guaranteed to be 42
}

So, in this case x = 42; can't be reordered with someList.add(...). However, this guarantee doesn't apply to the inverse situation:

// Thread 1
someList.addAll(wsResult);
initialized = true;

// Thread 2
if (!initialized) { ... }
for (final String s : someList) { ... }

In this case initialized = true; still can be reordered with someList.addAll(wsResult);.

So, you have a regular double-check idiom without any additional guarantees here, and therefore you need to use volatile, as suggested by Bozho.

Answer 5

Instead of having the initialized flag, can you just check someList.isEmpty()?