Happens before between putting and getting from and to ConcurrentHashMap

[John Hening]

Hello, let's look at:

    class P {      public String x;
    }
   
    ConcurrentHashMap<Integer, P> x = new ConcurrentHashMap<>();

    new Thread(() -> {                 // Thread 1
        x.put(1, new String("x"));     // 1
    }).start();
   
    new Thread(() -> {                 // Thread 2
            P p = x.get(1);             // 2
            if(p != null){            
                print(p.x);            // 4
            }
    }).start();

If thread 2 observes p != null is it guaranteed by JMM that p.x is initialized? For my eye, yes, because:

Let's assume a such execution when p != null was true. It means that there is a synchronize-with relation between x.put(1, new String("x")); --sw--> x.get().
Putting and getting an element from ConcurrentHashMap contain synchronization access (and, actually, synchronization-with is between them).

In a result, there is a chain of happens-before relation:

    tmp = new String("x") --hb--> x.put(1, tmp) --hb--> x.get(1) --hb--> read(p.x)

Yes?

[Gil Tene]

Well, "yes, sort of".

Your example works for String, because it is immutable.

Specifically, there is a happens-before relationship between the constructor's initialization of the final fields of the String and the subsequent publishing store of the result of the constructor.

However, non-final fields have no such happens-before relationship with the publishing store. E.g. the cached hash field in String may or may not be have been initialized when p.x is read. 

This [race on hash field initialization] has no visible side effect because of how the hash field is used in String: it caches the hash code, and will freshly compute the hash from the immutable char[] if the field holds a 0. So even if the initialization races with a call to hashCode() [e.g. a call to hashcode happens on another thread before the hash field is initialized, and the initialization overwrites the cached value with a 0], all that would happen is a recomputation of the same hash. The value returned by hashCode() won't change.

But in other cases where non-final fields are involved, e.g. if p.x was a Foo with a non-final field y with a getter, p.x.getY() may return an uninitialized value after the get() returns a non-null p.

[John Hening]

@Gil Tene,

thanks for your response.

But in other cases where non-final fields are involved, e.g. if p.x was a Foo with a non-final field y with a getter, p.x.getY() may return an uninitialized value after the get() returns a non-null p.

So, it means that in this case:
 

   class Foo {      

        public Foo(int i) { x = i;}

        public int x;
    }
   
    ConcurrentHashMap<Integer, Foo> x = new ConcurrentHashMap<>();

    new Thread(() -> {                 // Thread 1

        x.put(1, new Foo(1));     // 1

    }).start();
   
    new Thread(() -> {                 // Thread 2

            Foo p = x.get(1);             // 2
            if(p != null){                 // 3
                print(p.x);            // 4
            }
    }).start();

the Thread 2 can read 0 in the line (4).

I cannot agree with that because:

1. Note that a putting element to the hashmap stores a value to the field annotated as volatile: https://github.com/bpupadhyaya/openjdk-8/blob/master/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java#L622

2. Note that a getting element from the hashmap reads a value from the field annoated as volatile: https://github.com/bpupadhyaya/openjdk-8/blob/master/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java#L622

So, if the second thread obeserves not null value in the 3 line it means there is a synchronization-with relation between storing a Foo instance to value field in hashmap and reading from them.

In a result we have a HB relation:

new Foo(1) --HB--> store to volatile value --HB--> read from volatile value --HB--> read Foo.x field

We have a such chain of HB relations because it is a transitive close of PO and SW orders:

Could you explain why I am wrong?

[yawkat]

I don't think this is correct.

First of all, it's not really relevant if String is immutable or not, in this case: It could already break at the (non-final, non-volatile) field x, which could be null if an instance of P was unsafely published. Of course, String being immutable has the implications you say - it doesn't require safe publishing and will still show up "all-or-nothing" - but I don't think this is relevant here.

However, in this case, the instance of `P` *is* safely published: Just like a volatile field store, storing into a CHM is a safe publication. So the code cannot fail - if the .get returns not-null, the String field will also be non-null (assuming it has been set to non-null before the put of course, which it has here). This is basically a textbook JCIP case of safely publishing a mutable object.

It looks like the example mistakenly does `new String` instead of `new P`, so that might have been a bit confusing :D

- Jonas

[Vladimir Sitnikov]

> storing into a CHM is a safe publication

+1

That's declared in CHM JavaDoc: 

