AtomicReference weakCompareAndSet "May fail spuriously"?

classic Classic list List threaded Threaded
59 messages Options
123
Reply | Threaded
Open this post in threaded view
|

AtomicReference weakCompareAndSet "May fail spuriously"?

robertkuhar
I was strolling through the Docs one day, and came upon the JDK 1.5 Javadocs
for Class java.util.concurrent.atomic.AtomicReference.  The description for the
weakCompareAndSet method confuses me:

  public final boolean weakCompareAndSet(V expect, V update)

  Atomically set the value to the given updated value if the current
  value == the expected value. May fail spuriously.

  Parameters:
    expect - the expected value
    update - the new value
  Returns:
    true if successful.

What does "May fail spuriously" mean?  Why would it fail spuriously?  When the
spurious failures occur, is the return value always false?  Why would anyone
call this method having been warned that "spurious failure" is possible?  I
think I'm missing something here.

Bob

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: AtomicReference weakCompareAndSet "May fail spuriously"?

Doug Lea
Robert Kuhar wrote:

> I was strolling through the Docs one day, and came upon the JDK 1.5 Javadocs
> for Class java.util.concurrent.atomic.AtomicReference.  The description for the
> weakCompareAndSet method confuses me:
>
>   public final boolean weakCompareAndSet(V expect, V update)
>
>   Atomically set the value to the given updated value if the current
>   value == the expected value. May fail spuriously.
>
>   Parameters:
>     expect - the expected value
>     update - the new value
>   Returns:
>     true if successful.
>
> What does "May fail spuriously" mean?  Why would it fail spuriously?  When the
> spurious failures occur, is the return value always false?  Why would anyone
> call this method having been warned that "spurious failure" is possible?  I
> think I'm missing something here.
>

See
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html

The javadocs in the atomic package also mention that this form may be more
efficient. (At least on some processors; on most (in fact all supported by
hotspot) it actually compiles to the same code.) The reason that it may be more
efficient is that some processors perform CAS via a pair of Load-linked /
Store-conditional instructions, which may fail if some other processor
happened to write to the same cache line, among other reasons that have
nothing to do with the CAS. In some cases, this is acceptable. On
such processors, a full strong CAS must actually be coded internally
as a loop. There are a handfull of non-blocking algorithms out there
where you don't actually want that loop, so we include this method
so you can avoid it. We expect use of this method to be uncommon.

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

Re: AtomicReference weakCompareAndSet "May fail spuriously"?

Hanson Char
I've gone thru the javadoc, but would like to clarify further.

In case when the invocation of

  weakCompareAndSet

does fail, what behavior could we expect from the failure ?

1) corrupted data being set ? or
2) runtime exception or error being thrown ? or
3) the method (weakCompareAndSet) did not set the value but return true ? or
4) the method did set the value but return false ? or
5) the method just failed but the behavior is non-deterministic ?

Hanson

On 2/2/06, Doug Lea <[hidden email] > wrote:
Robert Kuhar wrote:

> I was strolling through the Docs one day, and came upon the JDK 1.5 Javadocs
> for Class java.util.concurrent.atomic.AtomicReference.  The description for the
> weakCompareAndSet method confuses me:
>
>   public final boolean weakCompareAndSet(V expect, V update)
>
>   Atomically set the value to the given updated value if the current
>   value == the expected value. May fail spuriously.
>
>   Parameters:
>     expect - the expected value
>     update - the new value
>   Returns:
>     true if successful.
>
> What does "May fail spuriously" mean?  Why would it fail spuriously?  When the
> spurious failures occur, is the return value always false?  Why would anyone
> call this method having been warned that "spurious failure" is possible?  I
> think I'm missing something here.
>

See
<a href="http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html

The javadocs in the atomic package also mention that this form may be more
efficient. (At least on some processors; on most (in fact all supported by
hotspot) it actually compiles to the same code.) The reason that it may be more
efficient is that some processors perform CAS via a pair of Load-linked /
Store-conditional instructions, which may fail if some other processor
happened to write to the same cache line, among other reasons that have
nothing to do with the CAS. In some cases, this is acceptable. On
such processors, a full strong CAS must actually be coded internally
as a loop. There are a handfull of non-blocking algorithms out there
where you don't actually want that loop, so we include this method
so you can avoid it. We expect use of this method to be uncommon.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
<a href="http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


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

RE: AtomicReference weakCompareAndSet "Mayfail spuriously"?

David Holmes-3
If it fails it just returns false and doesn't set the value.
 
The "weak" aspect of this is that it can fail for reasons other than the current value not matching the expected value. It still has well-defined behaviour.
 
If you are interested in the details on platforms that provide load-linked and store-conditional instructions (ll/sc), these are used to emulate CompareAndSwap. But a store conditional can fail for reasons other than the target memory location being written to by some other thread - the granularity is typically a cache-line, so a write to a close variable can cause the SC to fail. Even if the same value was written into the variable the SC would still fail. So typically you use ll/sc in a retry loop until you either succeed or determine the failure was due to the current value not being the expected value. This gives you the strong compareAndSet semantics. The weakCompareAndSet doesn't use the loop.
 
