AtomicReference.updateAndGet() mandatory updating

classic Classic list List threaded Threaded
125 messages Options
1234 ... 7
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

AtomicReference.updateAndGet() mandatory updating

Mike Duigou
Currently the AtomicReference updateAndGet implementation will
unconditionally perform a compareAndSet using the result of the update
function.

public final V updateAndGet(UnaryOperator<V> updateFunction) {
   V prev, next;
   do {
     prev = get();
     next = updateFunction.apply(prev);
   } while (!compareAndSet(prev, next));
   return next;
}

I find that I write a lot of update functions which only occasionally
change the value. For these cases I wonder if it would be reasonable to
skip the update if the value of next is unchanged from previous. A
proposed alternative (there are analogues for Integer and Long).

public final V updateAndGet(UnaryOperator<V> updateFunction) {
   V prev, next;
   do {
     prev = get();
     next = updateFunction.apply(prev);
   } while (prev != next && !compareAndSet(prev, next));
   return next;
}

The cases to consider are:

1. prev == value == next :: Nothing changed.

In this case omitting the compareAndSet is a useful optimization. No
difference for external observer.


2. (prev == value) != next :: Only next changed

In this case the compareAndSet would be performed and succeed as prev ==
value. No difference for external observer.


3. prev != value != next :: Both next and value changed. A concurrent
modification.

In this case the compareAndSet would be performed and will fail as prev
!= val. No difference for external observer.


4. (prev == next) != value :: Only value changed. A concurrent
modification.

In the original implementation the compareAndSet would fail resulting in
another update attempt. In proposed implementation the compareAndSet
would not be attempted and the value returned would be unchanged. The
concurrent modification of value is ignored. Surely this is wrong! It
appears wrong because some other thread beat us and updated the value.
The question is whether our thread could tell the difference between the
call it made to updateAndGet completing first and a concurrent update
being ignored. Other than via side-effects in updateFunction it does not
appear that it could. To an external observer this case is
indistinguishable from the first where there was no concurrent update.
Even if there is a concurrent update it will appear to callers that
non-mutating updates always completed first.

Useful? Wrongheaded?

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

David Holmes-6
Hi Mike,

What you suggest is too racy. As soon as you call get() the value may change such that you do want to update it - even if back to what it was previously. Only by doing the CAS can you be sure that nothing changed and you truly updated things in the manner expected.

Cheers,
David

> -----Original Message-----
> From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Mike Duigou
> Sent: Wednesday, May 24, 2017 9:59 AM
> To: Concurrency Interest <[hidden email]>
> Subject: [concurrency-interest] AtomicReference.updateAndGet() mandatory updating
>
> Currently the AtomicReference updateAndGet implementation will unconditionally perform a compareAndSet using the result of the
> update function.
>
> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>    V prev, next;
>    do {
>      prev = get();
>      next = updateFunction.apply(prev);
>    } while (!compareAndSet(prev, next));
>    return next;
> }
>
> I find that I write a lot of update functions which only occasionally change the value. For these cases I wonder if it would be reasonable
> to skip the update if the value of next is unchanged from previous. A proposed alternative (there are analogues for Integer and Long).
>
> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>    V prev, next;
>    do {
>      prev = get();
>      next = updateFunction.apply(prev);
>    } while (prev != next && !compareAndSet(prev, next));
>    return next;
> }
>
> The cases to consider are:
>
> 1. prev == value == next :: Nothing changed.
>
> In this case omitting the compareAndSet is a useful optimization. No difference for external observer.
>
>
> 2. (prev == value) != next :: Only next changed
>
> In this case the compareAndSet would be performed and succeed as prev ==
> value. No difference for external observer.
>
>
> 3. prev != value != next :: Both next and value changed. A concurrent
> modification.
>
> In this case the compareAndSet would be performed and will fail as prev
> != val. No difference for external observer.
>
>
> 4. (prev == next) != value :: Only value changed. A concurrent
> modification.
>
> In the original implementation the compareAndSet would fail resulting in
> another update attempt. In proposed implementation the compareAndSet
> would not be attempted and the value returned would be unchanged. The
> concurrent modification of value is ignored. Surely this is wrong! It
> appears wrong because some other thread beat us and updated the value.
> The question is whether our thread could tell the difference between the
> call it made to updateAndGet completing first and a concurrent update
> being ignored. Other than via side-effects in updateFunction it does not
> appear that it could. To an external observer this case is
> indistinguishable from the first where there was no concurrent update.
> Even if there is a concurrent update it will appear to callers that
> non-mutating updates always completed first.
>
> Useful? Wrongheaded?
>
> Mike
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatoryupdating

Dmitry Zaslavsky

I don’t see how this is more racy than the original code…

As soon as you call compareAndSet() the value might have changed.

 

I have a place in my code, where this make a significant performance difference on x86.

Volatile read is just a read and a single compare with predicted branch returns most of the time.

 

Sent from Mail for Windows 10

 

From: [hidden email]
Sent: Tuesday, May 23, 2017 8:16 PM
To: [hidden email]; [hidden email]
Subject: Re: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

Hi Mike,

 

What you suggest is too racy. As soon as you call get() the value may change such that you do want to update it - even if back to what it was previously. Only by doing the CAS can you be sure that nothing changed and you truly updated things in the manner expected.

 

Cheers,

David

 

> -----Original Message-----

> From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Mike Duigou

> Sent: Wednesday, May 24, 2017 9:59 AM

> To: Concurrency Interest <[hidden email]>

> Subject: [concurrency-interest] AtomicReference.updateAndGet() mandatory updating

>