More formally, an update operation for a given key bears a
* <em>happens-before</em> relation with any (non-null) retrieval for
* that key reporting the updated value.

Vladimir

[Gil Tene]

I'd be happy to be wrong here, but...

This statement in the CHM contract (JavaDoc quoted below) establishes a happens-before relationship between the put into the CHM and any (non-null) retrieval form the CHM. It amounts to a safe publication within the CHM itself, but does not read on the constructor of the value being put() into the CHM. There is no contract I've found that establishes a happens-before relationship between the initialization of non-final fields in some object construction and the put of that object (or of some object that refers to it) as a value into the CHM.

It is true that in current implementation a put() involves a volatile store of the value into a Node<K,V>.val field, and that this volatile store does establish the needed happens-before relationship between constructor initialization of non-final fields in the value object and subsequent reads from the val field (including subsequent get() operations that return that value object). But (AFAICT) that quality can only be deduced by reading the source code of a current implementation.

It is also true that future implementations of CHM will likely maintain similar qualities since they seem to be desirable and de-facto provided currently, so it may be surprising for them to disappear in some future CHM implementation.

But AFAICT, nowhere in the CHM contract, or in the spec, does it actually say that this relationship (a happens-before between non-final field initialization in a constructor and an eventual get() of the constructed object from a CHM) can be counted on.

If someone finds that missing statement (in the documentation, not the implementation source statements) that would provide the full happens-before links to non-final-field initialization, please point it out.

[John Hening]

Gil,

thank you.

In the docs it is written

Retrievals reflect the results of the most recently completed update operations holding upon their onset. (More formally, an update operation for a given key bears a happens-before relation with any (non-null) retrieval for that key reporting the updated value.)

and, ineed, you right. It is too generally written. Actually it points a HB relation between updating and getting value but we cannot conclude that there is a HB between initialization of element and getting it (nonnull). So, for users of ConcurrentHashMap it means completely nothing because we don't need to take care of implementation details.

By the way, how to put an element safely (fully constructed) to ConcurrentHashMap if we need mutable object? I see only one solution (by adding a "mock" final field):

class C {
    ..
    mutable fields
    ..
    final boolean publishSafely;

}

[Vladimir Sitnikov]

Gil>I'd be happy

I wish you all the best. I truly adore the way you explain things.

Gil>There is no contract I've found that establishes a happens-before relationship between the initialization of non-final fields in some object construction and the put of that object (or of some object that refers to it) as a value into the CHM.

In this case that contract is provided by JLS "17.4.3. Programs and Program Order" and "17.4.5. Happens-before Order" .

TL;DR: "If x and y are actions of the same thread and x comes before y in program order, then hb(x, y)."

Let me take an example:

class Wrapper {

  int value;

}

static CHM map;

Thread1:

val w = new Wrapper();

w.value=42;

map.put("wrap", w);

Thread2:

val u = map.get("wrap");

if (u != null) { println(u.value); }

1) In thread 1 there's happens-before between write "value=42", and write of "w" into the map since "program order implies happens-before"

2) CHM provides happends-before for non-null retrieval of the value

3) "retrieval of the value u" happens-before "read of u.value" since "program order implies happens-before"

The happens-before order is a partial order, so it is transitive, so 1+2+3 gives "write of value=42 happens-before read of u.value".

The key point of having a CHM is to have 2 (happens-before across threads) which is not provided automatically if simple HashMap is used.

What do you think?

Gil>It is true that in current implementation a put() involves a volatile store

JavaDoc contract is there, so CHM would provide "happens-before relation between update and non-null retrieval" in future one way or another.

Vladimir

[Jean-Philippe BEMPEL]

Hello Vladimir, 

On Sunday, November 18, 2018, Vladimir Sitnikov <sitnikov...@gmail.com> wrote:

In this case that contract is provided by JLS "17.4.3. Programs and Program Order" and "17.4.5. Happens-before Order" .

TL;DR: "If x and y are actions of the same thread and x comes before y in program order, then hb(x, y)."

I don't read the paragraph the same way 😁

For me 17.4.3 explains that action should keep order to be consistent with program order and further more than data dependency should remain. Example is given regarding writes and reads for the same location or variable. 

Also you miss this in 17.4.5:

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.

In your example, there is a write to value but no read of this value inside the same thread, so the write is free to be reordered. 

