Re: Lockless 63-bit Counter

From: Michael Brown (see_at_signature.below)
Date: 03/11/04 

Date: Thu, 11 Mar 2004 18:22:04 +0000 (UTC)

Terje Mathisen wrote:
> Matt Taylor wrote:
>
>> "Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote in message
>>>> are simply references to lockless algorithms in comments.
>>>
>>> Isn't the ls signbit then just a lock for half the counter?
>>>
>>> Besides, the 64-bit CMPXCHG8B (spelling?) is designed for this,
>>> isn't it?
>>
>> DCAS is possible, but this counter will be incrementing somewhere
>> around once every ~10-20 cycles on every CPU in the system. I would
>> expect an algorithm based on DCAS to have horrible performance in
>> such high-contention scenarios. Threads would frequently be
>> re-computing the next counter value and racing for it with each race
>> incuring the lock penalty.
>
> With 10-20 cycles between updates, _all_ algorithms will thrash!
>
> Remember you _have_ to aquire the relevant cache line ('read for
> ownership') before you can start any kind of update.
[...]
> OK, I'll take a look, but I warn you, you _must_ look for a more
> distributed way to do it if you want 10-20 cycle updates of a single
> counter!
[...]

(note: ignoring the Opteron, I don't understand the HT bus well enough to
comment on that)

Just to put some numbers on this ... most CPUs have 64 byte cache lines or
bigger. So to pull 64 bytes over the bus on a CPU with a multiplier of <m>
will take at least m*4 cycles (DDR interface) or m*2 cycles (QDR interface).
This equates to somewhere in the order of 44 (MP1700) to 66 (MP2800) cycles
on an Athlon MP based machine, and 32 (200MHz FSB Xeon 3.2) to 64 (100MHz
FSB Xeon 3.2) cycles on a Xeon platform. Though on the Xeon-based systems,
the shared-bus protocol is worse than the Athlon's EV6 protocol, so you're
probably looking at similar "minimum" latencies for each.

In any case, the main slowdown of your program will be the CPUs fighting
over the cache line. The key to getting reasonable performance will be to
change the global counter access rate to once every few thousand cycles or
so. 

--
Michael Brown
www.emboss.co.nz : OOS/RSI software and more :)
Add michael@ to emboss.co.nz - My inbox is always open

Relevant Pages