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

Groups > comp.programming.threads > #96 > unrolled thread

What are the CPU-internal characteristics of CAS collision?

Back to article view | Back to comp.programming.threads

Contents

  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

#96 — What are the CPU-internal characteristics of CAS collision?

Hi everyone - 

I'm trying to understand the low-level mechanics of CAS on x86/x64 and 
I'd really appreciate some help/insight.

The reason I've been thinking about this is that I'm trying to reason 
about exponential backoff, and figure out in principle what the correct 
single unit of backoff delay should be.

If I took at a lock-free freelist benchmark, without exponential 
backoff, I see as the number of threads increase, performance rapidly 
flatlines.

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.  

My original - and I believe now mistaken - thought was that CAS was 
interfering with CAS.  By that I mean, the CAS instruction itself would 
destructively collide with another CAS, should they occur concurrently.  
Both would fail.  (Prolly because I was in the back of my mind thinking 
about ethernet).

This 'obviously' explains the results - all those CAS instructions 
operating concurrently, very few have a chance to fully execute before 
being destructively interrupted.

Having thought about it some more, I believe now this cannot be the 
case.  The CAS instruction does not in fact HAVE a failure mode.  It 
will tell you the destination is equal or not equal to the comparand.  
That's all.  It doesn't come back and say "oh, sorry, bumped into 
someone else".

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.

But now I'm confused.

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.

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.

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.

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).

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

I think therefore I do not understand CAS properly.

