How does this MSDN CompareExchange sample not need a volatile read?

Question

I was looking for a thread-safe counter implementation using Interlocked that supported incrementing by arbitrary values, and found this sample straight from the Interlocked.CompareExchange documentation (slightly changed for simplicity):

private int totalValue = 0;

public int AddToTotal(int addend)
{
    int initialValue, computedValue;
    do
    {
        // How can we get away with not using a volatile read of totalValue here?
        // Shouldn't we use CompareExchange(ref TotalValue, 0, 0)
        // or Thread.VolatileRead
        // or declare totalValue to be volatile?           
        initialValue = totalValue;

        computedValue = initialValue + addend;

    } while (initialValue != Interlocked.CompareExchange(
        ref totalValue, computedValue, initialValue));

    return computedValue;
}

 public int Total
 {
    // This looks *really* dodgy too, but isn't 
    // the target of my question.
    get { return totalValue; }
 }

I get what this code is trying to do, but I'm not sure how it can get away with not using a volatile read of the shared variable when assigning to the temporary variable that is added to.

Is there a chance that initialValue will hold a stale value throughout the loop, making the function never return? Or does the memory-barrier (?) in CompareExchange eliminate any such possibility? Any insight would be appreciated.

EDIT: I should clarify that I understand that if CompareExchange caused the subsequent read of totalValue to be up to date as of the last CompareExchange call, then this code would be fine. But is that guaranteed?

Answer 1

If we read a stale value, then the CompareExchange won't perform the exchange - we're basically saying, "Only do the operation if the value really is the one we've based our calculation on." So long as at some point we get the right value, it's fine. It would be a problem if we kept reading the same stale value forever, so CompareExchange never passed the check, but I strongly suspect that the CompareExchange memory barriers mean that at least after the time through the loop, we'll read an up-to-date value. The worst that could happen would be cycling forever though - the important point is that we can't possibly update the variable in an incorrect way.

(And yes, I think you're right that the Total property is dodgy.)

EDIT: To put it another way:

CompareExchange(ref totalValue, computedValue, initialValue)

means: "If the current state really was initialValue, then my calculations are valid and you should set it to computedValue."

The current state could be wrong for at least two reasons:

• The initialValue = totalValue; assignment used a stale read with a different old value
• Something changed totalValue after that assignment

We don't need to handle those situations differently at all - so it's fine to do a "cheap" read so long as at some point we'll starting seeing up-to-date values... and I believe the memory barriers involved in CompareExchange will ensure that as we loop round, the stale value we see is only ever as stale as the previous CompareExchange call.

EDIT: To clarify, I think the sample is correct if and only if CompareExchange constitutes a memory barrier with respect to totalValue. If it doesn't - if we can still read arbitrarily-old values of totalValue when we keep going round the loop - then the code is indeed broken, and may never terminate.