Is CAS (compare and swap) thread safe while collection is iterated on?

Question

(1) In the below program if Swap and Iterate functions are called on two different threads, would it be safe to swap while collection is iterated on?

(2) Do I really need interlocked exchange as read/write to references are atomic (guaranteed by CLR), suppose Interlocked is required for release semantics for weak memory models?

class someClass
{
       public void Swap()
       {
           Queue<SomeType> newQueue = new Queue<SomeType>();
           var oldQueue = Interlocked.Exchange(ref queue, newQueue);
           //Perform operation on old queue
       }

       public void Iterate()
       {
           foreach(var someTypeObject in queue)
           {
              //Do Something
           }
        }

       Queue<SomeType> queue = new Queue<Sometype>();
}

If you have two questions then please **post two questions**. Adding more questions to an existing question is confusing and the later questions probably won't get answers. — Eric Lippert, Jan 23 '14 at 14:49
Now, with regard to your second question: overloads of Interlocked Exchange *exist* for types which are atomic to read and write. Why would they be designed, implemented, tested and shipped if they were never necessary? — Eric Lippert, Jan 23 '14 at 14:51

score 1 · Accepted Answer · edited May 23 '17 at 10:31

Assuming you don't modify oldQueue in Swap (i.e. modifying the collection while it's being enumerated), then yes it's safe. Your foreach expands to:

{
    IEnumerator e = ((IEnumerable)(queue)).GetEnumerator();
    try {
        Sometype someTypeObject;
        while (e.MoveNext()) {
            someTypeObject = (Sometype)e.Current;
            // loop body
       }
    }
    finally {
        // Dispose e
    }
}

From the C# Specification, Section 8.8.4: The foreach statement

In other words, the foreach loop in Iterate calls queue.GetEnumerator() and from then on uses the reference to the IEnumerator for queue. Changing out what queue points to no longer has any effect on the enumerator in the loop.

Regarding your second question, you need to use Interlocked.Exchange only if you intend to use the old value of the swap (and want that to be atomic). Otherwise if you're just performing an assignment you don't need it since reference assignments are always atomic (see this question for more explanation).

Minor quibble, but variable assignments are not always atomic; reference assignments are always atomic, but a variable assignment of an Int64 in x86 requires multiple instructions at the machine level. — Dan Bryant, Jan 23 '14 at 14:40
@Dan You're right, I paraphrased [this page from the spec](http://msdn.microsoft.com/en-us/library/aa691278%28VS.71%29.aspx) a bit too loosely. I've updated my answer. Thanks! — Patrick Quirk, Jan 23 '14 at 14:44

score 1 · Answer 2 · answered Jan 23 '14 at 14:35

This depends on the operations you perform on oldQueue; if you Swap in the middle of an Iterate, the iteration will still be over the old queue, so if you perform mutating operations on the old queue, this can break the iteration. This should be safe in the other direction (if you call Iterate in the middle of a Swap), as the iteration will be over the new (empty) queue, though it's unclear what you would want to do with the empty queue.

In general, lock-free operations are rarely necessary for performance and there are lots of subtle issues that can pop up. You still have to be careful with locks, but they are much less likely to bite you than trying to do clever things with Interlocked. It's hard to say what the proper locking design is for your code given just what you've posted, but do consider whether possible marginal performance improvements are worth the risk and maintainability cost of a lock-free design.

Is CAS (compare and swap) thread safe while collection is iterated on?

2 Answers2