> Currently the AtomicReference updateAndGet implementation will unconditionally perform a compareAndSet using the result of the

> update function.

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (!compareAndSet(prev, next));

>    return next;

> }

>

> I find that I write a lot of update functions which only occasionally change the value. For these cases I wonder if it would be reasonable

> to skip the update if the value of next is unchanged from previous. A proposed alternative (there are analogues for Integer and Long).

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (prev != next && !compareAndSet(prev, next));

>    return next;

> }

>

> The cases to consider are:

>

> 1. prev == value == next :: Nothing changed.

>

> In this case omitting the compareAndSet is a useful optimization. No difference for external observer.

>

>

> 2. (prev == value) != next :: Only next changed

>

> In this case the compareAndSet would be performed and succeed as prev ==

> value. No difference for external observer.

>

>

> 3. prev != value != next :: Both next and value changed. A concurrent

> modification.

>

> In this case the compareAndSet would be performed and will fail as prev

> != val. No difference for external observer.

>

>

> 4. (prev == next) != value :: Only value changed. A concurrent

> modification.

>

> In the original implementation the compareAndSet would fail resulting in

> another update attempt. In proposed implementation the compareAndSet

> would not be attempted and the value returned would be unchanged. The

> concurrent modification of value is ignored. Surely this is wrong! It

> appears wrong because some other thread beat us and updated the value.

> The question is whether our thread could tell the difference between the

> call it made to updateAndGet completing first and a concurrent update

> being ignored. Other than via side-effects in updateFunction it does not

> appear that it could. To an external observer this case is

> indistinguishable from the first where there was no concurrent update.

> Even if there is a concurrent update it will appear to callers that

> non-mutating updates always completed first.

>

> Useful? Wrongheaded?

>

> Mike

> _______________________________________________

> Concurrency-interest mailing list

> [hidden email]

> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 

_______________________________________________

Concurrency-interest mailing list

[hidden email]

http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatoryupdating

David Holmes-6

The value may change as soon as compareAndSet succeeds but at least you know that the value did not change after the get() and you did not miss an update that you should have “corrected”. Obviously depending on how you use this API this may be a non-issue, but the API doesn’t know your usecase.

 

David

 

From: Dmitry Zaslavsky [mailto:[hidden email]]
Sent: Wednesday, May 24, 2017 10:20 AM
To: [hidden email]; 'Mike Duigou' <[hidden email]>; 'Concurrency Interest' <[hidden email]>
Subject: RE: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

I don’t see how this is more racy than the original code…

As soon as you call compareAndSet() the value might have changed.

 

I have a place in my code, where this make a significant performance difference on x86.

Volatile read is just a read and a single compare with predicted branch returns most of the time.

 

Sent from Mail for Windows 10

 

From: [hidden email]
Sent: Tuesday, May 23, 2017 8:16 PM
To: [hidden email]; [hidden email]
Subject: Re: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

Hi Mike,

 

What you suggest is too racy. As soon as you call get() the value may change such that you do want to update it - even if back to what it was previously. Only by doing the CAS can you be sure that nothing changed and you truly updated things in the manner expected.

 

Cheers,

David

 

> -----Original Message-----

> From: Concurrency-interest [[hidden email]] On Behalf Of Mike Duigou

> Sent: Wednesday, May 24, 2017 9:59 AM

> To: Concurrency Interest <[hidden email]>

> Subject: [concurrency-interest] AtomicReference.updateAndGet() mandatory updating

>

> Currently the AtomicReference updateAndGet implementation will unconditionally perform a compareAndSet using the result of the

> update function.

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (!compareAndSet(prev, next));

>    return next;

> }

>

> I find that I write a lot of update functions which only occasionally change the value. For these cases I wonder if it would be reasonable

> to skip the update if the value of next is unchanged from previous. A proposed alternative (there are analogues for Integer and Long).

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (prev != next && !compareAndSet(prev, next));

>    return next;

> }

>

> The cases to consider are:

>

> 1. prev == value == next :: Nothing changed.

>

> In this case omitting the compareAndSet is a useful optimization. No difference for external observer.

>

>

> 2. (prev == value) != next :: Only next changed

>

> In this case the compareAndSet would be performed and succeed as prev ==

> value. No difference for external observer.

>

>

> 3. prev != value != next :: Both next and value changed. A concurrent

> modification.

>

> In this case the compareAndSet would be performed and will fail as prev

> != val. No difference for external observer.

>

>

> 4. (prev == next) != value :: Only value changed. A concurrent

> modification.

>

> In the original implementation the compareAndSet would fail resulting in

> another update attempt. In proposed implementation the compareAndSet

> would not be attempted and the value returned would be unchanged. The

> concurrent modification of value is ignored. Surely this is wrong! It

> appears wrong because some other thread beat us and updated the value.

> The question is whether our thread could tell the difference between the

> call it made to updateAndGet completing first and a concurrent update

> being ignored. Other than via side-effects in updateFunction it does not

> appear that it could. To an external observer this case is

> indistinguishable from the first where there was no concurrent update.

> Even if there is a concurrent update it will appear to callers that

> non-mutating updates always completed first.

>

> Useful? Wrongheaded?

>

> Mike

> _______________________________________________

> Concurrency-interest mailing list

> [hidden email]

> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 

_______________________________________________

Concurrency-interest mailing list

[hidden email]

http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatoryupdating

David Holmes-6

No you are right – the difference in behavior is not observable (except perhaps by the updateFunction – which would be odd in itself).

 

I’m used to cases where there will always be a change in value. 😊

 

David

 

