Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #97

Re: What are the CPU-internal characteristics of CAS collision?

Show key headers only | View raw

Toebs Douglass <a@b.com> writes:

> Release 7 Lock-Free Freelist Benchmark #1
>
>    M
>    N
>    S
>   L3U
> L2U L2U
> L1D L1D
> L1I L1I
>  P   P
> L L L L total ops,mean ops/sec per thread,standard deviation,scalability
> 0 0 0 1 310134488,31013449,0,1.00
> 0 1 0 1 136313300,6815665,38365,0.22
>
> 0 1 0 1 136401284,6820064,50706,0.22
> 1 1 1 1 111134328,2778358,23851,0.09
>
> 0 0 1 1 334747444,16737372,2421,0.54
> 1 1 1 1 111105898,2777647,40399,0.09
>
> As we know, live-lock can occur, where each thread prevents the others 
> from progressing.  

> Destructive interference IS occurring, but it's occurring at a higher 
> level, in the data structure algorithm itself.  When we push or pop 
> from/to the freelist, we are actually TRYING to swap.  We need the 
> destination to be stable for long enough that we can read it, do 
> whatever work we need to do, and then find it unchanged so we can 
> complete our push/pop.
>
> If other threads keep CASing, destination isn't stable - it keeps 
> changing - and we keep having to retry our operation.

Correct.

> What we see is that a single thread performs about 30 million push/pop 
> operations.  Destination has to be stable for the duration of one of 
> these operations, for the operation to succeed, so we see there are 30 
> million 'slots'.  If we have two threads, then the maximum theoretical 
> performance we can have is 15 million operations per thread; each thread 
> using half the slots.

That's correct, if you've got two threads on a single core, or two cores
sharing a cache.

> Now let's come back to CAS.  CAS has no failure mode.  So what's 
> happening when second thread tries to CAS when another thread is already 
> CASing?  well, the second thread will fail at the data structure level, 
> since the swap couldn't occur, so it will retry the swap.

The first CAS will lock the cache line. The second CAS, executing on
another core, will stall the CPU until the cache line can be transferred
to the second core's cache.

> But now imagine we have LOTS of threads.  The first thread to begin a 
> CAS will succeed (assuming each CAS takes exactly the same time - not 
> true, but that assumption doesn't change anything fundamental, so it's 
> okay to reason with).  All the others will fail.

Yes, but all the others will have to wait for the new value to transfer
from the successful core's cache, in order to return the new value.

> But once the first thread has finished, the very next thread who reads 
> the new destination value will have his CAS succeed (and all the other 
> threads, still executing their CASs or now beginning new CASs, will 
> fail).

True.

> So why do we not see perfect scaling?  because every 'slot' should be 
> being used!

It takes an order of magnitude (if not several orders of magnitude)
longer to transfer the new value from one CPU to another than it does
for the same CPU to rerun a second consecutive CAS operation on the same
location.

CAS contention can cause cache ping-pong, which causes processor stalls
and sucks performance.

> Let's consider the two thread case.  First thread begins its CAS.  The 
> cache line with the destination is in its cache and marked exclusive.
>
> Second thread begins to CAS.  The first core sends its cache line over 
> to the second core and both cores have that cache line marked shared.
>
> First thread completes the CAS and writes to the cache line (the write 
> always occurs on x86/x64, even if the compare was false; it just writes 
> the original value).
>
> The act of writing marks the cache line as modified; a RFO occurs, 
> causing the second core to mark its cache line as invalid.
>
> The second thread comes to complete its CAS and notices its cache line 
> is invalid... and then, what?  I find it hard to believe the instruction 
> is in the CPU internally looped until it succeeds - although I wonder, 
> because LL/SC on ARM requires *you* in your assembly to do that kind of 
> loop!  But the CAS instruction knows that the value of destination has 
> changed, so the results of its compare are invalid.  But there's no 
> error possible with CAS; it always returns true or false for the 
> compare.  But even if the instructions do loop until complete, I'd still 
> expect perfect scaling.  Each 'slot' should still be used.

On x86, CMPXCHG returns the "old" value on failure. If it fails, it must
therefore wait for the cache line to be transferred from the successful
CPU. This is a **slow** operation in terms of processor cycles.

> What I do note with considerable interest is that two threads on the 
> same physical core scale perfectly.  Something special and different is 
> happening in that case - two threads on separate physical cores scale 
> half as well.  But it's not enough of a clue to explain it all.

Two threads that share an L1 cache will not suffer from the cache
ping-pong effects. If they have different L1 caches, but share an L2
cache the effect will be more noticable, but not as bad as if they only
share an L3 cache, which is still lots better than processors that don't
share any cache.

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What are the CPU-internal characteristics of CAS collision? Toebs Douglass <a@b.com> - 2011-04-19 19:06 +0200
  Re: What are the CPU-internal characteristics of CAS collision? Anthony Williams <anthony.ajw@gmail.com> - 2011-04-19 21:38 +0100
    Re: What are the CPU-internal characteristics of CAS collision? Toebs Douglass <a@b.com> - 2011-04-22 19:35 +0200
      Re: What are the CPU-internal characteristics of CAS collision? Toebs Douglass <a@b.com> - 2011-04-22 22:35 +0200
      Re: What are the CPU-internal characteristics of CAS collision? Anthony Williams <anthony.ajw@gmail.com> - 2011-04-26 07:57 +0100

csiph-web