Cheers,
David Holmes
-----Original Message-----
From: [hidden email] [mailto:[hidden email]]On Behalf Of Hanson Char
Sent: Sunday, 14 May 2006 5:05 PM
To: Doug Lea
Cc: [hidden email]
Subject: Re: [concurrency-interest] AtomicReference weakCompareAndSet "Mayfail spuriously"?

I've gone thru the javadoc, but would like to clarify further.

In case when the invocation of

  weakCompareAndSet

does fail, what behavior could we expect from the failure ?

1) corrupted data being set ? or
2) runtime exception or error being thrown ? or
3) the method (weakCompareAndSet) did not set the value but return true ? or
4) the method did set the value but return false ? or
5) the method just failed but the behavior is non-deterministic ?

Hanson

On 2/2/06, Doug Lea <[hidden email] > wrote:
Robert Kuhar wrote:

> I was strolling through the Docs one day, and came upon the JDK 1.5 Javadocs
> for Class java.util.concurrent.atomic.AtomicReference.  The description for the
> weakCompareAndSet method confuses me:
>
>   public final boolean weakCompareAndSet(V expect, V update)
>
>   Atomically set the value to the given updated value if the current
>   value == the expected value. May fail spuriously.
>
>   Parameters:
>     expect - the expected value
>     update - the new value
>   Returns:
>     true if successful.
>
> What does "May fail spuriously" mean?  Why would it fail spuriously?  When the
> spurious failures occur, is the return value always false?  Why would anyone
> call this method having been warned that "spurious failure" is possible?  I
> think I'm missing something here.
>

See
<A onclick="return top.js.OpenExtLink(window,event,this)" href="http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html" target=_blank>http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html

The javadocs in the atomic package also mention that this form may be more
efficient. (At least on some processors; on most (in fact all supported by
hotspot) it actually compiles to the same code.) The reason that it may be more
efficient is that some processors perform CAS via a pair of Load-linked /
Store-conditional instructions, which may fail if some other processor
happened to write to the same cache line, among other reasons that have
nothing to do with the CAS. In some cases, this is acceptable. On
such processors, a full strong CAS must actually be coded internally
as a loop. There are a handfull of non-blocking algorithms out there
where you don't actually want that loop, so we include this method
so you can avoid it. We expect use of this method to be uncommon.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
<A onclick="return top.js.OpenExtLink(window,event,this)" href="http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest" target=_blank>http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Hanson Char
Thanks for explaining.

Does the following code look good to you ?  Is it a good case or "proper" use of weakCompareAndSet ? 
Hanson

public class Foo {
    private volatile int latency = -1;
    private final AtomicInteger maxLatency = new AtomicInteger(-1);

    public void setLatency(int latency)
    {
        this.latency = latency;
        updateMaxLatency(latency);
    }

    private void updateMaxLatency(int latency)
    {
        for (;;) {
            int maxLatencySnapshot = this.maxLatency.get();
           
            if (latency > maxLatencySnapshot)
            {
                if (this.maxLatency.weakCompareAndSet (maxLatencySnapshot, latency))
                    return; // new max succesfully set
                // race condition or just fail spuriously; so let's retry
                continue;
            }
            return;
        }
    }
}


On 5/14/06, David Holmes <[hidden email]> wrote:
If it fails it just returns false and doesn't set the value.
 
The "weak" aspect of this is that it can fail for reasons other than the current value not matching the expected value. It still has well-defined behaviour.
 
If you are interested in the details on platforms that provide load-linked and store-conditional instructions (ll/sc), these are used to emulate CompareAndSwap. But a store conditional can fail for reasons other than the target memory location being written to by some other thread - the granularity is typically a cache-line, so a write to a close variable can cause the SC to fail. Even if the same value was written into the variable the SC would still fail. So typically you use ll/sc in a retry loop until you either succeed or determine the failure was due to the current value not being the expected value. This gives you the strong compareAndSet semantics. The weakCompareAndSet doesn't use the loop.
 
Cheers,
David Holmes
-----Original Message-----
From: [hidden email] [mailto:[hidden email]]On Behalf Of Hanson Char
Sent: Sunday, 14 May 2006 5:05 PM
To: Doug Lea
Cc: [hidden email]
Subject: Re: [concurrency-interest] AtomicReference weakCompareAndSet "Mayfail spuriously"?

I've gone thru the javadoc, but would like to clarify further.

In case when the invocation of

  weakCompareAndSet

does fail, what behavior could we expect from the failure ?

1) corrupted data being set ? or
2) runtime exception or error being thrown ? or
3) the method (weakCompareAndSet) did not set the value but return true ? or
4) the method did set the value but return false ? or
5) the method just failed but the behavior is non-deterministic ?

