Is this a pattern or an anti-pattern for check-and-act?

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Is this a pattern or an anti-pattern for check-and-act?

Aleksey Shipilev-2
On 03/04/2016 04:02 PM, Millies, Sebastian wrote:

> Here's a variation on the SafeLocalDCLFactory, where the synchronization has been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication?
No, weakCompareAndSet is not specified with release semantics, even
though current implementation does delegate to stronger CAS (upcoming
VarHandles would change that). Therefore, the successful weakCAS-ing of
new instance is broken in the same way test-and-set on a non-volatile
field is.

> I haven't mastered jcstress, but I'd be curious if it's faster than DCL.

I think you mean JMH. I would imagine this version is subtly slower,
since it stores the instance in a box -- getting dereferences in a
picture. Although it would probably be hard to produce in an isolated
testcase.

Thanks,
-Aleksey


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

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FW: Is this a pattern or an anti-pattern for check-and-act?

nader
In reply to this post by Millies, Sebastian
My experience with CAS algorithms is limited.  Is this solution 100% correct?

On Fri, Mar 4, 2016 at 2:10 PM, Millies, Sebastian <[hidden email]> wrote:
Sorry, I think I was a bit hasty. The problem with this version it may happen that the code that actually constructs an object - s.get() - is called more than once. Laziness, however, is most useful if the object is a) perhaps not used and b) difficult to construct. So although the publication is safe, and the code will always return the same instance, in view of point b), this version does not really make sense as a singleton pattern. Right? -- Sebastian

> -----Original Message-----
> From: Millies, Sebastian
> Sent: Friday, March 04, 2016 2:02 PM
> To: concurrency-interest
> Cc: 'Aleksey Shipilev'; Nader Aeinehchi
> Subject: RE: [concurrency-interest] Is this a pattern or an anti-pattern for
> check-and-act?
>
> Here's a variation on the SafeLocalDCLFactory, where the synchronization has
> been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication? I haven't mastered jcstress, but I'd be
> curious if it's faster than DCL.
>
> -- Sebastian
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]
> [hidden email]] On Behalf Of Aleksey Shipilev
> Sent: Monday, February 29, 2016 9:31 PM
> To: Nader Aeinehchi; concurrency-interest
> Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for
> check-and-act?
>
> On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
> > I saw this pattern on an open source project, and wonder if it is
> > thread safe?  If so, would it scale?
>
> See:
http://shipilev.net/blog/2014/safe-public-construction/
>
> -Aleksey


Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



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

Re: Is this a pattern or an anti-pattern for check-and-act?

Millies, Sebastian
In reply to this post by Aleksey Shipilev-2
Thanks for the correction. Somehow, I was under the impression (don't remember where I may have read that), that weakCompareAndSet does not establish happens-before relationships for any variables EXCEPT the target of weakCompareAndSet itself. -- Sebastian

-----Original Message-----
From: Aleksey Shipilev [mailto:[hidden email]]
Sent: Friday, March 04, 2016 3:22 PM
To: Millies, Sebastian; concurrency-interest
Cc: Nader Aeinehchi
Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for check-and-act?

* PGP Signed by an unknown key

On 03/04/2016 04:02 PM, Millies, Sebastian wrote:

> Here's a variation on the SafeLocalDCLFactory, where the synchronization has been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication?

No, weakCompareAndSet is not specified with release semantics, even though current implementation does delegate to stronger CAS (upcoming VarHandles would change that). Therefore, the successful weakCAS-ing of new instance is broken in the same way test-and-set on a non-volatile field is.

> I haven't mastered jcstress, but I'd be curious if it's faster than DCL.

I think you mean JMH. I would imagine this version is subtly slower, since it stores the instance in a box -- getting dereferences in a picture. Although it would probably be hard to produce in an isolated testcase.

Thanks,
-Aleksey


* Unknown Key
* 0x62A119A7

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com


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

Re: FW: Is this a pattern or an anti-pattern for check-and-act?

nader
In reply to this post by nader
The link to the repository for Common Mistakes in Java Concurrency:

On Fri, Mar 4, 2016 at 3:29 PM, Nader Aeinehchi <[hidden email]> wrote:
My experience with CAS algorithms is limited.  Is this solution 100% correct?

On Fri, Mar 4, 2016 at 2:10 PM, Millies, Sebastian <[hidden email]> wrote:
Sorry, I think I was a bit hasty. The problem with this version it may happen that the code that actually constructs an object - s.get() - is called more than once. Laziness, however, is most useful if the object is a) perhaps not used and b) difficult to construct. So although the publication is safe, and the code will always return the same instance, in view of point b), this version does not really make sense as a singleton pattern. Right? -- Sebastian