Regarding CHM, there is happens before between put and get but no synchronize with. 

So for me the write can be reordered after the put without changing program order semantic. 

But maybe I am wrong too... 

 

Vladimir

--
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-sympathy+unsub...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gil Tene]

Well, I was wrong on the internet. (Again).

Vladimir is right, the happens-before is transitive. Regardless of the order of execution on either side, every field initialization (final or otherwise) happens-before the put(), and therefor happens-before any subsequent get() on any thread, such that the get()'ing thread cannot observe pre-initialization values in the value being put() in the CHM.

For others that might follow the confusing weekend logic that led me to the mistake: I need to remind myself that it is complicated (and error-prone) to deduce negatives from positive observations. E.g. "happened before" just means "there is no happens-before that prohibited it from being observed this way" (from JLS 1.4.5: "...Informally, a read r is allowed to see the result of a write w if there is no happens-before ordering to prevent that read.").

The process of making this mistake (for me) comes it comes from figuring out too many negatives in a row, as in when trying to fully figure out the meaning of "anti-anti-anti-missile-missile" in your head, without unfolding it on paper. It can lead to falsely jumping from "I have an example where I definitely saw A happen before B happened" to hb(A, B) instead of just the !hb(B, A) it actually means. And/or something like that backward.

For me, these multi-deep-negatives thinking sequence often start with something informal like "so we know that another thread can see pre-initialized values of non-final fields if the reference to the object was published without an ordering operation of some sort" followed by "so since I know that is allowed, what is it in this stuff [like the CHM put()/get() example above] that actually prevents it from happening in this case?", then, after finding the concrete ordering operation [the volatile write and read] in the implementation but not stated directly in the contract (now we are in a two-deep negative assessment), taking the path of "I can construct a sequence where I know that an initialization of a field in an object happened before a publication of the object, and where without this ordering operation another thread could still see a value that predates that initialization, so if I remove this implementation-specific ordering operation this can still happen under this contract" takes me into a triple negative territory.

The best thing to do is to erase the board and start from the other end...

The contract's happens-before statement between the put() and subsequent non-null get()s, even while not directly saying anything about the relationships with program operations prior to the put(), does carry a transitive property that covers them. So the contract would require all future implementations to apply some ordering operation(s) that would still enforce the happens-before, including its transitive properties.  What that operation would be doesn't matter, it is the implementor's responsibility to make sure it is there.

[yawkat]

According to JCIP, a happens-before order also constitutes a safe publication of the objects involved. Since there is a HB edge between the put and the get, this leads to a safe publication of the object stored in the map (safe publication is another JCIP term). JCIP also mentions CM explicitly. So the original code works just fine.

It is not true that you need a synchronizes-with edge for safe publication. In fact SW is insufficient for safe publication - see shipilevs "JMM pragmatics". HB being sufficient for this is also the reason why you can't see non-default field values in objects for example. There is a HB edge from the default initialization to all other actions in the program.

HB order is pretty complicated so I prefer JCIPs "safe publication" model. It makes the example very obviously correct, since mutable objects can be shared as long as they're safely published, and a put on a concurrent map constitutes safe publication. If you stick to JCIPs model, you will always be on the safe side - you only need the full JMM if you really need to get the last bit of performance :) (e.g. via piggy-backing)

- Jonas

[Vladimir Sitnikov]

Jean-Philippe>is a write to value but no read of this value inside the same thread, so the write is free to be reordered

It ("reordering") does not really matter.

For instance,

17.4.5. Happens-before Order> If the reordering produces results consistent with a legal execution, it is not illegal.

What matters is the set of possible "writes" that given "read" is allowed to observe.

In this case, simple transitivity is enough to establish hb.

As Gil highlights, "negations" are a bit hard to deal with, and Mr.Alexey converts the negations to a positive clauses: https://shipilev.net/blog/2014/jmm-pragmatics/#_happens_before

Shipilёv> Therefore, in the absence of races, we can only see the latest write in HB.

Note: we (as programmers) do not really care HOW the runtime and/or CPU would make that possible. We have guarantees from JVM that "in the absence of races, we can only see the latest write in HB".

CPU can reorder things and/or execute multiple instructions in parallel. I don't really need to know the way it is implemented in order to prove that "CHM is fine to share objects across threads".

Just in case: there are two writes for w.value field.