Hanson

On 2/2/06, Doug Lea <[hidden email] > wrote:
Robert Kuhar wrote:

> I was strolling through the Docs one day, and came upon the JDK 1.5 Javadocs
> for Class java.util.concurrent.atomic.AtomicReference.  The description for the
> weakCompareAndSet method confuses me:
>
>   public final boolean weakCompareAndSet(V expect, V update)
>
>   Atomically set the value to the given updated value if the current
>   value == the expected value. May fail spuriously.
>
>   Parameters:
>     expect - the expected value
>     update - the new value
>   Returns:
>     true if successful.
>
> What does "May fail spuriously" mean?  Why would it fail spuriously?  When the
> spurious failures occur, is the return value always false?  Why would anyone
> call this method having been warned that "spurious failure" is possible?  I
> think I'm missing something here.
>

See
<a href="http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/package-summary.html

The javadocs in the atomic package also mention that this form may be more
efficient. (At least on some processors; on most (in fact all supported by
hotspot) it actually compiles to the same code.) The reason that it may be more
efficient is that some processors perform CAS via a pair of Load-linked /
Store-conditional instructions, which may fail if some other processor
happened to write to the same cache line, among other reasons that have
nothing to do with the CAS. In some cases, this is acceptable. On
such processors, a full strong CAS must actually be coded internally
as a loop. There are a handfull of non-blocking algorithms out there
where you don't actually want that loop, so we include this method
so you can avoid it. We expect use of this method to be uncommon.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
<a href="http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)"> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest



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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Doug Lea
Hanson Char wrote:
>
> Does the following code look good to you ?  Is it a good case or
> "proper" use of weakCompareAndSet ?


Yes, this is fine; it is a good example where either the plain or
the weak form would work just as well, so you might as well use
the weak form.

>
> public class Foo {
>     private volatile int latency = -1;
>     private final AtomicInteger maxLatency = new AtomicInteger(-1);
>
>     public void setLatency(int latency)
>     {
>         this.latency = latency;
>         updateMaxLatency(latency);
>     }
>
>     private void updateMaxLatency(int latency)
>     {
>         for (;;) {
>             int maxLatencySnapshot = this.maxLatency.get();
>            
>             if (latency > maxLatencySnapshot)
>             {
>                 if (this.maxLatency.weakCompareAndSet
> (maxLatencySnapshot, latency))
>                     return; // new max succesfully set
>                 // race condition or just fail spuriously; so let's retry
>                 continue;
>             }
>             return;
>         }
>     }
> }
>
>


-Doug

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Bob Lee-8
On 5/15/06, Doug Lea <[hidden email]> wrote:
> Yes, this is fine; it is a good example where either the plain or
> the weak form would work just as well, so you might as well use
> the weak form.

Can you please provide an example of when you'd use one or the other?

Bob

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Doug Lea
Bob Lee wrote:
> On 5/15/06, Doug Lea <[hidden email]> wrote:
>> Yes, this is fine; it is a good example where either the plain or
>> the weak form would work just as well, so you might as well use
>> the weak form.
>
> Can you please provide an example of when you'd use one or the other?
>

Plain compareAndSet is always preferred when failure is informative.
A false return from x.compareAndSet(expected, newValue) tells you that the
current value is NOT equal to expected.

For example, suppose you have an AtomicInteger x serving as a lock or semaphore
of some sort. In that case you can write
   if (!x.compareAndSet(0, 1))
     // then lock must already be busy
     // ...



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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Doug Lea
In reply to this post by Bob Lee-8
Bob Lee wrote:
> On 5/15/06, Doug Lea <[hidden email]> wrote:
>> Yes, this is fine; it is a good example where either the plain or
>> the weak form would work just as well, so you might as well use
>> the weak form.
>
> Can you please provide an example of when you'd use one or the other?
>

Thanks to Bill Pugh for reminding me about a second difference
between weakCompareAndSet vs plain compareAndSet, that normally
goes hand-in-hand with the main difference of failure being
uninformative:

A plain compareAndSet has volatile-write memory model semantics, while a
weakCompareAndSet has non-volatile-write memory model semantics.

This mainly means that the visibility of a value written
using weakCompareAndSet does not imply visibility of previous writes by the
thread performing the weakCompareAndSet. This does hold for plain
compareAndSet though. For example

class C { int a; AtomicInteger b = new AtomicInteger(); }
static C c = new C();

Thread 1:
   c.a = 1;
   c.b.compareAndSet(0, 1);

Thread 2;
    if (c.b.get() == 1) assert(c.a == 1);

But if Thread 1 used weakCompareAndSet, the assertion in
Thread 2 need not hold.

This is a little subtle, but is in keeping with the
"uninformativeness" property of weakCompareAndSet.
It implies that weakCompareAndSet is not a good choice for
implementing locks, semaphores, initialization flags, etc, but
we already saw why this was so in last example.

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