> -----Original Message-----
> From: Millies, Sebastian
> Sent: Friday, March 04, 2016 2:02 PM
> To: concurrency-interest
> Cc: 'Aleksey Shipilev'; Nader Aeinehchi
> Subject: RE: [concurrency-interest] Is this a pattern or an anti-pattern for
> check-and-act?
>
> Here's a variation on the SafeLocalDCLFactory, where the synchronization has
> been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication? I haven't mastered jcstress, but I'd be
> curious if it's faster than DCL.
>
> -- Sebastian
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]
> [hidden email]] On Behalf Of Aleksey Shipilev
> Sent: Monday, February 29, 2016 9:31 PM
> To: Nader Aeinehchi; concurrency-interest
> Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for
> check-and-act?
>
> On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
> > I saw this pattern on an open source project, and wonder if it is
> > thread safe?  If so, would it scale?
>
> See:
http://shipilev.net/blog/2014/safe-public-construction/
>
> -Aleksey


Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com




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

Re: FW: Is this a pattern or an anti-pattern for check-and-act?

Arno Haase
In reply to this post by nader
* This code has a race that can cause several instances to be created,
since the call to s.get() is not guarded by a lock.

* As Aleksey pointed out, weakCompareAndSet does not guarantee publication.

But most importantly, this code incurs a volatile read for every read
access, which is where performance counts. So it is not faster for reads
than regular DCL.

Optimizing the code branch that creates a new instance looks irrelevant
to me.

- Arno


Am 04.03.2016 um 15:29 schrieb Nader Aeinehchi:

> My experience with CAS algorithms is limited.  Is this solution 100%
> correct?
>
> On Fri, Mar 4, 2016 at 2:10 PM, Millies, Sebastian
> <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Sorry, I think I was a bit hasty. The problem with this version it
>     may happen that the code that actually constructs an object -
>     s.get() - is called more than once. Laziness, however, is most
>     useful if the object is a) perhaps not used and b) difficult to
>     construct. So although the publication is safe, and the code will
>     always return the same instance, in view of point b), this version
>     does not really make sense as a singleton pattern. Right? -- Sebastian
>
>     > -----Original Message-----
>     > From: Millies, Sebastian
>     > Sent: Friday, March 04, 2016 2:02 PM
>     > To: concurrency-interest
>     > Cc: 'Aleksey Shipilev'; Nader Aeinehchi
>     > Subject: RE: [concurrency-interest] Is this a pattern or an anti-pattern for
>     > check-and-act?
>     >
>     > Here's a variation on the SafeLocalDCLFactory, where the synchronization has
>     > been replaced with CAS:
>     >
>     > public class LockfreeFactory<T> {
>     >
>     >     private AtomicReference<T> instance = new AtomicReference<>(null);
>     >
>     >     public T getInstance(Supplier<T> s) {
>     >         T i = instance.get();
>     >         if (i == null) {
>     >             i = s.get();
>     >             if (!instance.weakCompareAndSet(null, i)) {
>     >                 i = instance.get();
>     >             }
>     >         }
>     >         return i;
>     >     }
>     > }
>     >
>     > Would this count as safe publication? I haven't mastered jcstress, but I'd be
>     > curious if it's faster than DCL.
>     >
>     > -- Sebastian
>     >
>     > -----Original Message-----
>     > From: [hidden email]
>     <mailto:[hidden email]>
>     [mailto:concurrency- <mailto:concurrency->
>     > [hidden email]
>     <mailto:[hidden email]>] On Behalf Of Aleksey Shipilev
>     > Sent: Monday, February 29, 2016 9:31 PM
>     > To: Nader Aeinehchi; concurrency-interest
>     > Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for
>     > check-and-act?
>     >
>     > On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
>     > > I saw this pattern on an open source project, and wonder if it is
>     > > thread safe?  If so, would it scale?
>     >
>     > See:
>     >  http://shipilev.net/blog/2014/safe-public-construction/
>     >
>     > -Aleksey
>
>
>     Software AG – Sitz/Registered office: Uhlandstraße 12, 64297
>     Darmstadt, Germany – Registergericht/Commercial register: Darmstadt
>     HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich
>     (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd
>     Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory
>     Board: Dr. Andreas Bereczky - http://www.softwareag.com
>
>
>
>
> _______________________________________________
> 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
|

Re: Is this a pattern or an anti-pattern for check-and-act?

Aaron Grunthal
In reply to this post by Millies, Sebastian
CAS in the slow path gains you practically nothing since it will only
happen a few times at most. what's important is that the fast path is
cheap and yet safe. A volatile read usually is cheap enough, in the few
cases where it's not you start with the final holders or similar
optimizations.

I think yet another alternative not covered by Aleksey's blog post would
be method handle and switchpoint invalidation trickery that could get
you similar results by exploiting the memory ordering around safepoints.

- Aaron

On 04.03.2016 14:02, Millies, Sebastian wrote:

> Here's a variation on the SafeLocalDCLFactory, where the synchronization has been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication? I haven't mastered jcstress, but I'd be curious if it's faster than DCL.
>
> -- Sebastian
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Aleksey Shipilev
> Sent: Monday, February 29, 2016 9:31 PM
> To: Nader Aeinehchi; concurrency-interest
> Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for check-and-act?
>
> On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
>> I saw this pattern on an open source project, and wonder if it is
>> thread safe?  If so, would it scale?
>
> See:
>  http://shipilev.net/blog/2014/safe-public-construction/
>
> -Aleksey
>
>
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com
>
>
> _______________________________________________
> 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
|

Re: Is this a pattern or an anti-pattern for check-and-act?

Vitaly Davidovich


On Friday, March 4, 2016, Aaron Grunthal <[hidden email]> wrote:
CAS in the slow path gains you practically nothing since it will only
happen a few times at most. what's important is that the fast path is
cheap and yet safe. A volatile read usually is cheap enough, in the few
cases where it's not you start with the final holders or similar
optimizations.
I would actually start with final holders because you get the added benefit of the static final instance in the holder being a JIT constant; if you then add TrustNonStaticFinalFields you can get some additional constant folding. 

I think yet another alternative not covered by Aleksey's blog post would
be method handle and switchpoint invalidation trickery that could get
you similar results by exploiting the memory ordering around safepoints.

- Aaron

On 04.03.2016 14:02, Millies, Sebastian wrote:
> Here's a variation on the SafeLocalDCLFactory, where the synchronization has been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication? I haven't mastered jcstress, but I'd be curious if it's faster than DCL.
>
> -- Sebastian
>
> -----Original Message-----
> From: <a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;concurrency-interest-bounces@cs.oswego.edu&#39;)">concurrency-interest-bounces@... [mailto:<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;concurrency-interest-bounces@cs.oswego.edu&#39;)">concurrency-interest-bounces@...] On Behalf Of Aleksey Shipilev
> Sent: Monday, February 29, 2016 9:31 PM
> To: Nader Aeinehchi; concurrency-interest
> Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for check-and-act?
>
> On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
>> I saw this pattern on an open source project, and wonder if it is
>> thread safe?  If so, would it scale?
>
> See:
http://shipilev.net/blog/2014/safe-public-construction/
>
> -Aleksey
>
>
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com
>
>
> _______________________________________________
> Concurrency-interest mailing list
> <a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Concurrency-interest@cs.oswego.edu&#39;)">Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Concurrency-interest@cs.oswego.edu&#39;)">Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


--
Sent from my phone

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

Re: Is this a pattern or an anti-pattern for check-and-act?

Niranjan Nanda
Hello Nader,

I checked the GitHub repo you created for concurrency https://github.com/nader-aeinehchi/java-concurrency-mistakes. It is definitely helpful. I think it will be more helpful if you can add some documentation saying why something is wrong. 

Thank you.

Warm Regards,
Niranjan

Warm Regards,
Niranjan

On Fri, Mar 4, 2016 at 9:36 PM, Vitaly Davidovich <[hidden email]> wrote:


On Friday, March 4, 2016, Aaron Grunthal <[hidden email]> wrote:
CAS in the slow path gains you practically nothing since it will only
happen a few times at most. what's important is that the fast path is
cheap and yet safe. A volatile read usually is cheap enough, in the few
cases where it's not you start with the final holders or similar
optimizations.
I would actually start with final holders because you get the added benefit of the static final instance in the holder being a JIT constant; if you then add TrustNonStaticFinalFields you can get some additional constant folding. 

I think yet another alternative not covered by Aleksey's blog post would
be method handle and switchpoint invalidation trickery that could get
you similar results by exploiting the memory ordering around safepoints.

- Aaron

On 04.03.2016 14:02, Millies, Sebastian wrote:
> Here's a variation on the SafeLocalDCLFactory, where the synchronization has been replaced with CAS:
>
> public class LockfreeFactory<T> {
>
>     private AtomicReference<T> instance = new AtomicReference<>(null);
>
>     public T getInstance(Supplier<T> s) {
>         T i = instance.get();
>         if (i == null) {
>             i = s.get();
>             if (!instance.weakCompareAndSet(null, i)) {
>                 i = instance.get();
>             }
>         }
>         return i;
>     }
> }
>
> Would this count as safe publication? I haven't mastered jcstress, but I'd be curious if it's faster than DCL.
>
> -- Sebastian
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Aleksey Shipilev
> Sent: Monday, February 29, 2016 9:31 PM
> To: Nader Aeinehchi; concurrency-interest
> Subject: Re: [concurrency-interest] Is this a pattern or an anti-pattern for check-and-act?
>
> On 02/29/2016 10:17 PM, Nader Aeinehchi wrote:
>> I saw this pattern on an open source project, and wonder if it is
>> thread safe?  If so, would it scale?
>
> See:
http://shipilev.net/blog/2014/safe-public-construction/
>
> -Aleksey
>
>
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com
>
>
> _______________________________________________
> 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


--
Sent from my phone

_______________________________________________
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
12