question about volatile

[tm jee]

Hi folks, 

I'm hoping to get some confirmation of my understanding of volatile from knowledgeable folks in this group.

Let's say 

volatile Map myMap; // a non-thread safe map

public void method_that_writes() {

  Map temp = myMap;

  // make changes to temp 

  myMap = temp;

}

public Object method_that_reads() {

   Map temp = myMap;

   // read from temp and return some object

   return someObjFromMyMap;

}

in a multithread environment, 

1] can i say that the above read write is thread safe as in  "weakly consistent"  

2] changes in method_that_writes() by one thread will be seen by another thead that's in method_that_reads() according to the hb relationship defined in JMM spec. (as per the volatile contract)?

Tia. Appreciated. 

Cheers

[Dan Eloff]

No, you're doing it wrong. Presumably you use volatile because Map is not thread-safe for concurrent modifications. The read code is fine in this case, but the right code needs to:

1) be the only thread that can write, otherwise temp might be an old map and another thread replaces myMap in the interim and then you overwrite that with myMap = temp. To do that safely with multiple writers you would need to CAS myMap and handle the failure case by re-reading myMap into temp, re-copying it, etc.

2) needs to make a copy of the map and modify the copy, then assign the copy back to myMap. This is obviously more expensive that using a ConcurrentHashMap for a high write volume, but can be more efficient if writes are rare enough.

If myMap were threadsafe, you don't need volatile at all.

And although nobody would ever make any personal progress if they paid attention, if you're going to do this in an important code base, at least get your code reviewed by experts. Lock-free concurrency is a wild world of very difficult debugging and rare and "impossible" errors. I've been learning it for years and it's still the only programming problem that has defeated me. I once spent three months of evenings and weekeds debugging a concurrent skip list implementation. I never did find all the bugs, I went for an easier algorithm (single-writer) eventually. You've been warned.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[tm jee]

Cheers Daniel. Let's say its using single-writer principal, 

public void method_that_writes() {

  Map temp = myMap;

  // change #1

  // change #2

  // change #3

  myMap = temp;

}

1]  would making a copy of myMap still necessary? Assuming that change#1, change#2 and change#3 will be flushed to main memory as the discretion of hotspot/hw/whatnot and that reader do not really care if change#1, change#2 and change#3 needs to get it in one atomic action. 

2]  but when myMap=temp is executed, is it not right that there is a guarantee that a memory fence should be issued such that it gets into main memory?

 

Cheers folks.

[tm jee]

Missed another question

3] can it be guarantee that myMap = temp will not be optimized away? Last i know (if memory serves me right) volatile stuff will never ever be optimized away.

Thanks Daniel for the warning. All this is for learning / academic purposes and also to hopefully satisfy my curiosity around this matter. :)

[Henri Tremblay]

JVM never changes the behavior of the code. myMap = temp is doing something (unless I've lost track of your code) so it can't be removed.

However, the JVM can reorder the code between memory barriers. That's what we need to beware of and volatile is one of the tools.

The temp = myMap; myMap = temp; trick is used a lot in java.util.concurrent.

--

[Olivier Bourgain]

1] With a single writer, we can assume that it can already see the last state of the map, having created this state itself, so i think it doesn't need this volatile read. This is only true if it is a single writer to both the map instance and the myMap reference.

2] On this write, you have a happens before relationship for readers on this volatile reference for reads happening after the write. If the reader takes a reference to myMap and after that the writers modifies the map and assign temp = myMap, there is no guarantee that the reader will see the changes until it performs a new volatile read.

3] IIRC, the volatile may be removed. What can not be removed is the effect on memory ordering, be it the JIT performing no optimization/reordering before and after the barrier or an instruction providing the required memory ordering if the underlying hardware memory model does not enforce it.
So the assignment of temp to myMap in itself is useless, what is interesting here is the visibility of all changes.

If the Map is not thread safe, I will not assume that using a single writer will solve the problem. Readers might still see inconsistent states or worse.

If a high throughput is not required, a Collections.synchronizedMap will do the trick.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