From: Concurrency-interest [mailto:[hidden email]] On Behalf Of David Holmes
Sent: Wednesday, May 24, 2017 10:29 AM
To: 'Dmitry Zaslavsky' <[hidden email]>; 'Mike Duigou' <[hidden email]>; 'Concurrency Interest' <[hidden email]>
Subject: Re: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

The value may change as soon as compareAndSet succeeds but at least you know that the value did not change after the get() and you did not miss an update that you should have “corrected”. Obviously depending on how you use this API this may be a non-issue, but the API doesn’t know your usecase.

 

David

 

From: Dmitry Zaslavsky [[hidden email]]
Sent: Wednesday, May 24, 2017 10:20 AM
To: [hidden email]; 'Mike Duigou' <[hidden email]>; 'Concurrency Interest' <[hidden email]>
Subject: RE: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

I don’t see how this is more racy than the original code…

As soon as you call compareAndSet() the value might have changed.

 

I have a place in my code, where this make a significant performance difference on x86.

Volatile read is just a read and a single compare with predicted branch returns most of the time.

 

Sent from Mail for Windows 10

 

From: [hidden email]
Sent: Tuesday, May 23, 2017 8:16 PM
To: [hidden email]; [hidden email]
Subject: Re: [concurrency-interest] AtomicReference.updateAndGet() mandatoryupdating

 

Hi Mike,

 

What you suggest is too racy. As soon as you call get() the value may change such that you do want to update it - even if back to what it was previously. Only by doing the CAS can you be sure that nothing changed and you truly updated things in the manner expected.

 

Cheers,

David

 

> -----Original Message-----

> From: Concurrency-interest [[hidden email]] On Behalf Of Mike Duigou

> Sent: Wednesday, May 24, 2017 9:59 AM

> To: Concurrency Interest <[hidden email]>

> Subject: [concurrency-interest] AtomicReference.updateAndGet() mandatory updating

>

> Currently the AtomicReference updateAndGet implementation will unconditionally perform a compareAndSet using the result of the

> update function.

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (!compareAndSet(prev, next));

>    return next;

> }

>

> I find that I write a lot of update functions which only occasionally change the value. For these cases I wonder if it would be reasonable

> to skip the update if the value of next is unchanged from previous. A proposed alternative (there are analogues for Integer and Long).

>

> public final V updateAndGet(UnaryOperator<V> updateFunction) {

>    V prev, next;

>    do {

>      prev = get();

>      next = updateFunction.apply(prev);

>    } while (prev != next && !compareAndSet(prev, next));

>    return next;

> }

>

> The cases to consider are:

>

> 1. prev == value == next :: Nothing changed.

>

> In this case omitting the compareAndSet is a useful optimization. No difference for external observer.

>

>

> 2. (prev == value) != next :: Only next changed

>

> In this case the compareAndSet would be performed and succeed as prev ==

> value. No difference for external observer.

>

>

> 3. prev != value != next :: Both next and value changed. A concurrent

> modification.

>

> In this case the compareAndSet would be performed and will fail as prev

> != val. No difference for external observer.

>

>

> 4. (prev == next) != value :: Only value changed. A concurrent

> modification.

>

> In the original implementation the compareAndSet would fail resulting in

> another update attempt. In proposed implementation the compareAndSet

> would not be attempted and the value returned would be unchanged. The

> concurrent modification of value is ignored. Surely this is wrong! It

> appears wrong because some other thread beat us and updated the value.

> The question is whether our thread could tell the difference between the

> call it made to updateAndGet completing first and a concurrent update

> being ignored. Other than via side-effects in updateFunction it does not

> appear that it could. To an external observer this case is

> indistinguishable from the first where there was no concurrent update.

> Even if there is a concurrent update it will appear to callers that

> non-mutating updates always completed first.

>

> Useful? Wrongheaded?

>

> Mike

> _______________________________________________

> Concurrency-interest mailing list

> [hidden email]

> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 

_______________________________________________

Concurrency-interest mailing list

[hidden email]

http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Andrew Haley
In reply to this post by Mike Duigou
On 24/05/17 00:58, Mike Duigou wrote:
> I find that I write a lot of update functions which only occasionally
> change the value. For these cases I wonder if it would be reasonable to
> skip the update if the value of next is unchanged from previous.

I don't think so, because the update has the effect of a volatile
write.  If you skip the update you lose the happens-before ordering
of that write.

Andrew.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Justin Sampson
Andrew Haley wrote:
> Mike Duigou wrote:
> > I find that I write a lot of update functions which only occasionally
> > change the value. For these cases I wonder if it would be reasonable to
> > skip the update if the value of next is unchanged from previous.
>
> I don't think so, because the update has the effect of a volatile
> write. If you skip the update you lose the happens-before ordering
> of that write.

That's strictly true (the memory barriers come out different), but no
algorithm could actually rely on the difference. The reading thread can't
tell if it's reading after the write (and therefore can depend on the
happens-before) or reading before the write (and therefore cannot), since
it sees the same value in either case.

This kind of optimization is already done in some places in the JDK, such
as AtomicStampedReference and AtomicMarkableReference, both of which skip
the write if the current value is already equal to the new value in set(),
compareAndSet(), etc.

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Mike Duigou
That's my view of this optimization as well; the writes that occur do
change but only in ways that nobody should be able to rely upon.
Assuming the proposed change to getAndUpdate seemed reasonable to folks
I planned to next suggest:

replace:

public final boolean compareAndSet(V expect, V update) {
    return unsafe.compareAndSwapObject(this, valueOffset, expect,
update);
}

with:

public final boolean compareAndSet(V expect, V update) {
     return expect != update
        ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
        : expect != value ? false : true;
}