Reading Intel's Architecture Software Developer's Manual, I find that if 
all data is present in cache (which the situation I'm interested in), 
the cache coherency protocol takes care of CAS.

Drepper in his white paper describes LL/SC and how it works using MESI.

It seems reasonable to me for CAS to operate in a similar manner.

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.

So what happens?  what *is* happening with CAS?

What I do see is that as the thread count rises, less and less work is 
done - all available 'slots' certainly are not being used.  Something is 
causing this.  Is it destructive interference between CAS instructions?  
or it is a large number of RFO hogging the CPU->northbridge bus?

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.

[toc] | [next] | [standalone]

#97

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

[toc] | [prev] | [next] | [standalone]

#101

In article <87d3ki563g.fsf@justsoftwaresolutions.co.uk>, 
anthony.ajw@gmail.com says...
> Toebs Douglass <a@b.com> writes:

Thanks for your reply, Anthony.  I've been thinking it and a few other 
replies (elsewhere) over.
 
> > 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.

This I think I understand.

When a core completes a CAS, in x86/x64, there's always a write to 
memory, so even when the CAS isn't equal, the memory write and cache 
line invalidations still occur; the CAS only completes when the memory 
write has completed.

So, when there are no caches, just memory, and a whole bunch of cores, 
every time a core completes a CAS, every other cores cache line is now 
invalid, forcing a memory read for the next core to CAS.

If however some cores shared a common cache, and the core which just 
completed a CAS and the core about to perform the next CAS are in that 
group and so share that CAS, the memory read will in fact only need to 
occur from the shared cache, because that cache line will have been 
updated during the write to memory.

> > 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.

I understand, but I'm not sure I'm seeing this in the benchmark results 
(or, more likely, there's another factor I don't yet know about).  I'll 
explain in a bit.
 
> > 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.

Right.  Understood.
 
> > 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.

This I don't understand.  If the CAS operation stalls on the cache lin, 
how can there *be* a failure?
 
> > 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.

Which makes sense to me, except it doesn't quite show up in the 
benchmark results.

So, first the single thread case;

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00

Here we have maximum performance. Every 'slot' is used by the single 
thread.

Now we come to two threads on the same core;

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 1 1 334747444,16737372,2421,0.54

Here we still of course have the same number of 'slots' - a CAS takes as 
long as it takes - but we see they're evenly distributed between logical 
processors. This makes sense; one core locks the cache line, the other 
stalls, the first completes, the second gets the lock... they alternate. 
The destination remains in L1 cache with the cache line being in the 
modified state; we never need to re-read the destination from memory, so 
in that sense we're just like the one thread case.

Now we come to two threads on different cores;

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 1 0 1 136401284,6820064,50706,0.22

Here we see our first big slow down. Our maximum theoretical scaling is 
0.5, but we're at 0.22. How come? well, each thread is trying to lock 
the same cache line (in its own cache, of course) which is fine - but 
the problem is when a core gets the lock, it will need to re-read the 
destination from memory because its cache line will have been marked 
invalid by the other core having modified its copy of the data. So we 
put the slow down to the memory reads we're having to do.

Now we come to four threads, two per core.

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
1 1 1 1 111105898,2777647,40399,0.09

Here we see the total number of ops is actually only slightly less than 
one thread per core, although of course the scaling is much worse, since 
we now have four threads, not two.

In the one thread per core scenario, every CAS begins with a read of 
memory, since the other core has invalided the CASing cores cache line.

In this scenario, when a core finishes a CAS and releases the cache 
lock, three threads are competing for the lock, two on another core, one 
on the same core. So two thirds of the time we need to re-read memory at 
the start of CAS; one third of the time we do not.

So we should be FASTER. But we are in fact SLOWER.

0% memory re-reading gives 33,474,744.4 total ops per second (two 
threads, same core)
75% memory re-reading, gives 11,110,589.8 total ops per second (four 
threads, two per core)
100% memory re-reading, gives 13,640,128.4 total ops per second (two 
threads, one per core)

And this puzzles me. The observed facts do not fit the theory.

[toc] | [prev] | [next] | [standalone]

#103

In article <MPG.281bdac8735d6d229896bc@news-europe.giganews.com>, 
a@b.com says...
> In this scenario, when a core finishes a CAS and releases the cache 
> lock, three threads are competing for the lock, two on another core, one 
> on the same core. So two thirds of the time we need to re-read memory at 
> the start of CAS; one third of the time we do not.
> 
> So we should be FASTER. But we are in fact SLOWER.
> 
> 0% memory re-reading gives 33,474,744.4 total ops per second (two 
> threads, same core)
> 75% memory re-reading, gives 11,110,589.8 total ops per second (four 
> threads, two per core)
> 100% memory re-reading, gives 13,640,128.4 total ops per second (two 
> threads, one per core)

That should be 66%, not 75%.  It's two thirds, not three quarters!

[toc] | [prev] | [next] | [standalone]

#106

Toebs Douglass <a@b.com> writes:

>> 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.
>
> This I don't understand.  If the CAS operation stalls on the cache lin, 
> how can there *be* a failure?

With CMPXCHG, "failure" means that the expected value is not the same as
the read value. This is independent of where the read value came from,
or whether the CPU had to wait to get it.
  
> Now we come to four threads, two per core.
>
> L L L L total ops,mean ops/sec per thread,standard deviation,scalability
> 1 1 1 1 111105898,2777647,40399,0.09
>
> Here we see the total number of ops is actually only slightly less than 
> one thread per core, although of course the scaling is much worse, since 
> we now have four threads, not two.
>
> In this scenario, when a core finishes a CAS and releases the cache 
> lock, three threads are competing for the lock, two on another core, one 
> on the same core. So two thirds of the time we need to re-read memory at 
> the start of CAS; one third of the time we do not.
>
> So we should be FASTER. But we are in fact SLOWER.
>
> 0% memory re-reading gives 33,474,744.4 total ops per second (two 
> threads, same core)
> 75% memory re-reading, gives 11,110,589.8 total ops per second (four 
> threads, two per core)
> 100% memory re-reading, gives 13,640,128.4 total ops per second (two 
> threads, one per core)
>
> And this puzzles me. The observed facts do not fit the theory.

There is far more to the intricacies of CPU cache coherency than is
covered by my simple explanation, especially in the face of
hyperthreading. Your "two thirds of the time  we need to re-read memory,
one third of the time we do not" is probably wrong, or
oversimplified.

I have a general guideline "more contention => worse peformance", which
this data does fit --- 4 threads is more contention than 2, even if they
are paired off on only two CPU cores.

If you really want to know more detail, I would suggest finding a
friendly CPU hardware engineer.

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web