Re: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Thomas Hawtin
Doug Lea wrote:
>
> A plain compareAndSet has volatile-write memory model semantics, while a
> weakCompareAndSet has non-volatile-write memory model semantics.

And the same for (non-)volatile-read memory model semantics, if my
reading of the package JavaDocs is correct.

Is there any particular reason for not having a "weakGet" method? Going
back to Hanson Char's example:

  int maxLatencySnapshot = this.maxLatency.get();
  if (latency > maxLatencySnapshot) {
    if (this.maxLatency.weakCompareAndSet(maxLatencySnapshot, latency)) {

Most of the gains that may be made from using weakCompareAndSet seem to
be blown away by the get. (Sun's implementation doesn't seem to
differentiate between weakCompareAndSet and compareAndSet, at the moment.)


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

Re: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Doug Lea
Thomas Hawtin wrote:

> Doug Lea wrote:
>>
>> A plain compareAndSet has volatile-write memory model semantics, while a
>> weakCompareAndSet has non-volatile-write memory model semantics.
>
> And the same for (non-)volatile-read memory model semantics, if my
> reading of the package JavaDocs is correct.
>
> Is there any particular reason for not having a "weakGet" method? Going
> back to Hanson Char's example:
>
>  int maxLatencySnapshot = this.maxLatency.get();
>  if (latency > maxLatencySnapshot) {
>    if (this.maxLatency.weakCompareAndSet(maxLatencySnapshot, latency)) {
>
> Most of the gains that may be made from using weakCompareAndSet seem to
> be blown away by the get. (Sun's implementation doesn't seem to
> differentiate between weakCompareAndSet and compareAndSet, at the moment.)
>

Generally, volatile-reads are cheap -- the main cost
is suppressing optimizations/reorderings. On most machines,
they don't generate machine-level barriers, and
on the ones where they do (mainly: Itanium/IA64), they are the
cheapest kind, and so barely measurable.

And the suppressed optimizations/orderings are exactly those you'd need to
suppress in uses like this. Without this, a VM might (depending on
context) forever cache a single read of the value, which would rarely
be useful for an AtomicX. There may be a few use-cases for some kind of
weakGet, but I think they are most rare.

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

wpugh
In reply to this post by Doug Lea

On May 17, 2006, at 4:43 AM, Doug Lea wrote:

> Bob Lee wrote:
>> On 5/15/06, Doug Lea <[hidden email]> wrote:
>>> Yes, this is fine; it is a good example where either the plain or
>>> the weak form would work just as well, so you might as well use
>>> the weak form.
>> Can you please provide an example of when you'd use one or the other?
>
> Thanks to Bill Pugh for reminding me about a second difference
> between weakCompareAndSet vs plain compareAndSet, that normally
> goes hand-in-hand with the main difference of failure being
> uninformative:
>
> A plain compareAndSet has volatile-write memory model semantics,  
> while a
> weakCompareAndSet has non-volatile-write memory model semantics.
]

I would explain this differently (actually, the JMM requires that it  
be explained differently):

weakCompareAndSet has volatile semantics, _except_ that it doesn't  
create any happens-before
edges.

Thus, using weakCompareAndSet is ideal for things such as performance  
counters,
unique identifiers and reference counting.

However, what about AtomicReference? If you actually try to pass  
references between threads,
you need to establish a happens-before relationship between the two  
threads, so that the contents of
the object are communicated as well.

So, here is the question we should discuss:

**********

Should weakCompareAndSet on an AtomicReference create happens before  
edges (just as
compareAndSwap does)?

**********

For AtomicInteger, and similar classes, there isn't a question. Just  
for AtomicReference classes.

I talked with Doug, and we agreed that we didn't have enough use  
cases to really decide.

The only possible use for a weakCompareAndSet on a reference where  
you don't need a happens-before
edge is if you can prove that a happens-before edge is created by  
some other mechanism.

So, if weakCompareAndSet does not establish a happens-before  
ordering, then a few people (i.e, just Doug)
might be able to effectively use it to superoptimize some code.  
However, without the happens-before ordering,
some potential use cases are invalid, and many people trying to use  
it will create a data race.

Thoughts?

        Bill



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

RE: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Boehm, Hans
I'm not completely convinced that the issue is really different for
references.

I think that fundamentally spurious failures and ordering are quite
different.  Allowing spurious failures is occasionally useful, and I
think something that's relatively easily understood.  Relaxing the
ordering can occasionally also be very useful, especially for low level
libraries, but I think it gets you considerably further into
"wizards-only" territory.

My impression, based in part on recent discussions in a C++ context, is
that few people really understand that in the absence of the ordering
semantics, data- or control-dependence does not imply ordering.  This
may be less of an issue with CompareAndSet, but I still think that the
fact that the changes to x and y in

if(x.weakCompareAndSet(a, b)) {
        y = 17;
}

can appear out of order is really unintuitive for most people.  And such
code is essentially untestable, since the ordering is in fact implied in
most cases, with most compilers, on most current hardware.  If you
require ordering, this sort of issue just goes away.

It seems to me that references are special, only in that the
weakCompareAndSet is often dereferenced before or after the
WeakCompareAndSet.  But that's a statistical property; not a guarantee.
It's certainly conceivable that references are used in an algorithm in
which they are only compared and never dereferenced.  Thus the contents
don't need to be communicated.  (I know of one large C++ program for
which the contents corresponding to many references were in fact dead
and had been explicitly deallocated.)  And I'm not sure that the
reference situation in which the contents of the reference are used is
much different from the AtomicInteger situation for which a later load
is dependent on the weakCompareAndSet result, as above.

Thus I think I would argue against resolving this differently for
AtomicReference and AtomicInteger.

I would be more positive on strengthening ordering of weakCompareAndSet
for both.  If you really want relaxed ordering variants for
CompareAndSet, my intuition is that all four possible variants (no
ordering, acquire, release, both) have about equal utility, and the "no
ordering" variant is the hardest to understand.  (It's usually
insufficient for reference counting, as I recall.)  And each weakening
potentially involves a performance gain. On the other hand, I'm not at
all sure that this is a sufficient argument for change at this point.

Hans

> -----Original Message-----
> From: Bill Pugh
>
> weakCompareAndSet has volatile semantics, _except_ that it
> doesn't create any happens-before edges.
>
> Thus, using weakCompareAndSet is ideal for things such as
> performance counters, unique identifiers and reference counting.
>
> However, what about AtomicReference? If you actually try to
> pass references between threads, you need to establish a
> happens-before relationship between the two threads, so that
> the contents of the object are communicated as well.
>
> So, here is the question we should discuss:
>
> **********
>
> Should weakCompareAndSet on an AtomicReference create happens
> before edges (just as compareAndSwap does)?
>
> **********
>
> For AtomicInteger, and similar classes, there isn't a
> question. Just for AtomicReference classes.
>
> I talked with Doug, and we agreed that we didn't have enough
> use cases to really decide.
>
> The only possible use for a weakCompareAndSet on a reference
> where you don't need a happens-before edge is if you can
> prove that a happens-before edge is created by some other mechanism.
>
> So, if weakCompareAndSet does not establish a happens-before
> ordering, then a few people (i.e, just Doug) might be able to
> effectively use it to superoptimize some code.  
> However, without the happens-before ordering, some potential
> use cases are invalid, and many people trying to use it will
> create a data race.
>
> Thoughts?
>
> Bill
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Cliff Click
In reply to this post by wpugh
My use-case for AtomicInteger NOT forcing a happens-before is in
high-performance perf-counters.  Since it's a perf-counter I've no need
of a happens-before; but I can't tolerate the very high level of
count-dropping that happens if I don't use a CAS.

In my case I've got 380 CPUs busy incrementing a counter; the counter
goes up about 790,000 increments/sec (one increment per piece of 'real'
work).  If I use a lock, I'm limited to about 50 CPUs and 60,000
ops/sec.  If I use a strong CAS (CAS+fence) I get ~400,000 ops/sec.  If
I use a CAS-no-fence I get 790,000 ops/sec.  That extra fence really
costs!  This is admittedly an extreme case, but it's going to be less
extreme going forward: next year we'll have double the CPU count.

For AtomicRef's I agree with Bill's statement: for ease of correct
coding we should just require the happens-before.

The other option worth mentioning is just to define all variations,
which can be trivially implemented by using the strong version, but
would allow experts some lea-way on more interesting hardware.

Cliff


Bill Pugh wrote:

>
> On May 17, 2006, at 4:43 AM, Doug Lea wrote:
>
>> Bob Lee wrote:
>>
>>> On 5/15/06, Doug Lea <[hidden email]> wrote:
>>>
>>>> Yes, this is fine; it is a good example where either the plain or
>>>> the weak form would work just as well, so you might as well use
>>>> the weak form.
>>>
>>> Can you please provide an example of when you'd use one or the other?
>>
>>
>> Thanks to Bill Pugh for reminding me about a second difference
>> between weakCompareAndSet vs plain compareAndSet, that normally
>> goes hand-in-hand with the main difference of failure being
>> uninformative:
>>
>> A plain compareAndSet has volatile-write memory model semantics,  
>> while a
>> weakCompareAndSet has non-volatile-write memory model semantics.
>
> ]
>
> I would explain this differently (actually, the JMM requires that it  
> be explained differently):
>
> weakCompareAndSet has volatile semantics, _except_ that it doesn't  
> create any happens-before
> edges.
>
> Thus, using weakCompareAndSet is ideal for things such as performance  
> counters,
> unique identifiers and reference counting.
>
> However, what about AtomicReference? If you actually try to pass  
> references between threads,
> you need to establish a happens-before relationship between the two  
> threads, so that the contents of
> the object are communicated as well.
>
> So, here is the question we should discuss:
>
> **********
>
> Should weakCompareAndSet on an AtomicReference create happens before  
> edges (just as
> compareAndSwap does)?
>
> **********
>
> For AtomicInteger, and similar classes, there isn't a question. Just  
> for AtomicReference classes.
>
> I talked with Doug, and we agreed that we didn't have enough use  
> cases to really decide.
>
> The only possible use for a weakCompareAndSet on a reference where  
> you don't need a happens-before
> edge is if you can prove that a happens-before edge is created by  
> some other mechanism.
>
> So, if weakCompareAndSet does not establish a happens-before  
> ordering, then a few people (i.e, just Doug)
> might be able to effectively use it to superoptimize some code.  
> However, without the happens-before ordering,
> some potential use cases are invalid, and many people trying to use  
> it will create a data race.
>
> Thoughts?
>
>     Bill
>
>
>

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

