Volatile array of arrays

Question

I have a class with

private volatile long[][] data = new long[SIZE][];

which initially contains just nulls and a method which accesses it. When it hits an null element, it creates a long[] and stores for future use. This operation is idempotent and multiple threads wasting time on the same element is not a problem.

No thread must ever see an incompletely filled element. I hope that the following code does it right:

long[] getOrMakeNewElement(int index) {
    long[] element = data[index]; // volatile read
    if (element==null) {
        element = makeNewElement(index); // local operation
        data = data; // ugliness 1
        data[index] = element;
        data = data; // ugliness 2
    }
    return element;
}

The first ugliness is for ensuring that other threads can in theory see the changes made to element. They can't actually access it as it isn't stored anyway yet. However, in the next like element gets stored and another thread may or may not see this store, so AFAIK the first ugliness is necessary.

The second ugliness then just ensures that other threads see the new data containing element. The strange thing here is using the ugliness twice.

Is this is necessary and sufficient for safe publication?

Note: While this question is similar to this one, it's no duplicate as it deals with modifying an existing 1D array rather than creating one. This makes the answer clear.

Update

Note: This is no production code and I know and don't care about the alternatives (AtomicReferenceArray, synchronized, whatever, ...). I wrote this question in order to learn more about the JMM. It's a real code, but used just for my fooling around with project Euler and no animals were harmed in the process.

I guess, a safe and practical solution would be

class Element {
    Element(int index) {
        value = makeNewElementValue(index);
    }
    final long[] value;
}

private volatile Element[] data = new Element[SIZE];

where the Element ensures visibility via the Semantics of final Fields.

As pointed by user2357112, there's also a (IMHO harmless) data race when multiple thread write the same data[index], which is actually easy to avoid. While the reading must be fast, making a new element is slow enough to allow for any synchronization needed. It'll also allow a more efficient initialization of the data.

Answer 1

This is probably safe in practice, according to roach-motel model, or JSR-133 Cookbook.

Let's expand all volatile reads/writes in the following code

    element[0] = something;
    data = data; // ugliness 1
    data[index] = element;

it becomes

    element[0] = something;             [0]
    tmp1 = data;  // volatile read      [1]
    data = tmp1;  // volatile write     [2]
    tmp2 = data;  // volatile read      [3]
    tmp2[index] = element;              [4]

The critical barrier here is [2]+[3]. According to roach motel model:

  nothing before a volatile write can be reordered after  it.
  nothing after  a volatile read  can be reordered before it.

Therefore [2]+[3] combo prevents instructions from being reordered across it. Therefore [0] and [4] cannot be reordered.

Note that [1]+[2] combo is not enough; without [3], the code can be reordered as [1] [4][0] [2].

---

That's cool. But is it safe in JMM which is weaker than roach-motel? I think it's not. This code

    long[] element = data[index];
    x = element[0];

is expanded to

    tmp0 = data; // volatile read   [a]
                                    [b]  
    element = tmp0[index];          [c]
    x = element[0]                  [d]

Now imagine the earliest thread does [a], then gets paused in [b] for a few seconds, then does [c]. Now [a] is before any other volatile writes, therefore it does not establish any ordering per JMM, therefore there's no telling what [c] and [d] could read. [c] is not a serious problem, but [d] is - [d] could read the default value 0 instead of something written by [0]; or even gibberish because it's long.

As far as I know, if you want to publish an object through a volatile field, either it must be a new object (immutable or not), or it must use volatile members.

JMM is strong enough to guarantee that common concurrency patterns work; but if you want to do something unconventional, it is often too weak; and the worse thing is that JMM is too complicated as a reasoning framework. So if you want your code strictly JMM compliant, the best practice is to follow boring ordinary patterns:)

---

A better solution that favors reads would be copy-on-write.

Answer 2

The Java Language Specification defines the semantics of volatile as follows:

A write to a volatile variable v synchronizes-with all subsequent reads of v by any thread (where "subsequent" is defined according to the synchronization order).

The spec guarantees that whenever an action happens-before another, it is visible to that other action.

For an object to be safely published, the object's initialization must be visible to any thread that obtains a reference to this object. Since the field we are interested in is not final, this can only be accomplished if the initialization of the object is guaranteed to happen-before any other thread obtains a reference to this object.

To verify whether this is the case, let's look at the happens-before graph of the actions involved:

  makeNewElement        
        |               
        v               
   read of data         
        |               
        v               ?
  write to data --------------> read of data
        |                             |
        v                             v
write to array element       read of array element
        |                             |
        v                             V
  read of data                   useElement
        |
        v
  write to data

Clearly, there is a path from makeNewElement to useElement if and only if "write of data" synchronizes-with the "read of data", which it does if and only if the read is subsequent. However, it need not be subsequent: For every execution where the read is subsequent, we can create another execution where it is not, simply by moving the read backwards in synchronization order:

  makeNewElement                   
        |                                
        v                                
   read of data                    read of data
        |                                |
        v                                |
  write to data                          |
        |                                |
        v                                v
write to array element          read of array element            
        |                                |
        v                                v
  read of data                      useElement
        |                                
        v                                
  write to data                     

Ordinarily, we could not do this, as this would change the value being read, but as the writes do not change the value of data, we can not tell from the value read whether the read was before or after the write.

In such an execution, the reference to our new object is published through a data race, because the write of the array element does not happen-before the read. In such cases, the spec writes:

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.

That is, the reading thread may see the reference to the new object, but not the effect of its initialization, which would be rather bad.

So, how could we ensure that the read is subsequent? If the value read from the volatile field proves that the necessary write has taken place. In your case, we need to distinguish writes to different elements. We can do this with a separate volatile variable for each array element:

