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

Groups > comp.programming.threads > #106

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

Show all headers | View raw

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

Back to comp.programming.threads | Previous | Next — Previous 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