For both the proposed updateAndGet and compareAndSet the goal is to
avoid expensive volatile writes when the value is not actually changing.

Mike

On 2017-05-24 12:38, Justin Sampson wrote:

> Andrew Haley wrote:
>> Mike Duigou wrote:
>> > I find that I write a lot of update functions which only occasionally
>> > change the value. For these cases I wonder if it would be reasonable to
>> > skip the update if the value of next is unchanged from previous.
>>
>> I don't think so, because the update has the effect of a volatile
>> write. If you skip the update you lose the happens-before ordering
>> of that write.
>
> That's strictly true (the memory barriers come out different), but no
> algorithm could actually rely on the difference. The reading thread
> can't
> tell if it's reading after the write (and therefore can depend on the
> happens-before) or reading before the write (and therefore cannot),
> since
> it sees the same value in either case.
>
> This kind of optimization is already done in some places in the JDK,
> such
> as AtomicStampedReference and AtomicMarkableReference, both of which
> skip
> the write if the current value is already equal to the new value in
> set(),
> compareAndSet(), etc.
>
> Cheers,
> Justin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Gregg Wonderly-3
In reply to this post by Justin Sampson
One of the things that ends up happening, is that people to start trying to do the optimizations that you are doing here, in their own code, knowing what other fences are guaranteed to be happening.  As soon as you make this a conditional fence, you force the user to always use their own fence if they were relying on this fence, and now they have two fences that are dropped when they only ever needed one.  And, if you force them to wrap this operation into an object that can mediate the details of whether or not a fence was actually encountered in the actions of the API, they are recreating exactly the logic you have in your code, and then they will simply be prepared to just go ahead and skip out on providing the JRE provided implementation because it is now a barrier to simple programming models that have simple, dependable behavior.

At some level, there is only so many optimizations that should be done behind the users back.  Surprises like this with disappearing fences will suddenly break a lot of software for nearly unexplainable reasons without deep dives into implementation details and other nuances of behavior which just used to work because the fence was always there.

To put this another way, if the runtime environment is ever going to provide fences than the circumstance of doing that or not doing that should be completely controllable by the developer so that there are no surprises and no change in correctness happening because of things like this going on behind the scenes.

Gregg

> On May 24, 2017, at 4:50 PM, Mike Duigou <[hidden email]> wrote:
>
> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>
> replace:
>
> public final boolean compareAndSet(V expect, V update) {
>   return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
> }
>
> with:
>
> public final boolean compareAndSet(V expect, V update) {
>    return expect != update
>       ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>       : expect != value ? false : true;
> }
>
> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>
> Mike
>
> On 2017-05-24 12:38, Justin Sampson wrote:
>> Andrew Haley wrote:
>>> Mike Duigou wrote:
>>> > I find that I write a lot of update functions which only occasionally
>>> > change the value. For these cases I wonder if it would be reasonable to
>>> > skip the update if the value of next is unchanged from previous.
>>> I don't think so, because the update has the effect of a volatile
>>> write. If you skip the update you lose the happens-before ordering
>>> of that write.
>> That's strictly true (the memory barriers come out different), but no
>> algorithm could actually rely on the difference. The reading thread can't
>> tell if it's reading after the write (and therefore can depend on the
>> happens-before) or reading before the write (and therefore cannot), since
>> it sees the same value in either case.
>> This kind of optimization is already done in some places in the JDK, such
>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>> the write if the current value is already equal to the new value in set(),
>> compareAndSet(), etc.
>> Cheers,
>> Justin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Gil Tene-2
In reply to this post by Mike Duigou
The memory semantics of updateAndGet() need to be captured in its JavaDoc. In this sense it is no different from compareAndSet(), which currently defines the memory semantics:

http://download.java.net/java/jdk9/docs/api/java/util/concurrent/atomic/AtomicReference.html#compareAndSet-V-V- says:
"Atomically sets the value to newValue if the current value == expectedValue, with memory effects as specified by VarHandle.compareAndSet(java.lang.Object…)."