cliffc.vcf (145 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Doug Lea
In reply to this post by Boehm, Hans
Backing up a little first, the intent of weakCAS is to provide the
cheapest possible conditional atomic update available on a machine,
that may entail tradeoffs wrt determinism and ordering.
It is mainly useful for things like collecting statistics
as in Hanson Char's example code, which is a common and useful use case.
It is almost never used inside java.util.concurrent, because atomics
used within synchronizers almost always need to rely on comparison
outcome and/or to ensure happens-before orderings, so the opportunity
to use it rarely arises.


Boehm, Hans wrote:
> I'm not completely convinced that the issue is really different for
> references.

I agree. I think that weakCAS is even less commonly useful
for references, but not qualitatively different.

> This may be less of an issue with CompareAndSet, but I still think that the
> fact that the changes to x and y in
>
> if(x.weakCompareAndSet(a, b)) { y = 17; }
>
> can appear out of order is really unintuitive for most people.

I'm not sure what you have in mind here though. For this ordering to
be guaranteed, "y" would need to be volatile, which would cause
this to hold regardless of weakCAS ordering. As it stands now,
it would basically have the same outcome ordering semantics as, for
some variable z,
   if (z == a) {
      z = b;
      y = 17;
   }

Where the main ordering constraint relies on whether "y" is volatile,
not whether "z" is.

>
>
> I would be more positive on strengthening ordering of weakCompareAndSet for
> both.

But then people like Cliff will be unhappy.

> On the other hand, I'm not at all sure that this is a sufficient argument for
> change at this point.
>

I'm completely open about adding variants distinguishing
determinism vs ordering, but I don't see a very compelling
argument for it either.

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Bart Jacobs-2
In reply to this post by Cliff Click
Wouldn't it be better to increase the granularity of your counter? Use
thread-local counters and increment the shared counter per thousand
pieces of real work?

Note: it's probably best to use some app-specific mechanism for
thread-local counters, since ThreadLocal may have high overhead.

Thanks,-
Bart

Cliff Click wrote:

> My use-case for AtomicInteger NOT forcing a happens-before is in
> high-performance perf-counters.  Since it's a perf-counter I've no need
> of a happens-before; but I can't tolerate the very high level of
> count-dropping that happens if I don't use a CAS.
>
> In my case I've got 380 CPUs busy incrementing a counter; the counter
> goes up about 790,000 increments/sec (one increment per piece of 'real'
> work).  If I use a lock, I'm limited to about 50 CPUs and 60,000
> ops/sec.  If I use a strong CAS (CAS+fence) I get ~400,000 ops/sec.  If
> I use a CAS-no-fence I get 790,000 ops/sec.  That extra fence really
> costs!  This is admittedly an extreme case, but it's going to be less
> extreme going forward: next year we'll have double the CPU count.
>
> For AtomicRef's I agree with Bill's statement: for ease of correct
> coding we should just require the happens-before.
>
> The other option worth mentioning is just to define all variations,
> which can be trivially implemented by using the strong version, but
> would allow experts some lea-way on more interesting hardware.
>
> Cliff
>
>
> Bill Pugh wrote:
>
>>
>> On May 17, 2006, at 4:43 AM, Doug Lea wrote:
>>
>>> Bob Lee wrote:
>>>
>>>> On 5/15/06, Doug Lea <[hidden email]> wrote:
>>>>
>>>>> Yes, this is fine; it is a good example where either the plain or
>>>>> the weak form would work just as well, so you might as well use
>>>>> the weak form.
>>>>
>>>> Can you please provide an example of when you'd use one or the other?
>>>
>>>
>>> Thanks to Bill Pugh for reminding me about a second difference
>>> between weakCompareAndSet vs plain compareAndSet, that normally
>>> goes hand-in-hand with the main difference of failure being
>>> uninformative:
>>>
>>> A plain compareAndSet has volatile-write memory model semantics,  
>>> while a
>>> weakCompareAndSet has non-volatile-write memory model semantics.
>>
>> ]
>>
>> I would explain this differently (actually, the JMM requires that it  
>> be explained differently):
>>
>> weakCompareAndSet has volatile semantics, _except_ that it doesn't  
>> create any happens-before
>> edges.
>>
>> Thus, using weakCompareAndSet is ideal for things such as performance  
>> counters,
>> unique identifiers and reference counting.
>>
>> However, what about AtomicReference? If you actually try to pass  
>> references between threads,
>> you need to establish a happens-before relationship between the two  
>> threads, so that the contents of
>> the object are communicated as well.
>>
>> So, here is the question we should discuss:
>>
>> **********
>>
>> Should weakCompareAndSet on an AtomicReference create happens before  
>> edges (just as
>> compareAndSwap does)?
>>
>> **********
>>
>> For AtomicInteger, and similar classes, there isn't a question. Just  
>> for AtomicReference classes.
>>
>> I talked with Doug, and we agreed that we didn't have enough use  
>> cases to really decide.
>>
>> The only possible use for a weakCompareAndSet on a reference where  
>> you don't need a happens-before
>> edge is if you can prove that a happens-before edge is created by  
>> some other mechanism.
>>
>> So, if weakCompareAndSet does not establish a happens-before  
>> ordering, then a few people (i.e, just Doug)
>> might be able to effectively use it to superoptimize some code.  
>> However, without the happens-before ordering,
>> some potential use cases are invalid, and many people trying to use  
>> it will create a data race.
>>
>> Thoughts?
>>
>>     Bill
>>
>>
>>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

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

