Overuse of Interlocked.exchange?

Question

I am trying to understand correct usage of Interlocked.Exchange, so I am implementing a simple sorted LinkedList with add and remove functionality.

If this was not a threadsafe list, obviously to find the insertion point, you'd have something like the below to find the correct point to insert then new node.

    public void Insert(int newValue)
    {
        var prev = _header;
        Node curr = _header.Next;

        while(curr != null && curr.value > newValue )
        {
            prev = curr;
            curr = curr.Next;
        }
        var newNode = new Node(newValue, curr);
        prev.Next = newNode;
    }

Below is my take on how you'd have to do this for a concurrent list. Is there too much Interlocked.Exchange's going on? Without this, would the insert still be threadsafe? Would hundreds or thousands of Interlocked operations cause bad performance?

    public void InsertAsync(int newValue)
    {
        var prev = _header;
        Node curr = new Node(0, null);
        Interlocked.Exchange(ref curr, _header.Next);

        while (curr != null && curr.value > newValue)
        {
            prev = Interlocked.Exchange(ref curr, curr.Next);
        }
        //need some locking around prev.next first, ensure not modified/deleted, etc..
        //not in the scope of this question.
        var newNode = new Node(newValue, prev.Next);
        prev.Next = newNode;
    }

I understand that, for example, curr = curr.next is an atomic read, but can I be sure that a specific thread will read the most up to date value of curr.next, without the Interlocked?

Answer 1

Using an Interlocked method does two things:

1. It performs some series of operations that normally wouldn't be atomic, and makes them effectively atomic. In the case of Exchange you doing the equivalent of: var temp = first; first=second; return temp; but without risk of either variable being modified by another thread while you're doing that.
2. It introduces a memory barrier. It's possible for compiler, runtime, and or hardware optimizations to result in different threads having a local "copy" of a value that is technically in shared memory (normally as a result of caching variables). This can result in it taking a long time for one thread to "see" the results of a write in another thread. A memory barrier essentially syncs up all of these different versions of the same variable.

So, onto your code specifically. Your second solution isn't actually thread safe. Each individual Interlocked operation is atomic, but any number of calls to various Interlocked calls aren't atomic. Given everything that you're methods are doing, your critical sections are actually much larger; you'll need to use lock or another similar mechanism (i.e. a semaphore or monitor) to limit access to sections of code to only a single thread. In your particular case I'd imagine that the entirety of the method is a critical section. If you're really, really careful you may be able to have several smaller critical blocks, but it will be very difficult to ensure that there are no possible race conditions as a result.

As for performance, well, as it is the code doesn't work, and so performance is irrelevant.

Answer 2

Implementing a lock-free linked list is quite a bit more complicated than this. I strongly recommend that you don't do it. Just use plain old monitors instead. If this is just for interests sake, than you need to do some research into lock-free algorithms.

To more directly answer your question, the cost of an interlocked operation depends on the amount of contention over the variables. In a contention free scenario (e.g. single threaded), the cost is extremely minimal. As the number of concurrent accesses rise, the cost increases. The reason is that an interlocked operation isn't really lock free. It's simply using a hardware lock instead of a software one. For this reason, lock-free algorithms often do not perform as well as you would intuitively expect.

Answer 3

You are only protecting the assignments, but they are atomic anyway. You should check if the Exchanged actually succeeded.

But that still wouldn't make your list thread-safe, a concurrent thread could be inserting a new value larger than your newValue before your insert point. I think the list could even end up being broken.