propper way to use CAS ?

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

propper way to use CAS ?

Yechiel Feffer
propper way to use CAS ?

Hi,
in many concurrent classes when compare-and-set (cas) is used- it is an endless loop of competing threads trying to fight over an object (,say, a queue's tail in order to connect a new element (reference)) .

Wouldn't it be benefitial to perform a thread.Yield() after N (pre-configured) unsuccessful CAS retries ? wouldnt it give better overall performance ?

Regrds,
Yechiel Fefer    


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

Re: propper way to use CAS ?

Brian Goetz
> in many concurrent classes when compare-and-set (cas) is used- it is an
> endless loop of competing threads trying to fight over an object (,say,
> a queue's tail in order to connect a new element (reference)) .
>
> Wouldn't it be benefitial to perform a thread.Yield() after N
> (pre-configured) unsuccessful CAS retries ? wouldnt it give better
> overall performance ?

It depends on the degree of contention you expect to experience.

In most cases, the standard approach (retry continuously) is best.  Only
when you are expecting very heavy contention, where you expect most CAS
attempts to fail, is a more sophisticated backoff strategy beneficial.

When there is no contention for a CAS, it always succeeds.  When
multiple threads compete for a CAS, one will always win and make
progress.  So the question is, what percent of CAS attempts will lose
and need to be retried?  Only if this ratio is high will a better
contention management strategy be a win.  This is a function of how many
threads are involved, and the ratio of CAS to "other work".

If your contention is so high that most CAS attempts fail, you might be
better off with a lock, as locking automatically addresses the problem
you raise fairly well, by blocking so as not to create more contention.

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

RE: propper way to use CAS ?

Mike Skells-3
Hi,
Doesnt this presuppose that you are running on a system the is pre-emptive,
So if you are running on a non pre-emptive system then the unsuccessful CAS
retries will just continue wont they?

Mike

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf
> Of Brian Goetz
> Sent: 09 October 2005 16:18
> To: Yechiel Feffer
> Cc: [hidden email]
> Subject: Re: [concurrency-interest] propper way to use CAS ?
>
> > in many concurrent classes when compare-and-set (cas) is
> used- it is
> > an endless loop of competing threads trying to fight over an object
> > (,say, a queue's tail in order to connect a new element
> (reference)) .
> >
> > Wouldn't it be benefitial to perform a thread.Yield() after N
> > (pre-configured) unsuccessful CAS retries ? wouldnt it give better
> > overall performance ?
>
> It depends on the degree of contention you expect to experience.
>
> In most cases, the standard approach (retry continuously) is
> best.  Only when you are expecting very heavy contention,
> where you expect most CAS attempts to fail, is a more
> sophisticated backoff strategy beneficial.
>
> When there is no contention for a CAS, it always succeeds.  
> When multiple threads compete for a CAS, one will always win
> and make progress.  So the question is, what percent of CAS
> attempts will lose and need to be retried?  Only if this
> ratio is high will a better contention management strategy be
> a win.  This is a function of how many threads are involved,
> and the ratio of CAS to "other work".
>
> If your contention is so high that most CAS attempts fail,
> you might be better off with a lock, as locking automatically
> addresses the problem you raise fairly well, by blocking so
> as not to create more contention.
>
> _______________________________________________
> 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: propper way to use CAS ?

Brian Goetz
> Doesnt this presuppose that you are running on a system the is pre-emptive,
> So if you are running on a non pre-emptive system then the unsuccessful CAS
> retries will just continue wont they?

Until they eventually succeed.  But the point is, under real-world
conditions, they _will_ eventually succeed.

An uncontended CAS is always successful.  In every contended CAS, one
thread always succeeds.  Some thread always makes progress.

In order for a thread to continue retrying a CAS forever, it means that
other threads must be pounding really hard on that same atomic variable,
and always winning.  But each thread has an unbiased chance of winning
any given CAS.  On a system with N processors, that chance should be
close to 1/N.  So the expected number of retrys _in the absolute
unrealistic worst case, where every processing is doing nothing but
pounding on one atomic variable_, is N.  A far cry from "retrying
forever".

But in reality, you will never see contention like that, because
programs do other work besides pounding on a given memory location with
CAS.

It's not like locking, where one thread can do this:

   synchronized (globalLock) {
     Thread.sleep(Long.MAX_VALUE);
   }

and deny access to the lock to other threads.  In a CAS, someone always
makes progress, and in reality, every thread makes progress within a few
retries.

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

Re: propper way to use CAS ?

Chris Purcell
> But each thread has an unbiased chance of winning any given CAS.

Actually, this probably doesn't hold up on all processors. Biasing
success towards the current owner of the cache-line just makes good
sense, as it gives an increase in throughput.

Chris

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