and under compareAndSet in VarHandle (http://download.java.net/java/jdk9/docs/api/java/lang/invoke/VarHandle.html#compareAndSet-java.lang.Object…- ) it currently says:
"Atomically sets the value of a variable to the newValue with the memory semantics of setVolatile(java.lang.Object...) if the variable's current value, referred to as the witness value, == the expectedValue, as accessed with the memory semantics of getVolatile(java.lang.Object…)."

However,
http://download.java.net/java/jdk9/docs/api/java/util/concurrent/atomic/AtomicReference.html#updateAndGet-java.util.function.UnaryOperator- says nothing about the memory semantics. It should. And it should probably say it either like this:

"Atomically updates the current value with the results of applying the given function with memory semntics of VarHandle.setVolatile(java.lang.Object..), returning the updated value, as accessed with the memory semantics of getVolatile(java.lang.Object…). The function should be side-effect-free, since it may be re-applied when attempted updates fail due to contention among threads."

or like this:

"Atomically updates the current value with the results of applying the given function with memory semntics of VarHandle.setVolatile(java.lang.Object..) if the variable's current value, referred to as the witness value, != the existing value, as accessed with the memory semantics of getVolatile(java.lang.Object…), returning the updated value. The function should be side-effect-free, since it may be re-applied when attempted updates fail due to contention among threads."

The choice between the two above definitions will determine whether or not the suggested optimization is allowed...

Once could argue that the backwards compatible (with java 8) version would be the first form (i.e. always equivalent to both a volatile write and a volatile read), since the Java 8 semantics are defined that way for all of of j.u.c.atomic ((https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/package-summary.html): "… • compareAndSet and all other read-and-update operations such as getAndIncrement have the memory effects of both reading and writing volatile variables. ". However, since Java 9 seems to be relaxing the semantics for compareAndSet() [in an arguably not-fully-compatible way, since the new Java 9 compareAndSet semantics are somewhat weaker], we can/should do that consistently across the board.

In any case, all of the various atomic operations *should* have defined memory semantics. These used to be globally captured in the j.u.c.atomic JavaDoc in Java 8. But with Java 9, the memory semantics notes were removed from j.u.c.atomic and are "punted" by most individual method definitions to VarHandle. However, this punting is not universal, and arguably leaves the memory semantics of several operations in j.u.c.atomic classes unspecified, including getAndUpdate, upodateAndGet, getAndAccumulate, accumulateAndGet [all of which did have a defined memory semantics behavior in Java 8, since they all fit under the "...all other read-and-update.." catchall in j.u.c.atomic].

— Gil.

> On May 24, 2017, at 2:50 PM, Mike Duigou <[hidden email]> wrote:
>
> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>
> replace:
>
> public final boolean compareAndSet(V expect, V update) {
>   return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
> }
>
> with:
>
> public final boolean compareAndSet(V expect, V update) {
>    return expect != update
>       ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>       : expect != value ? false : true;
> }
>
> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>
> Mike
>
> On 2017-05-24 12:38, Justin Sampson wrote:
>> Andrew Haley wrote:
>>> Mike Duigou wrote:
>>> > I find that I write a lot of update functions which only occasionally
>>> > change the value. For these cases I wonder if it would be reasonable to
>>> > skip the update if the value of next is unchanged from previous.
>>> I don't think so, because the update has the effect of a volatile
>>> write. If you skip the update you lose the happens-before ordering
>>> of that write.
>> That's strictly true (the memory barriers come out different), but no
>> algorithm could actually rely on the difference. The reading thread can't
>> tell if it's reading after the write (and therefore can depend on the
>> happens-before) or reading before the write (and therefore cannot), since
>> it sees the same value in either case.
>> This kind of optimization is already done in some places in the JDK, such
>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>> the write if the current value is already equal to the new value in set(),
>> compareAndSet(), etc.
>> Cheers,
>> Justin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Brian S O'Neill-3
In reply to this post by Mike Duigou
Have you had a chance to take a look at the Java 9 version of this method?

     public final V updateAndGet(UnaryOperator<V> updateFunction) {
         V prev = get(), next = null;
         for (boolean haveNext = false;;) {
             if (!haveNext)
                 next = updateFunction.apply(prev);
             if (weakCompareAndSetVolatile(prev, next))
                 return next;
             haveNext = (prev == (prev = get()));
         }
     }

It doesn't omit the CAS, but it does omit calling the function
needlessly if prev hasn't changed. I wonder what effect the weak CAS
has. For which platforms does it make a difference?


On 2017-05-23 04:58 PM, Mike Duigou wrote:

> Currently the AtomicReference updateAndGet implementation will
> unconditionally perform a compareAndSet using the result of the update
> function.
>
> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>    V prev, next;
>    do {
>      prev = get();
>      next = updateFunction.apply(prev);
>    } while (!compareAndSet(prev, next));
>    return next;
> }
>
> I find that I write a lot of update functions which only occasionally
> change the value. For these cases I wonder if it would be reasonable to
> skip the update if the value of next is unchanged from previous. A
> proposed alternative (there are analogues for Integer and Long).
>
> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>    V prev, next;
>    do {
>      prev = get();
>      next = updateFunction.apply(prev);
>    } while (prev != next && !compareAndSet(prev, next));
>    return next;
> }
>
> The cases to consider are:
>
> 1. prev == value == next :: Nothing changed.
>
> In this case omitting the compareAndSet is a useful optimization. No
> difference for external observer.
>
>
> 2. (prev == value) != next :: Only next changed
>
> In this case the compareAndSet would be performed and succeed as prev ==
> value. No difference for external observer.
>
>
> 3. prev != value != next :: Both next and value changed. A concurrent
> modification.
>
> In this case the compareAndSet would be performed and will fail as prev
> != val. No difference for external observer.
>
>
> 4. (prev == next) != value :: Only value changed. A concurrent
> modification.
>
> In the original implementation the compareAndSet would fail resulting in
> another update attempt. In proposed implementation the compareAndSet
> would not be attempted and the value returned would be unchanged. The
> concurrent modification of value is ignored. Surely this is wrong! It
> appears wrong because some other thread beat us and updated the value.
> The question is whether our thread could tell the difference between the
> call it made to updateAndGet completing first and a concurrent update
> being ignored. Other than via side-effects in updateFunction it does not
> appear that it could. To an external observer this case is
> indistinguishable from the first where there was no concurrent update.
> Even if there is a concurrent update it will appear to callers that
> non-mutating updates always completed first.
>
> Useful? Wrongheaded?
>
> Mike
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Gil Tene-2

> On May 24, 2017, at 3:51 PM, Brian S O'Neill <[hidden email]> wrote:
>
> Have you had a chance to take a look at the Java 9 version of this method?
>
>    public final V updateAndGet(UnaryOperator<V> updateFunction) {
>        V prev = get(), next = null;
>        for (boolean haveNext = false;;) {
>            if (!haveNext)
>                next = updateFunction.apply(prev);
>            if (weakCompareAndSetVolatile(prev, next))
>                return next;
>            haveNext = (prev == (prev = get()));
>        }
>    }
>
> It doesn't omit the CAS, but it does omit calling the function needlessly if prev hasn't changed. I wonder what effect the weak CAS has. For which platforms does it make a difference?