Re: AtomicReference weakCompareAndSet "Mayfail spuriously"?

Cliff Click-2
Better yes, but I'm looking for a cheapo solution I can tell customers
to slap into their code.
Thread-local counters work where the ratio of increments-to-reads is
real high, but not if reads are common.  That distinction requires me to
know something about the application, i.e., it's not a no-brainer
drop-in solution.

In one case I can say "use this standard API which you can read about in
Sun's online javadoc's and even exists in 1.4.2 (sun.misc.atomic)"
versus "if you aren't reading the counter alot, download this code from
Azul and use it instead and also it requires 5.0".

It would help if a very-high-performance counter class made it into the
JRE, so we can start moving people towards a portably-performant solution.

Cliff


Bart Jacobs wrote:

> Wouldn't it be better to increase the granularity of your counter? Use
> thread-local counters and increment the shared counter per thousand
> pieces of real work?
>
> Note: it's probably best to use some app-specific mechanism for
> thread-local counters, since ThreadLocal may have high overhead.
>
> Thanks,-
> Bart
>
> Cliff Click wrote:
>> My use-case for AtomicInteger NOT forcing a happens-before is in
>> high-performance perf-counters.  Since it's a perf-counter I've no
>> need of a happens-before; but I can't tolerate the very high level of
>> count-dropping that happens if I don't use a CAS.
>>
>> In my case I've got 380 CPUs busy incrementing a counter; the counter
>> goes up about 790,000 increments/sec (one increment per piece of
>> 'real' work).  If I use a lock, I'm limited to about 50 CPUs and
>> 60,000 ops/sec.  If I use a strong CAS (CAS+fence) I get ~400,000
>> ops/sec.  If I use a CAS-no-fence I get 790,000 ops/sec.  That extra
>> fence really costs!  This is admittedly an extreme case, but it's
>> going to be less extreme going forward: next year we'll have double
>> the CPU count.
>>
>> For AtomicRef's I agree with Bill's statement: for ease of correct
>> coding we should just require the happens-before.
>>
>> The other option worth mentioning is just to define all variations,
>> which can be trivially implemented by using the strong version, but
>> would allow experts some lea-way on more interesting hardware.
>>
>> Cliff
>>
>>
>> Bill Pugh wrote:
>>
>>>
>>> On May 17, 2006, at 4:43 AM, Doug Lea wrote:
>>>
>>>> Bob Lee wrote:
>>>>
>>>>> On 5/15/06, Doug Lea <[hidden email]> wrote:
>>>>>
>>>>>> Yes, this is fine; it is a good example where either the plain or
>>>>>> the weak form would work just as well, so you might as well use
>>>>>> the weak form.
>>>>>
>>>>> Can you please provide an example of when you'd use one or the other?
>>>>
>>>>
>>>> Thanks to Bill Pugh for reminding me about a second difference
>>>> between weakCompareAndSet vs plain compareAndSet, that normally
>>>> goes hand-in-hand with the main difference of failure being
>>>> uninformative:
>>>>
>>>> A plain compareAndSet has volatile-write memory model semantics,  
>>>> while a
>>>> weakCompareAndSet has non-volatile-write memory model semantics.
>>>
>>> ]
>>>
>>> I would explain this differently (actually, the JMM requires that
>>> it  be explained differently):
>>>
>>> weakCompareAndSet has volatile semantics, _except_ that it doesn't  
>>> create any happens-before
>>> edges.
>>>
>>> Thus, using weakCompareAndSet is ideal for things such as
>>> performance  counters,
>>> unique identifiers and reference counting.
>>>
>>> However, what about AtomicReference? If you actually try to pass  
>>> references between threads,
>>> you need to establish a happens-before relationship between the two  
>>> threads, so that the contents of
>>> the object are communicated as well.
>>>
>>> So, here is the question we should discuss:
>>>
>>> **********
>>>
>>> Should weakCompareAndSet on an AtomicReference create happens
>>> before  edges (just as
>>> compareAndSwap does)?
>>>
>>> **********
>>>
>>> For AtomicInteger, and similar classes, there isn't a question.
>>> Just  for AtomicReference classes.
>>>
>>> I talked with Doug, and we agreed that we didn't have enough use  
>>> cases to really decide.
>>>
>>> The only possible use for a weakCompareAndSet on a reference where  
>>> you don't need a happens-before
>>> edge is if you can prove that a happens-before edge is created by  
>>> some other mechanism.
>>>
>>> So, if weakCompareAndSet does not establish a happens-before  
>>> ordering, then a few people (i.e, just Doug)
>>> might be able to effectively use it to superoptimize some code.  
>>> However, without the happens-before ordering,
>>> some potential use cases are invalid, and many people trying to use  
>>> it will create a data race.
>>>
>>> Thoughts?
>>>
>>>     Bill
>>>
>>>
>>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>

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