[Dan Eloff]

Yes the copy cannot be avoided, this is the copy-on-write pattern for a reason. You cannot make concurrent changes to a non-thread safe data structure (that's true for concurrent with just readers.) So the only way to do it safely is make a copy and modify the copy.

volatile is not strictly needed here, what is needed is a write barrier on myMap = temp and a read barrier on temp = myMap. This can be done for example with Unsafe.putOrderedObject on write and Unsafe.getVolatileObject on read. (The C++11 equivalent of store(release) and load(acquire).) On x86 that's a noop, no actual memory barriers need be issued. You still need it though as a compiler barrier so the compiler doesn't re-order loads and stores across the barriers. Volatile is a little stronger in ordering semantics and will issue real memory barriers usually, even on x86. However, it's simple and it's not likely to be your bottleneck, so just stick with volatile.

[Alexandru Nedelcu]

On Mon, Jun 2, 2014 at 8:03 PM, Dan Eloff <dan....@gmail.com> wrote:

Yes the copy cannot be avoided, this is the copy-on-write pattern for a reason. You cannot make concurrent changes to a non-thread safe data structure (that's true for concurrent with just readers.) So the only way to do it safely is make a copy and modify the copy.

The alternative is to use an immutable/persistent data-structure, as in data structures that use structural sharing on changes. With Scala’s Map for example, you could simply do this and it would work:

myMap = myMap.updated("some-key", value)

// on another thread
myMap("some-key")

On updates, other threads will see either the old version or the new version, no intermediate state, no locks necessary and the seen snapshots can’t be destroyed by the producer.

The problem with persistent data-structures is that they are usually based on trees and/or linked-lists, but mostly trees, which means increased cache misses, although this is an active area of research - for example Scala’s Vector, which is a 32-wide tree and Scala’s Map, a persistent HAMT variant are pretty decent given the design constraints. They also blend well with atomic references (CAS updates) and with STM, however in high-contention scenarios this will stress the GC and it doesn’t scale as the contention can only happen at the root (Martin Thomson has an interview about it). However they perform fine if the updates are not contended (i.e. they are IMHO perfect for the above use-case), because shared reads need no synchronization and the producer doesn’t need to publish a full copy on updates. And if extreme throughput is not one’s focus, then the biggest advantage of persistent data-structures is that they are worry free.

​

--
Alexandru Nedelcu
www.bionicspirit.com

PGP Public Key:
https://bionicspirit.com/key.aexpk

[tm jee]

> Yes the copy cannot be avoided, this is the copy-on-write pattern for a reason. You cannot make concurrent changes to a non-thread safe data structure (that's true for concurrent with just readers.) So the only way to do it safely is make a copy and modify the copy.

Regarding you statement "you cannot make concurrent changes to non-thread safe data structure (that's true for concurrent with just readers)"

Case 1 #

volatile aMap // non-thread safe map

thread #1 (before thread#2 starts) single writer

aMap.put("a", "b"); # change1

.... # change2

...  # change3

thread #2 #3 #4 #5 ... #n (after thread#1 ends) multiple reader

aMap.get(...)  # read1

  ..... # read2

  ..... # read3

Case #2

final bMap; // initialized in constructor

thread #2 #3 #4 #5 ... #n (after constructor is done) multiple reader

bMap.get(...)  # read1

  ..... # read2

  ..... # read3

In both case #1 and case#2, surely concurrent reads on non-thread safe data structure is still ok, if not my understanding is fundamentally flaw ? Thoughts anyone?

Tia

 

[Nitsan Wakart]

Dropping in late:

An issue thus far not discussed is map resizing. If a put(K,V) results in a resize the map internal array/arrays will be replaced which can lead to a broken view on the readers side(returning wrong value for key for instance). To fix this issue you will need to change the map implementation.

[tm jee]

Hi Nitsan, 

Nice of you dropping by. Regarding your statement. I can totally relate to it if single write and multiple read are working at the same time (and the copy-on-write must be done statement Daniel is talking about). But what about the case#1 and case#2 i mentioned above? Surely those are still thread-safe aren't they not?

Cheers

[Vitaly Davidovich]

Cases 1 and 2 are fine.  In case 1 you probably don't even need the volatile modifier as it's very likely that the way you start the other threads or hand off the map to them already induces a happens-before edge.

Sent from my phone

--

[Dan Eloff]

> An issue thus far not discussed is map resizing. If a put(K,V) results in a resize the map internal array/arrays will be replaced which can lead to a broken view on the readers side(returning wrong value for key for instance). To fix this issue you will need to change the map implementation.

That's besides the point, even without the resizing it's unsafe to modify the map while readers may be reading it.

[Vitaly Davidovich]

This is actually known (at least I've seen it several times) to potentially cause a reader to enter an infinite loop if the bucket list it's traversing is modified at the "right" time by a writer.

Sent from my phone

On Jun 3, 2014 2:46 PM, "Dan Eloff" <dan....@gmail.com> wrote:

> An issue thus far not discussed is map resizing. If a put(K,V) results in a resize the map internal array/arrays will be replaced which can lead to a broken view on the readers side(returning wrong value for key for instance). To fix this issue you will need to change the map implementation.

That's besides the point, even without the resizing it's unsafe to modify the map while readers may be reading it.

[Dan Eloff]

Case 1 and Case 2 don't involve any concurrent changes. You don't need volatile at all. You're sharing an "immutable" structure. That's safe.

[Vitaly Davidovich]

Should mention that I've seen this with HashMap, in case that wasn't clear.

Sent from my phone

[tm jee]

Cases 1 and 2 are fine.  In case 1 you probably don't even need the volatile modifier as it's very likely that the way you start the other threads or hand off the map to them already induces a happens-before edge

 Cool.

Case A:

======

volatile Map theMap; // member variable

thread1 = new Thread(new Runnable() { 

   // modify theMap

}).start();

thread1.join();

thread2 = new Thread(new Runnable(){

   // read theMap

}).start(); 

in this case volatile is not required. It's because when thread2 access theMap it has to get it from somewhere and it doesn't exists anywhere not from it's registries, L1 or L2 so it has to get it from L3 (say main memory). Is this argument right so far?

Say in CaseB:-

volatile Map theMap; // member variable

thread1 = new Thread(new Runnable() { 

   // modify theMap

}).start();

thread1.join();

thread2 = new Thread(new Runnable(){

   // modify theMap

}).start(); 

thread2.join();

thread2 = new Thread(new Runnable(){

   // read theMap

}).start(); 

In this case, presumably if my argument above is correct then volatile is also not necessary. Is this right?

cheers folks.

[Vitaly Davidovich]

You don't need volatile in these cases, yes.  In JMM terms, Thread.start() is a synchronizing action which means it creates a happens-before edge.  Talking about caches, memory and registers isn't even needed here.

Sent from my phone

[tm jee]

Also guys, are there any hb/sw relationship that kindof implies this? If it is true that is?

[tm jee]

You don't need volatile in these cases, yes.  In JMM terms, Thread.start() is a synchronizing action which means it creates a happens-before edge.  Talking about caches, memory and registers isn't even needed here

Alright. Found it 

• An action that starts a thread synchronizes-with the first action in the thread it starts

 Thanks folks.

[Alexandru Nedelcu]

On Tue, Jun 3, 2014 at 10:24 AM, ‘Nitsan Wakart’ via mechanical-sympathy [mechanica...@googlegroups.com](mailto:mechanica...@googlegroups.com) wrote:

An issue thus far not discussed is map resizing. If a put(K,V) results in a resize the map internal array/arrays will be replaced which can lead to a broken view on the readers side(returning wrong value for key for instance). To fix this issue you will need to change the map implementation.

Btw, Scala has an interesting mutable/concurrent map implementation called TrieMap, from which readers can read non-blocking snapshots, based on this paper: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

Haven’t evaluated or used it yet, but it’s interesting nonetheless.

​