The weak CAS is allowed to spuriously fail (i.e. fail even when the the expected value matches). On architectures that do not directly support a non-spuriously-failing CAS in hardware (e.g. architectures that only have LL/SC variants, such as ARM pre-v8, and some PowerPC and MIPS, etc.) this is cheaper to implement than a proper CAS.

>
>
> On 2017-05-23 04:58 PM, Mike Duigou wrote:
>> Currently the AtomicReference updateAndGet implementation will unconditionally perform a compareAndSet using the result of the update function.
>> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>>   V prev, next;
>>   do {
>>     prev = get();
>>     next = updateFunction.apply(prev);
>>   } while (!compareAndSet(prev, next));
>>   return next;
>> }
>> I find that I write a lot of update functions which only occasionally change the value. For these cases I wonder if it would be reasonable to skip the update if the value of next is unchanged from previous. A proposed alternative (there are analogues for Integer and Long).
>> public final V updateAndGet(UnaryOperator<V> updateFunction) {
>>   V prev, next;
>>   do {
>>     prev = get();
>>     next = updateFunction.apply(prev);
>>   } while (prev != next && !compareAndSet(prev, next));
>>   return next;
>> }
>> The cases to consider are:
>> 1. prev == value == next :: Nothing changed.
>> In this case omitting the compareAndSet is a useful optimization. No difference for external observer.
>> 2. (prev == value) != next :: Only next changed
>> In this case the compareAndSet would be performed and succeed as prev == value. No difference for external observer.
>> 3. prev != value != next :: Both next and value changed. A concurrent modification.
>> In this case the compareAndSet would be performed and will fail as prev != val. No difference for external observer.
>> 4. (prev == next) != value :: Only value changed. A concurrent modification.
>> In the original implementation the compareAndSet would fail resulting in another update attempt. In proposed implementation the compareAndSet would not be attempted and the value returned would be unchanged. The concurrent modification of value is ignored. Surely this is wrong! It appears wrong because some other thread beat us and updated the value. The question is whether our thread could tell the difference between the call it made to updateAndGet completing first and a concurrent update being ignored. Other than via side-effects in updateFunction it does not appear that it could. To an external observer this case is indistinguishable from the first where there was no concurrent update. Even if there is a concurrent update it will appear to callers that non-mutating updates always completed first.
>> Useful? Wrongheaded?
>> Mike
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Alex Otenko
In reply to this post by Mike Duigou
This is a bad idea.

Now there is no guarantee that the synchronizes-with edge exists.

Alex

> On 24 May 2017, at 22:50, Mike Duigou <[hidden email]> wrote:
>
> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>
> replace:
>
> public final boolean compareAndSet(V expect, V update) {
>   return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
> }
>
> with:
>
> public final boolean compareAndSet(V expect, V update) {
>    return expect != update
>       ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>       : expect != value ? false : true;
> }
>
> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>
> Mike
>
> On 2017-05-24 12:38, Justin Sampson wrote:
>> Andrew Haley wrote:
>>> Mike Duigou wrote:
>>> > I find that I write a lot of update functions which only occasionally
>>> > change the value. For these cases I wonder if it would be reasonable to
>>> > skip the update if the value of next is unchanged from previous.
>>> I don't think so, because the update has the effect of a volatile
>>> write. If you skip the update you lose the happens-before ordering
>>> of that write.
>> That's strictly true (the memory barriers come out different), but no
>> algorithm could actually rely on the difference. The reading thread can't
>> tell if it's reading after the write (and therefore can depend on the
>> happens-before) or reading before the write (and therefore cannot), since
>> it sees the same value in either case.
>> This kind of optimization is already done in some places in the JDK, such
>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>> the write if the current value is already equal to the new value in set(),
>> compareAndSet(), etc.
>> Cheers,
>> Justin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Gil Tene-2

> On May 25, 2017, at 12:35 AM, Alex Otenko <[hidden email]> wrote:
>
> This is a bad idea.
>
> Now there is no guarantee that the synchronizes-with edge exists.

The current Java 9 specification (in the JavaDoc) of AtomicReference.updateAndGet() doesn't say there is such an edge (the Java 8 one did, but the current Java 9 one doesn't). So this is valid with the current spec'ed behavior. The spec is probably wrong and should be changed to document the expected memory semantics in any case, and depending on what those are, the suggested optimization will either be ok or wrong to do.

>
> Alex
>
>> On 24 May 2017, at 22:50, Mike Duigou <[hidden email]> wrote:
>>
>> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>>
>> replace:
>>
>> public final boolean compareAndSet(V expect, V update) {
>>  return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
>> }
>>
>> with:
>>
>> public final boolean compareAndSet(V expect, V update) {
>>   return expect != update
>>      ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>>      : expect != value ? false : true;
>> }
>>
>> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>>
>> Mike
>>
>> On 2017-05-24 12:38, Justin Sampson wrote:
>>> Andrew Haley wrote:
>>>> Mike Duigou wrote:
>>>>> I find that I write a lot of update functions which only occasionally
>>>>> change the value. For these cases I wonder if it would be reasonable to
>>>>> skip the update if the value of next is unchanged from previous.
>>>> I don't think so, because the update has the effect of a volatile
>>>> write. If you skip the update you lose the happens-before ordering
>>>> of that write.
>>> That's strictly true (the memory barriers come out different), but no
>>> algorithm could actually rely on the difference. The reading thread can't
>>> tell if it's reading after the write (and therefore can depend on the
>>> happens-before) or reading before the write (and therefore cannot), since
>>> it sees the same value in either case.
>>> This kind of optimization is already done in some places in the JDK, such
>>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>>> the write if the current value is already equal to the new value in set(),
>>> compareAndSet(), etc.
>>> Cheers,
>>> Justin
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Alex Otenko
In reply to this post by Justin Sampson
How quickly you arrived at “no algorithm whatsoever”! :-)

