How to do compare and increment atomically?

Question

In my attempt to develope a thread-safe C++ weak pointer template class, I need to check a flag that indicating the object is still alive, if yes then increment the object's reference count and I need to do the both steps atomically.

I know the existance of intrinsics functions provided by the compiler, for instance _InterlockedCompareExchange() and _InterlockedIncrement(). But what I want is an interlockedCompareIncrement() function, is there an efficient way to simulate this intrinsic using other primitives, at least on the Windows x86 platform?

Roquelaure

If this is on Windows, you should say so. – Sobriquet

Answer 1

Suppose that value is your flag variable. It should be declared volatile.

long curvalue;
long newvalue;

do
{
    curvalue = value;
    newvalue = curvalue + 1;
}
while( _InterlockedCompareExchange( &value, newvalue, curvalue ) != curvalue );

As you see you can generalize this to whatever kind of arithmetic you need by changing the operations that are applied to calculate newvalue.

If you want to compare two values at the same time, your best bet is to pack both values into a single variable, and then operate on that single variable. Since you're using a flag combined with a reference count, I'd recommend using the lowest bit of value as the 'alive' flag, and then increment/decrement by 2 at a time. This allows you to encode both the flag and the reference count into a single 32-bit variable.

Twinkle

It's seems what I am looking for, I will look deeper in it. – Roquelaure

+1: I was looking for an atomic IncIfNot function. This is also possible to write with a loop and _InterlockedCompareExchange()! – Zygophyte

Answer 2

If you want your library to run on multiple CPU or multiple core machines you have to use the hardware support provided by the CPU. Here are some references for you:

http://en.wikipedia.org/wiki/Test-and-set http://software.intel.com/en-us/forums/showthread.php?t=47498

Or you have to use locking mechanism provided by the OS. Such as

http://msdn.microsoft.com/en-us/library/ms684841%28VS.85%29.aspx or http://en.wikipedia.org/wiki/POSIX_Threads

Gloria

Answer 3

Since you are in C++, you can write your own assembly code.

Perhaps this is related to Implement atomic increment using atomic swap?

Salmanazar