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).

Shul

This is .NET, so it should not depend on the underlying memory model as far as I know? But for the record I'm using x86-32 and x86-64, not IA-64 – Shul

@thr: The underlying mm does matter. The Microsoft CLR provides stronger guarantees than the ECMA CLI specification, so if you want to be sure that your code will work on any platform then you should assume only the (weaker) guarantees offered by the ECMA spec. – Shamanism

The .NET memory model already promises atomicity for object references. The posted code cannot work, it prepends multiple copies of the item when another thread is also modifying the head field. Not using lock to protect head just buys you a guaranteed threading race. Using a memory barrier doesn't change this, might as well omit it. The list implodes when another thread removes the head node. – Tibetoburman

@HansPassant: Nah, it shouldn't as far as I can tell. The Interlocked operation will fail if head got modified by another thread. The loop will spin around and try again. – Iodine

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.

Iodine

Thank you, finally someone giving a clear cut answer. Marked as correct. Also thanks for the performance opt. tip, while you are correct that this would work in my small example case my real world code is a bit more complex and this would not work. – Shul

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.

Dicrotic

Not trying to be rude, but this was not my question. I asked about any threads, not the same thread. – Shul

Are you 100% sure of this (your edit), I have seen conflicting information about this (some people saying what you do, some people saying different things, etc.) and if you look into the Mono source code their concurrent collections do not use volatile fields, which I would assume to be needed? – Shul

Though I assume since the comparisons to check if the operation is "ok" always is done with Interlocked.CompareExchange<T>() (talking about monos concurrent collections now) this would cause them to always verify the latest value and in case it's outdated their CPU caches would be refreshed. – Shul

After a fence, the caches in the cpus will be coherent, so any actual read instruction executed on any core will see the new value. However, the compiler could theoretically optimise away the read altogether. – Dicrotic

Nicholas: Perfect, this was the answer I was looking for – Shul

@Shul Yes, a CompareExchange will always read the latest value – Dicrotic