Interlocked.CompareExchange if not equal? [duplicate]

Question 1

A more efficient (less bus locking and less reads) and simplified implementation of what Marc posted:

static int InterlockedIncrementAndClamp(ref int count, int max)
{
    int oldval = Volatile.Read(ref count), val = ~oldval;

    while(oldval != max && oldval != val)
    {   
        val = oldval;
        oldval = Interlocked.CompareExchange(ref count, oldval + 1, oldval);
    }

    return oldval + 1;
}

If you have really high contention, we might be able to improve scalability further by reducing the common case to a single atomic increment instruction: same overhead as CompareExchange, but no chance of a loop.

static int InterlockedIncrementAndClamp(ref int count, int max, int drift)
{
    int v = Interlocked.Increment(ref count);

    while(v > (max + drift))
    {
        // try to adjust value.
        v = Interlocked.CompareExchange(ref count, max, v);
    }

    return Math.Min(v, max);
}

Here we allow count to go up to drift values beyond max. But we still return only up to max. This allows us to fold the entire op into a single atomic increment in most cases, which will allow maximum scalability. We only need more than one op if we go above our drift value, which you can probably make large enough to make very rare.

In response to Marc's worries about Interlocked and non-Interlocked memory access working together:

Regarding specifically volatile vs Interlocked: volatile is just a normal memory op, but one that isn't optimized away and one that isn't reordered with regards to other memory ops. This specific issue doesn't revolve around either of those specific properties, so really we're talking non-Interlocked vs Interlocked interoperability.

The .NET memory model guarantees reads and writes of basic integer types (up to the machine's native word size) and references are atomic. The Interlocked methods are also atomic. Because .NET only has one definition of "atomic", they don't need to explicitly special-case saying they're compatible with each-other.

One thing Volatile.Read does not guarantee is visibility: you'll always get a load instruction, but the CPU might read an old value from its local cache instead of a new value just put in memory by a different CPU. x86 doesn't need to worry about this in most cases (special instructions like MOVNTPS being the exception), but it's a very possible thing with others architectures.

To summarize, this describes two problems that could affect the Volatile.Read: first, we could be running on a 16-bit CPU, in which case reading an int is not going to be atomic and what we read might not be the value someone else is writing. Second, even if it is atomic, we might be reading an old value due to visibility.

But affecting Volatile.Read does not mean they affect the algorithm as a whole, which is perfectly secure from these.

The first case would only bite us if you're writing to count concurrently in a non-atomic way. This is because what could end up happening is (write A[0]; CAS A[0:1]; write A[1]). Because all of our writes to count happen in the guaranteed-atomic CAS, this isn't a problem. When we're just reading, if we read a wrong value, it'll be caught in the upcoming CAS.

If you think about it, the second case is actually just a specialization of the normal case where the value changes between read and write -- the read just happens before we ask for it. In this case the first Interlocked.CompareExchange call would report a different value than what Volatile.Read gave, and you'd start looping until it succeeded.

If you'd like, you can think of the Volatile.Read as a pure optimization for cases of low contention. We could init oldval with 0 and it would still work just fine. Using Volatile.Read gives it a high chance to only perform one CAS (which, as instructions go, is quite expensive especially in multi-CPU configurations) instead of two.

But yes, as Marc says -- sometimes locks are just simpler!

Question 2

There isn't a "compare if not equal", however: you can test the value yourself first, and then only do the update if you don't get a thread race; this often means you may need to loop if the second test fails. In pseudo-code:

bool retry;
do {
    retry = false;
    // get current value
    var val = Interlocked.CompareExchange(ref field, 0, 0);
    if(val != max) { // if not maxed
        // increment; if the value isn't what it was above: redo from start
        retry = Interlocked.CompareExchange(ref field, val + 1, val) != val;
    }        
} while (retry);

But frankly, a lock would be simpler.