x=1;
y.compareAndSet(e,v)

Under assumption that there are infinitely many volatile reads of y, the return from compareAndSet is a witness that there exists a read in the future that synchronizes-with this invocation of compareAndSet.

You cannot argue that sometimes you can skip the volatile store semantics on what would be a successful compareAndSet - because then the stores preceding compareAndSet are not guaranteed to be visible - ever. This optimization is a platform-specific decision.


You can argue about what happens if compareAndSet fails. My take is it should still have volatile store semantics - ie should be equivalent to the store of the value that is already there, so it appears unmodified, but synchronizes-with edges can be established.


Alex

> On 24 May 2017, at 20:38, Justin Sampson <[hidden email]> wrote:
>
> Andrew Haley wrote:
>> Mike Duigou wrote:
>>> I find that I write a lot of update functions which only occasionally
>>> change the value. For these cases I wonder if it would be reasonable to
>>> skip the update if the value of next is unchanged from previous.
>>
>> I don't think so, because the update has the effect of a volatile
>> write. If you skip the update you lose the happens-before ordering
>> of that write.
>
> That's strictly true (the memory barriers come out different), but no
> algorithm could actually rely on the difference. The reading thread can't
> tell if it's reading after the write (and therefore can depend on the
> happens-before) or reading before the write (and therefore cannot), since
> it sees the same value in either case.
>
> This kind of optimization is already done in some places in the JDK, such
> as AtomicStampedReference and AtomicMarkableReference, both of which skip
> the write if the current value is already equal to the new value in set(),
> compareAndSet(), etc.
>
> Cheers,
> Justin
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Alex Otenko
In reply to this post by Gil Tene-2
Yes, your quote is a rather weak guarantee. That’s a shame.

The API should provide strong guarantees. Those who want them weaker, should do their own checks. eg expected == stored value is easy to test to skip compareAndSet call, but is not easy (if possible at all!) to enforce a strong guarantee, if the API is unable to provide one: how do I make sure the edge exists, without ruining the value?

Besides, the old implementation of getAndSet() used to invoke compareAndSet() inside. That’s another very subtle gotcha.


Alex


> On 25 May 2017, at 09:16, Gil Tene <[hidden email]> wrote:
>
>
>> On May 25, 2017, at 12:35 AM, Alex Otenko <[hidden email]> wrote:
>>
>> This is a bad idea.
>>
>> Now there is no guarantee that the synchronizes-with edge exists.
>
> The current Java 9 specification (in the JavaDoc) of AtomicReference.updateAndGet() doesn't say there is such an edge (the Java 8 one did, but the current Java 9 one doesn't). So this is valid with the current spec'ed behavior. The spec is probably wrong and should be changed to document the expected memory semantics in any case, and depending on what those are, the suggested optimization will either be ok or wrong to do.
>
>>
>> Alex
>>
>>> On 24 May 2017, at 22:50, Mike Duigou <[hidden email]> wrote:
>>>
>>> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>>>
>>> replace:
>>>
>>> public final boolean compareAndSet(V expect, V update) {
>>> return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
>>> }
>>>
>>> with:
>>>
>>> public final boolean compareAndSet(V expect, V update) {
>>>  return expect != update
>>>     ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>>>     : expect != value ? false : true;
>>> }
>>>
>>> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>>>
>>> Mike
>>>
>>> On 2017-05-24 12:38, Justin Sampson wrote:
>>>> Andrew Haley wrote:
>>>>> Mike Duigou wrote:
>>>>>> I find that I write a lot of update functions which only occasionally
>>>>>> change the value. For these cases I wonder if it would be reasonable to
>>>>>> skip the update if the value of next is unchanged from previous.
>>>>> I don't think so, because the update has the effect of a volatile
>>>>> write. If you skip the update you lose the happens-before ordering
>>>>> of that write.
>>>> That's strictly true (the memory barriers come out different), but no
>>>> algorithm could actually rely on the difference. The reading thread can't
>>>> tell if it's reading after the write (and therefore can depend on the
>>>> happens-before) or reading before the write (and therefore cannot), since
>>>> it sees the same value in either case.
>>>> This kind of optimization is already done in some places in the JDK, such
>>>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>>>> the write if the current value is already equal to the new value in set(),
>>>> compareAndSet(), etc.
>>>> Cheers,
>>>> Justin
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> [hidden email]
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Alex Otenko
In reply to this post by Mike Duigou
More than that, you are replacing a volatile read-and-store with a volatile read, so the ordering with respect to other operations will also suffer.

It is a really bad idea.

Alex