"write1" is "the write of default value" which "synchronizes-with the first action in every thread" (see 17.4.4.) + "If an action x synchronizes-with a following action y, then we also have hb(x, y)." (see 17.4.5)

"write2" is "w.value=42"

"value=0" (write1) happens-before "w.value=42" (write2) by definition (17.4.4+17.4.5)

w.value=42 happens-before map.put (program order implies happens-before)

read of u.value happens-before map.put (CHM guarantees that)

In other words, "w.value=42" is the latest write in hb order for u.value read, so u.value must observe 42.

JRE must ensure that the only possible outcome for the program in question is 42.

Vladimir

[John Hening]

Gil and Vladimir, thanks a lot for your time and explanation. This discussion was very fruitful, at least for me.

[Kodewerk]

This is all too confusing… can’t you just single thread everything?

— Kirk

--
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.

[Dr Heinz M. Kabutz]

Or get rid of pipelining and caches ... :-D

--

Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion
JavaOne Rockstar Speaker
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz

[Michael Barker]

And optimising compilers.

[Jean-Philippe BEMPEL]

Thanks Vladimir for your thoroughly explanation, I need to re read the Aleksey's JMM pragmatics 10 times more I guess 🙄

--

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.

[Roman Leventov]

Does anybody understand what could go wrong if that CHM.Node.value volatile write is relaxed to storeFence + normal write, and no fence at all within the CHM.Node constructor (Hotspot JVM only)?

On Mon, 19 Nov 2018, 10:28 Jean-Philippe BEMPEL <jean-p...@bempel.fr wrote:

Thanks Vladimir for your thoroughly explanation, I need to re read the Aleksey's JMM pragmatics 10 times more I guess 🙄

On Sun, Nov 18, 2018 at 7:35 PM Vladimir Sitnikov <sitnikov...@gmail.com> wrote:

Jean-Philippe>is a write to value but no read of this va lue inside the same thread, so the write is free to be reordered

[Francesco Nigro]

It would matter if you add some logic around it:

//put of a value in the map with just a lazySet/putOrdered etc etc

If (anyConsumerIsSleeping()) {

   wakeUpConsumers();

}

If you won't have a full barrier the compile *could* reorder anyConsumerIsSleeping() ahead of the map.put, making possible to miss some consumer that is gone asleep :)

The consumer example is more related to a queue case, but the idea is the same: you can't rely on any sequential consistent order on that operation (the volatile store), because without a volatile store that order doesn't exist.

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

For more options, visit https://groups.google.com/d/optout.

--
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-sympathy+unsub...@googlegroups.com.

[Roman Leventov]

On the other hand, CHM didn't guarantee volatile store semantics of put(), it only guaranteed HB between get() and put() with the same key. However, it's the same for java.util.concurrent's Queue implementations, such as ConcurrentLinkedQueue: Javadoc doesn't say that queue.offer() and poll() are synchronization actions.

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.

--
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.

--
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.

[Francesco Nigro]

Good point, you're totally right: I have checked the CHM Javadoc and it won't say anything about "total" ordered operations.

"By contract" we can't rely on such ordering: I would say that only if the map consumer is per-key we can assume that what I have written in the past answer is correct.

You received this message because you are subscribed to a topic in the Google Groups "mechanical-sympathy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/mechanical-sympathy/lxlJBA49EoM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to mechanical-symp...@googlegroups.com.

[Travis Downs]

It's good that sanity prevailed and that HB applies between inserts and subsequent gets (and before that to any operations on the object such as the construction).

Another way of looking at it is that almost every use of CHM would be race if this wasn't the case! After all, very few objects are designed to me unsafely published, and if there was no HB propagation through CHM, how would you ever safely access an object put into a CHM by on thread and retrieved by another. The only way it could work would be if there was some other HB edge between the producer and consumer, e.g., you put a bunch of things in the CHM, and then started some other threads (so there is a HB edge due to thread start) and then accessed those objects - but you couldn't access any new object inserted, and in that case why not just pass the list of objects to the threads directly in any old non-concurrent structure.

So the OP's original question is far from an obscure one: it applies to the overwhelming majority of CHM use. CHM would be most unusable if it didn't work like that.

[Steven Stewart-Gallus]

By the way, how to put an element safely (fully constructed) to ConcurrentHashMap if we need mutable object? I see only one solution (by adding a "mock" final field):

Seriously no. Just use a VarHandle fence