Fields read from/written by several threads, Interlocked vs. volatile

Question

There are a fair share of questions about Interlocked vs. volatile here on SO, I understand and know the concepts of volatile (no re-ordering, always reading from memory, etc.) and I am aware of how Interlocked works in that it performs an atomic operation.

But my question is this: Assume I have a field that is read from several threads, which is some reference type, say: public Object MyObject;. I know that if I do a compare exchange on it, like this: Interlocked.CompareExchange(ref MyObject, newValue, oldValue) that interlocked guarantees to only write newValue to the memory location that ref MyObject refers to, if ref MyObject and oldValue currently refer to the same object.

But what about reading? Does Interlocked guarantee that any threads reading MyObject after the CompareExchange operation succeeded will instantly get the new value, or do I have to mark MyObject as volatile to ensure this?

The reason I'm wondering is that I've implemented a lock-free linked list which updates the "head" node inside itself constantly when you prepend an element to it, like this:

[System.Diagnostics.DebuggerDisplay("Length={Length}")]
public class LinkedList<T>
{
    LList<T>.Cell head;

    // ....

    public void Prepend(T item)
    {
        LList<T>.Cell oldHead;
        LList<T>.Cell newHead;

        do
        {
            oldHead = head;
            newHead = LList<T>.Cons(item, oldHead);

        } while (!Object.ReferenceEquals(Interlocked.CompareExchange(ref head, newHead, oldHead), oldHead));
    }

    // ....
}

Now after Prepend succeeds, are the threads reading head guaranteed to get the latest version, even though it's not marked as volatile?

I have been doing some empirical tests, and it seems to be working fine, and I have searched here on SO but not found a definitive answer (a bunch of different questions and comments/answer in them all say conflicting things).

Answer 1

Your code should work fine. Though it is not clearly documented the Interlocked.CompareExchange method will produce a full-fence barrier. I suppose you could make one small change and omit the Object.ReferenceEquals call in favor of relying on the != operator which would perform reference equality by default.

For what it is worth the documentation for the InterlockedCompareExchange Win API call is much better.

This function generates a full memory barrier (or fence) to ensure that memory operations are completed in order.

It is a shame the same level documenation does not exist on the .NET BCL counterpart Interlocked.CompareExchange because it is very likely they map to the exact same underlying mechanisms for the CAS.

Now after Prepend succeeds, are the threads reading head guaranteed to get the latest version, even though it's not marked as volatile?

No, not necessarily. If those threads do not generate an acquire-fence barrier then there is no guarantee that they will read the latest value. Make sure that you perform a volatile read upon any use of head. You have already ensured that in Prepend with the Interlocked.CompareExchange call. Sure, that code may go through the loop once with an stale value of head, but the next iteration will be refreshed due to the Interlocked operation.

So if the context of your question was in regards to other threads who are also executing Prepend then nothing more needs to be done.

But if the context of your question was in regards to other threads executing another method on LinkedList then make sure you use Thread.VolatileRead or Interlocked.CompareExchange where appropriate.

Side note...there may be a micro-optimization that could be performed on the following code.

newHead = LList<T>.Cons(item, oldHead);

The only problem I see with this is that memory is allocated on every iteration of the loop. During periods of high contention the loop may spin around several times before it finally succeeds. You could probably lift this line outside of the loop as long as you reassign the linked reference to oldHead on every iteration (so that you get the fresh read). This way memory is only allocated once.

Answer 2

Does Interlocked guarantee that any threads reading MyObject after the CompareExchange operation succeeded will instantly get the new value, or do I have to mark MyObject as volatile to ensure this?

Yes, subsequent reads on the same thread will get the new value.

Your loop unrolls to this:

oldHead = head;
newHead = ... ;

Interlocked.CompareExchange(ref head, newHead, oldHead) // full fence

oldHead = head; // this read cannot move before the fence

---

EDIT:

Normal caching can happen on other threads. Consider:

var copy = head;

while ( copy == head )
{
}

If you run that on another thread, the complier can cache the value of head and never see the update.