> On 24 May 2017, at 22:50, Mike Duigou <[hidden email]> wrote:
>
> That's my view of this optimization as well; the writes that occur do change but only in ways that nobody should be able to rely upon. Assuming the proposed change to getAndUpdate seemed reasonable to folks I planned to next suggest:
>
> replace:
>
> public final boolean compareAndSet(V expect, V update) {
>   return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
> }
>
> with:
>
> public final boolean compareAndSet(V expect, V update) {
>    return expect != update
>       ? unsafe.compareAndSwapObject(this, valueOffset, expect, update)
>       : expect != value ? false : true;
> }
>
> For both the proposed updateAndGet and compareAndSet the goal is to avoid expensive volatile writes when the value is not actually changing.
>
> Mike
>
> On 2017-05-24 12:38, Justin Sampson wrote:
>> Andrew Haley wrote:
>>> Mike Duigou wrote:
>>> > I find that I write a lot of update functions which only occasionally
>>> > change the value. For these cases I wonder if it would be reasonable to
>>> > skip the update if the value of next is unchanged from previous.
>>> I don't think so, because the update has the effect of a volatile
>>> write. If you skip the update you lose the happens-before ordering
>>> of that write.
>> That's strictly true (the memory barriers come out different), but no
>> algorithm could actually rely on the difference. The reading thread can't
>> tell if it's reading after the write (and therefore can depend on the
>> happens-before) or reading before the write (and therefore cannot), since
>> it sees the same value in either case.
>> This kind of optimization is already done in some places in the JDK, such
>> as AtomicStampedReference and AtomicMarkableReference, both of which skip
>> the write if the current value is already equal to the new value in set(),
>> compareAndSet(), etc.
>> Cheers,
>> Justin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Andrew Haley
In reply to this post by Gil Tene-2
On 25/05/17 09:16, Gil Tene wrote:
>
>> On May 25, 2017, at 12:35 AM, Alex Otenko <[hidden email]> wrote:
>>
>> This is a bad idea.
>>
>> Now there is no guarantee that the synchronizes-with edge exists.
>
> The current Java 9 specification (in the JavaDoc) of AtomicReference.updateAndGet() doesn't say there is such an edge (the Java 8 one did, but the current Java 9 one doesn't). So this is valid with the current spec'ed behavior. The spec is probably wrong and should be changed to document the expected memory semantics in any case, and depending on what those are, the suggested optimization will either be
ok or wrong to do.

Ah, I see:

"compareAndSet and all other read-and-update operations such as getAndIncrement have the memory effects of both reading and writing volatile variables. "
seems to have gone.  That's a breaking spec change if there's nothing anywhere else.

Andrew.



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Doug Lea
On 05/25/2017 06:16 AM, Andrew Haley wrote:

> On 25/05/17 09:16, Gil Tene wrote:
>>
>>> On May 25, 2017, at 12:35 AM, Alex Otenko
>>> <[hidden email]> wrote:
>>>
>>> This is a bad idea.
>>>
>>> Now there is no guarantee that the synchronizes-with edge
>>> exists.
>>
>> The current Java 9 specification (in the JavaDoc) of
>> AtomicReference.updateAndGet() doesn't say there is such an edge
>> (the Java 8 one did, but the current Java 9 one doesn't).
>
> Ah, I see:
>
> "compareAndSet and all other read-and-update operations such as
> getAndIncrement have the memory effects of both reading and writing
> volatile variables. " seems to have gone.  

Thanks for pointing this out!
The "...and all other read-and-update operations" clause
inadvertently disappeared while meshing j.u.c.atomic specs
with jdk9 VarHandles
(http://download.java.net/java/jdk9/docs/api/java/lang/invoke/VarHandle.html)

The updateAndGet method is not a part of VarHandles, so is no longer
covered by any existing statement. We will need to somehow do so.

And so, Mike: Some existing code might rely on this, so the best we
could so here is replace elided volatile-write with a fullFence,
which would probably not be detectably faster.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating

Nathan & Ila Reynolds
 > The best we could so here is replace elided volatile write with a
full fence, which would probably not be detectably faster.

I definitely agree with Alex Otenko's position of keeping the
synchronizes-with edge.  I can think of several places in code where
removing this edge would cause all sorts of wacky hard-to-reproduce
issues.  Doug's suggestion I quoted above seems like a good solution.  
 From my limited perspective, his suggestion seems to keep the
synchronizes-with edge yet avoid the volatile write.  I can assure you
that replacing a volatile write with a full fence is definitely faster.  
On a highly contended cache line, eliding a volatile write will definite
improve scalability. I can think of one place in code where each write
to the cache line is very costly in terms of scalability.  I've spent a
lot of time optimizing that code to reduce the number of writes to 1
cache line.  Before this optimization, cores would sit at 100%
utilization but the internal execution pipelines were stalled waiting
for a highly contended cache line.

-Nathan

On 5/25/2017 4:39 AM, Doug Lea wrote:

> On 05/25/2017 06:16 AM, Andrew Haley wrote:
>> On 25/05/17 09:16, Gil Tene wrote:
>>>> On May 25, 2017, at 12:35 AM, Alex Otenko
>>>> <[hidden email]> wrote:
>>>>
>>>> This is a bad idea.
>>>>
>>>> Now there is no guarantee that the synchronizes-with edge
>>>> exists.
>>> The current Java 9 specification (in the JavaDoc) of
>>> AtomicReference.updateAndGet() doesn't say there is such an edge
>>> (the Java 8 one did, but the current Java 9 one doesn't).
>> Ah, I see:
>>
>> "compareAndSet and all other read-and-update operations such as
>> getAndIncrement have the memory effects of both reading and writing
>> volatile variables. " seems to have gone.
> Thanks for pointing this out!
> The "...and all other read-and-update operations" clause
> inadvertently disappeared while meshing j.u.c.atomic specs
> with jdk9 VarHandles
> (http://download.java.net/java/jdk9/docs/api/java/lang/invoke/VarHandle.html)
>
> The updateAndGet method is not a part of VarHandles, so is no longer
> covered by any existing statement. We will need to somehow do so.
>
> And so, Mike: Some existing code might rely on this, so the best we
> could so here is replace elided volatile-write with a fullFence,
> which would probably not be detectably faster.
>
> -Doug
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--
-Nathan

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
1234 ... 7
Loading...