7

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

ciamej
  • 6,918
  • 2
  • 29
  • 39

3 Answers3

8

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.

John Vint
  • 39,695
  • 7
  • 78
  • 108
  • 2
    +1. Nice explanation of the memory barrier semantics of `volatile`, although it should be pointed out that pre-JSR133 JVMs (i.e. Java < 5.0) did not have the same semantics... – thkala Jun 29 '11 at 17:35
  • Thanks for a great answer. I hope you understood well what's going on in my code. There is no root reference, only a root node. That's why I set two different next fields (one of the new object and one of the root node). – ciamej Jun 30 '11 at 02:09
  • @ciamej thanks for clarifyinh for us. My answer was written with the assumption you describe. Just to reiterate and to conclude, your solution to have a 'final' value/fields and a volatile next is absolutely fine and probably best optimized then synchronized counterpart. Take a look at the ConcurrentHashMap's HashEntry inner class. It uses a similar idiom you describe – John Vint Jun 30 '11 at 03:41
2

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.

thkala
  • 84,049
  • 23
  • 157
  • 201
  • I am not completely sold on this. If 'would impose a memory barrier on all instances of the node class' were true then the ConcurrentHashMap would incur the same cost for each node within a bucket, right? – John Vint Jun 29 '11 at 17:20
  • @John V.: It does, but it's necessary in that case - the usage pattern of the Map is not known. The OP on the other hand only needs to synchronize on the root node. – thkala Jun 29 '11 at 17:26
  • When you say on 'all instances' do you mean that a write to a next field will impose a barrier on all the nodes also? Or do you only mean that each node will have its own barrier when written or read? – John Vint Jun 29 '11 at 17:32
  • @John V: Each node will have it's own barrier, so when the threads will iterate over the list they will not be able to cache anything, unless the JVM optimizes the barrier out, which I believe it won't - contrary to any superfluous `synchronized` items. – thkala Jun 29 '11 at 17:37
  • @John V: Well, it's more complex than that - depending on the processor, invalidating a cache line could implicitly affect more than one objects. And I believe that a write to a volatile field would flush all pending writes, regardless of which object they belong to. – thkala Jun 29 '11 at 17:42
  • Ok I see, I missread. You're right the JVM will not optimize those reads out, the underlying OS may though. If the OS can optimize the volatile reads, it will not be able to optimize synchronized reads. The write may flush all writes or it may just keep it in the cache line that processors are communicating with. But you are definitely right (I wrote write too many writes) , it is a bit complicated. – John Vint Jun 29 '11 at 17:53
  • 1
    @thkala: You are talking about general case, right? but does it also hold for the x86 architecture? I think that in x86 only volatile writes issue a memory barrier and iterating threads could easily cache values and read them without any penalty (this seems to be reassured by John V's answer point 2, since the time is "very close to a normal read"). Could you please elaborate more on that? – ciamej Jun 30 '11 at 01:37
2

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.

toto2
  • 5,306
  • 21
  • 24
  • A volatile read on the first node does not guarantee visibility/ordering constraints on the Node's non-volatile fields. A separate write occuring on say firstNode.next.next holds no happens-before relationships and thus is not truly thread safe – John Vint Jun 29 '11 at 23:58
  • See the OP: the nodes are immutable. – toto2 Jun 30 '11 at 00:23
  • They are only immutable when the next field is set. 'then setting the root's next field to this new node' Unless I am missing something there is no way you can have all nodes immutable in a Linkedlist where as a node needs to add to the list by settings its next field. – John Vint Jun 30 '11 at 00:37
  • According to the OP the `next` field is also immutable. I guess all nodes are added as the `firstNode`. – toto2 Jun 30 '11 at 00:46
  • @toto: You are right that it would be the best to have a volatile reference to the first node. Unfortunately I'm a bit stuck with this root node design because of reasons I'd like to skip. – ciamej Jun 30 '11 at 01:45
  • I used the term immutable in a not very precise manner... What I meant was that after all the fields are set (including the next field) there will be no need to change them, though non of them are really declared final. – ciamej Jun 30 '11 at 01:46
  • To be more precise, once a node gets into the structure it won't be modified until it is disposed. The disposal is that special situation that I've mentioned in my question. At some point it might happen to be that some of the last nodes in the structure up to the very tail are no longer needed and no thread will ever look them up anymore. This is the only situation that I might change the next field of some node to null to cut the list and let the older nodes be GCed. But this special case does not involve any concurrency so its irrelevant. – ciamej Jun 30 '11 at 01:58