cliffc.vcf (279 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Boehm, Hans
In reply to this post by Doug Lea
I think we basically agree, so this is only a detail:

> From: Doug Lea [mailto:[hidden email]]
> I agree. I think that weakCAS is even less commonly useful
> for references, but not qualitatively different.
>
> > This may be less of an issue with CompareAndSet, but I still think
> > that the fact that the changes to x and y in
> >
> > if(x.weakCompareAndSet(a, b)) { y = 17; }
> >
> > can appear out of order is really unintuitive for most people.
>
> I'm not sure what you have in mind here though. For this
> ordering to be guaranteed, "y" would need to be volatile,
> which would cause this to hold regardless of weakCAS
> ordering. As it stands now, it would basically have the same
> outcome ordering semantics as, for some variable z,
>    if (z == a) {
>       z = b;
>       y = 17;
>    }
>
> Where the main ordering constraint relies on whether "y" is
> volatile, not whether "z" is.
>
Let me revise the example slightly, though I'm still not sure this is
convincing enough to motivate a change.  Assume x is AtomicSomething
initially not a, y not volatile.

Thread 1:
y = 17; x.set(a);

Thread 2:
if(x.weakCompareAndSet(a, b)) { r1 = y; }

Currently r1 does not have to be 17.  With an ordered weakCompareAndSet,
it would have to be.  I think the current situation is hard to explain,
because there is a data race only in a somewhat technical sense (atomics
are supposed to be used for thread communication after all, and y cannot
actually be accessed concurrently in the sequentially consistent
interpretation), and the program does not behave sequentially
consistently.  It is even less intuitive, since any attempt to explain
this operation runs into the problem that the two memory operations in
thread 2 are dependent, which everyone expects to imply ordering.  (I'd
be the first to agree that it cannot, but still that's the expectation.)
The nice thing about dealing with ordered operations is that they
usually make the dependency issues irrelevant.

Hans

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

RE: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Boehm, Hans
In reply to this post by Cliff Click
> From: Cliff Click
> For AtomicRef's I agree with Bill's statement: for ease of
> correct coding we should just require the happens-before.
>
It still strikes me as very weird to distinguish the two.  If I
implement a single bit counter as an integer, I would get different
semantics than if I implement it via switching between references to two
preinitialized Boolean objects.  In cases like these, the user's
requirements are absolutely the same for both.

If you want to do this, I think the operations should at least have
different names.

The real issue here may be the current documentation for
AtomicReference.weakCompareAndSet, which seems to be lacking the
requisite warnings, like: "This provides weaker memory visibility
guarantees than compareAndSet.  If you have any doubt whether you should
be using weakCompareAndSet or compareAndSet, then use compareAndSet."

Hans

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

Re: AtomicReference weakCompareAndSet "Mayfailspuriously"?

Doug Lea
Boehm, Hans wrote:

>
> The real issue here may be the current documentation for
> AtomicReference.weakCompareAndSet,

Presciently, Marting Buchholz filed a documentation bug for
weakCompareAndSet last week, so we should be able to do this soon.
(http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6425639)

> which seems to be lacking the
> requisite warnings, like: "This provides weaker memory visibility
> guarantees than compareAndSet.  If you have any doubt whether you should
> be using weakCompareAndSet or compareAndSet, then use compareAndSet."

Thanks. This is a good start.
Additional wording suggestions (from everyone!) would be welcome.

-Doug


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