volatile variables and memory barrier in java

Question

I've got a data structure which consists of linked nodes. You can think of it as of a simple LinkedList. Each node of the list consists of some value and a next field pointing the other node or null if it is the last node. The first node works as a root, it has no value it only points to the next node. All the other nodes are practically immutable that is once they are created neither their value nor their next field change during lifetime, unless the structure is being disposed which relates to a specific situation.

One (only one) thread adds new nodes to the front of the list. It is accomplished by constructing a new object, setting its fields and setting the next field to the object pointed by the root, then setting the root's next field to this new node.

The other nodes browse through the structure only performing reads. They have a reference to the root node, then they go through the other nodes until they find what are looking for or reach the end of the list.

My question is: is it sufficient to make the next field volatile? From my understanding of java memory model, if the main thread (the one that adds new nodes) will perform a volatile write when adding a new node then everything will be synchronized just fine and no inconsistencies will occur.

Also is it right to assume that on x86 architecture reads of a volatile variable won't incur any performance degradation? As the other threads will frequently browse through the structure reading the next field it is important that this can be done freely without any memory barriers etc.

I also have one more concern. The threads that are going to browse the structure are also going to hold some additional nodes. These nodes will be completely thread-local that is they are going to be used by only the thread that created them and are not going to be shared at all. For these additional nodes it is unnecessary for the next field to be volatile. Moreover setting the volatile next field will issue a memory barrier which will cause an undesirable performance loss. I wonder is there a way to avoid this. Ideally it would be just perfect if the next field would work sometimes as a volatile field and sometimes as a normal field ;) or if I had a full control and could issue memory barriers on my own, whenever I need.

Edit:

I also wondered would it be possible to somehow synchronize all these writes on a different volatile variable? For example some other completely unrelated static variable? Since volatile write flushes all the pending writes, wouldn't it be possible for the next field not to be volatile and instead a different volatile variable would be written after the updating thread does all the work?

It does not look very safe to me since there is no happens before relation and the previous writes might get reordered. Next field assignments could be reoredered with the value fields assignments leading to iterating threads observing inconsistent object state.

But maybe it is possible to come up with such a scheme that would be safe? How about this one:

updating thread first constructs a new object, initializes its value fields, sets its next field to node pointed by the root node, performs a volatile write on some static variable, sets the next field of the root node to the newly created node

Answer 1

Your root node actually does not need to be a node. You only need a reference to the first "real" node.

public class LinkedList {
  private volatile Node firstNode;
  ...
  addNode(Node node) {
    node.next = firstNode;
    firstNode = node;
  }
}

So you don't need to make the next field volatile in all your nodes; the nodes are not synchronized at all. You could use that class for the non-synchronized linked lists if you don't mind the cost of the volatile access to the first node. Or you could instead simply rewrite the class with a non-volatile firstNode for the non-synchronized version.

Answer 2

1.

Based on what you say here

constructing a new object, setting its fields and setting the next field to the object pointed by the root, then setting the root's next field to this new node.

Then yes, setting the next field to volatile will correctly synchronize. Its important to understand why. You have three sets of writes before hand, the one to the node object, one to the fields and one to the nodes next (though not completely sure why you are doing that, maybe I miss understand something).

So that's 2 + (N number of field) writes. At this point there is no happens-before relationship and if the node is written normally there is no guarantee. As soon as you write to the volatile field all previous writes will now also be visible.

2.

Volatile reads/writes on a x86 (or any cache-coherent) operating system has the following attributes:

 volatile-read: very close to a normal read
 volatile-write: about 1/3 the time of a synchronization write 
         (whether within intrinsic locking or  j.u.c.Lock locking)

3.

Looks like you will have to create VolatileNode and Node. There was a proposal for Java 7 to come out with a Fences API which you can specify which style of reading/write you want to execute with a static utility class but doesn't look like its releasing

Edit:

Thkala made a great point I feel is worth including

although it should be pointed out that pre-JSR133 JVMs (i.e. Java < 5.0) did not have the same semantics

So what I wrote does not apply to applications run in Java 1.4 or less.

Answer 3

Making the next field volatile would impose a memory barrier on all instances of the node class, not just the root node. I'd expect that to be more expensive than just using synchronized on the root node. In addition, the JVM may be able to optimize synchronized method calls far better. See also this and this.

That said, you should probably try both and benchmark/profile to see what happens.