Element[] data = ...;

class Element {
    volatile long[] value;
}

long[] getOrMakeNewElement(int index) {
    long[] element = data[index].value; // volatile read
    if (element==null) {
        element = makeNewElement(index); // local operation
        data[index].value = element;
    }
    return element;
}

or change the value of your single volatile field for each write:

volatile long[][] data;

long[] getOrMakeNewElement(int index) {
    long[] element = data[index]; // volatile read
    if (element==null) {
        long[][] newData = Arrays.copyOf(data);
        newData[index] = element = makeNewElement(index);
        data = newData;
    }
    return element;
}    

Of course, this latter solution has the disadvantage that concurrent writes can conflict even for different array elements.

Answer 3

I'd identify two aspects of your task. The first one is "visibility" of new array prepared by makeNewElement (both, a reference to the array and its initial content prepared by the method) among a number of threads. That's exactly what JMM and Happens-before relationships (with memory barriers) deal with. As you probably know, there is a number of ways to set a happens-before edge (as well as materials about JMM/HB)

• http://shipilev.net/blog/2014/jmm-pragmatics/
• http://shipilev.net/blog/2014/safe-public-construction/
• http://shipilev.net/blog/2014/on-the-fence-with-dependencies/
• http://g.oswego.edu/dl/jmm/cookbook.html etc...

According to JMM, volatile write to a shared var HB volatile read from the same var. That means volatile read should see all changes made by the last volatile write to the variable. And since all writes before the volatile write cannot be reordered after it, they should be visible after the volatile read as well. So, your code could be the following:

long[] getOrMakeNewElement(int index) {
    long[][] data = this.data; // volatile read (to a local var) produces memory barriers to get all changes happened before this read (see volatile write below). Acquire semantic
    long[] element = data[index]; // work with local
    if (element == null) {
        element = makeNewElement(index); // local operation
        data[index] = element;
        this.data = data; // volatile write (from the local var) produces memory barriers to make all changes, including just created array and all writes to it, visible to all volatile reads which happen after this write (see volatile read above). Release semantic
    }
    return element;
}

if you are not worrying about the "element" array should be created only once for an index and all readers should have a reference to one instance of the array. That's the second question - "critical sectioning". You can deal with it with CAS or any type of locking (synchronized, java.util.concurrent.locks etc). For example:

long[] getOrMakeNewElement(int index) {
    long[][] data = this.data; // volatile read
    long[] element = data[index];
    if (element == null) {
        synchronized (this) { // critical section
            data = this.data; // volatile read again 
            element = data[index];
            if (element == null) { // yes, that's a double checking
                element = makeNewElement(index);
                data[index] = element;
                this.data = data; // volatile write
            }
         }
    }
    return element;
}

Now, when you deal with the array prepared by makeNewElement, you may have to care about visibility of changes of its content, in addition to visibility of the reference to the array and its initial state. If some threads write some longs to the array and some other ones read the written values, you need HB edges/Memory barriers, for example with MonitorEnter/MonitorExit (just as an example of other way to have a HB edge) as follows:

public class MyArayWriter extends Thread {
    public void run() {
        final long[] myarray = getOrMakeNewElement(1);
        synchronyzed (myarray) { // MonitorEnter produces memory barriers to make all changes made before visible below. Acquire semantic 
            myarray[0] = 1;
        } // MonitorExit produces memory barriers to make all changes made before in this thread visible for all other threads.  Release semantic
    }
}

public class MyArayReader extends Thread {
    public void run() {
        final long[] myarray = getOrMakeNewElement(1);
        synchronyzed (myarray) { // MonitorEnter... Acquire semantic
            System.out.println(myarray[0]);
        } // MonitorExit... Release semantic
    }
}

OR use AtomicReferenceArray/AtomicLongArray if you prefer:

private final AtomicReferenceArray<AtomicLongArray> data = new AtomicReferenceArray<>(SIZE);

As for your 1st version

long[] getOrMakeNewElement(int index) {
    long[] element = data[index]; // volatile read
    if (element==null) {
        element = makeNewElement(index); // local operation
        data = data; // ugliness 1 - DEFINITELY THERE IS NO NEED TO HAVE THIS ONE
        data[index] = element;
        data = data; // ugliness 2
    }
    return element;
}

it almost equals to my 1st version (without critical section for new array preparation) but you definitely can get rid of ugliness 1 as follows:

long[] getOrMakeNewElement(int index) {
    long[] element = data[index]; // volatile read (for acquire semantic with appropriate memory barriers)
    if (element==null) {
        element = makeNewElement(index); // local operation
        data[index] = element; // here is a volatile read, again
        data = data; // volatile read (again? but OK) and write, at last (for release semantic with appropriate memory barriers)
    }
    return element;
}

but even after that your version has a number of volatile operations instead of only two ones required for the safe publication - a volatile read to acquire and a volatile write to release.

UPDATE on your UPDATE

Your publishing of "value" array as a final one using 'Freeze action HB read of just created object reference':

class Element {
    Element(int index) {
        value = makeNewElementValue(index);
    }
    final long[] value;
}

private volatile Element[] data = new Element[SIZE];

guarantees that any reader sees a reference to the correctly instantiates and initially filled array and can be used only in case when you publish constant content (no one thread changes elements of that array after the array is published as a final field).

Answer 4

Your code has a data race. If threads A and B each execute

        data = data; // ugliness 1

then each execute

        data[index] = element;

then each execute

        data = data; // ugliness 2

there is no happens-before relationship between the two writes to data[index]. I am not entirely sure of what guarantees the JMM makes in the presence of data races, but there aren't many. It would not be a good idea to use this code.