Using Interlocked.CompareExchange with a class

Question

System.Threading.Interlocked.CompareExchange operator provides atomic (thus thread-safe) C# implementation of the Compare-And-Swap operation.

For example int i = 5; Interlocked.CompareExchange(ref i, 10, 5); After this command, the int i would have a value = 10. And also the compare and exchange happens atomically (single operation).

When I tried using this with a class instance, the compare fails and the values are not exchanged.

   public class X
   {
       public int y;
       public X(int val) { y = val; }
   }

Now when I do

    X a = new X(1);
    X b = new X(1);
    X c = new X(2);
    Interlocked.CompareExchange<X>(ref a, c, b);

The compare and Exchange operation fails. So, I overrided the Equals and the == operator for the class X as

    public override bool Equals(object obj) { return y == ((X) obj).y; }

So, now I get Interlocked.Equals(a,b) as true, but the CompareExchange operations still fails.

Is there any method to do this? I want to compare two class instances and assign one of them a value based on the comparision.

Sciamachy

I would guess that CompareExchange uses ReferenceEquals to compare a and b, which makes sense. Your Equals override is only recommended for immutable types, have you thought carefully what Equals behaviour you want/need ? – Mulvey

Unfortunately, it isn't documented, how equality is determined in this context. – Cube

@Henk Suppose that I want the behaviour as above where two class instances are equal when their member y has the same value. – Sciamachy

As @jaff explains below, that could not be made atomic. – Mulvey

Your example is broken. "After this command, the int i would have a value = 10" - only if the value returned by CompareExchange is 5 (or 10 :-)). This may have been simplified example code, but I've seen a lot of broken code where people forget that you need to check that the CompareExchange was successful before continuing. – Better

Answer 1

No. It can't be done.

Interlocked.CompareExchange basically maps directly to an assembly instruction which is able to atomically compare and swap the contents of a memory address. I believe in 32-bit mode, a 64-bit version of the instruction is available (as well as 32- and 16-bit versions), and in 64-bit mode, I think a 128-bit version is available. But that's all. The CPU doesnt' have a "swap .NET class based on its specific Equals function" instruction.

If you want to swap arbitrary objects, using arbitrary equality functions, you have to do it yourself, using locks or other synchronization mechanisms.

There is an overload of the Interlocked.CompareExchange function which works on object references, but it uses reference equality for the above reason. It simply compares the references, and then swaps them.

In response to your comment, using structs would not solve the problem. Again, the CPU can only atomically compare and swap values of certain fixed sizes, and it has no notion of abstract datatypes. Reference types can be used because the reference itself has a valid size, and can be compared against another reference by the CPU. But the CPU knows nothing about the object that the reference points to.

Submarginal

Thanks. Using locks defeats the purpose of using atomic operations for various reasons, but it seems i dont have much choice. Also, I was wondering it that operation supports swapping struct as they are not reference types. – Sciamachy

@Bhargav: No, it doesn't, as described in the documentation of that method: "This method only supports reference types." – Cube

@Bhargav: structs are no better. I added some more detail to my answer to hopefully explain it. The CPU just blindly compares two references (which are basically pointers, or memory addresses), and swaps those. It doesn't know anything about what the reference points to, and it doesn't know that you've defined special ways to compare those objects. It sees the two references as opaque chunks of data, and checks that they store the same bit pattern (they point to the same object) – Submarginal

Answer 2

I feel there is some some diffuse confusion throughout this page. First, a commentator is correct that the question contains an dangerous assumption:

int i = 5; 
Interlocked.CompareExchange(ref i, 10, 5);

After this command, the int i would have a value = 10.

No, only if the value of i hasn't changed to a value other than 5 in the meantime. Although that seems improbable in the code shown here, the whole point of using CompareExchange is that it should be possible, so it's a critical technicality here. I worry that the OP may not understand the purpose of Interlocked.CompareExchange, particularly because he is not examining the return value (see below).

Now the text of the original question was:

"Is there any method to do this? I want to compare two class instances and assign one of them a value based on the comparison."

Since there's no viable antecedent for the word "this", we should perhaps consider as the question here the sentence which comes after, giving the paraphrase:

"Is there any way to compare two class instances and assign one of them a value based on the comparison?"

Unfortunately, this question is still unclear, or possibly has little to do with atomic operations. Firstly, you can't "assign [a class instance] a value." It just doesn't make sense. A reference to a class instance is a value, but there's no way to "assign" anything to a class instance itself. That's a major difference versus value types, which can be assigned to each other. You can create an instance using the new operator, but you'll still just get a reference to it. Again, these may seem like technicalities, but are critical points if the question is truly meant to concern lock-free concurrency.

Next, the Interlocked.CompareExchange function doesn't condition a storage location upon a value, but rather it conditionally stores a value to a (given) location, meaning that it either stores the value (success), or leaves the storage location unchanged (failure), while reliably indicating which of these occurred.

This means that the phrase "based on the comparison" is incomplete about exactly what the alternative actions are supposed to be. Looking at the earlier part of the OP's question, one best guess might be that the question is looking to conditionally manipulate the instance references, and atomicity is a red herring. It's hard to know because, as noted above, CompareExchange (which was used to state the question) doesn't "swap" two values in memory, it only possibly "stores" one value.

X a = new X(1);
X b = new X(1);
X c = new X(2);

if (a.y == b.y)
    a = c;
else
    // ???

With the Equals overload, this could be streamlined:

if (a == b)
    a = c;
else
    // ???

The OP's focus on equality of the internal field y seems to increase the likelihood that this interpretation of the question is on the right track. But obviously, answers along these lines have nothing to do with Interlocked.CompareExchange. We would need more information to know why the OP thinks the assignment has to be atomic.

So alternatively then, we should note that it is also possible to atomically swap the y values in the existing instances:

var Hmmmm = Interlocked.CompareExchange(ref a.y, c.y, b.y);

Or swap instance references, and by now it now should be obvious that equating references is only defined in terms of "reference equality":

var Hmmmm = Interlocked.CompareExchange(ref a, c, b);

To proceed from here, the question would need more clarity. For example, to restate a comment made elsewhere on this page, but more strongly, it is an error to not examine the return value of Interlocked.CompareExchange.

This is why I stored the return value in the example above, and how I deemed its name appropriate. To not branch on the return value is to not understand the basic principles of lock-free ("optimistic") concurrency, a discussion of which is beyond the scope of this question. For an excellent introduction, see Concurrent Programming on Windows by Joe Duffy.

Finally, I think it's quite unlikely that the OP really needs to atomically store a class references based on arbitrary considerations, because this is an extremely specialized operation that's typically only necessary at the very crux of a comprehensive lock-free system design. But (contrary to another answer) it's certainly possible along the lines of what @supercat describes.

So please don't get the impression that you can't write lock-free code in .NET, or that class references are any kind of problem for the Interlocked operations; in fact it's actually quite the opposite: if you actually need to do an atomic operation which selects between two different storage locations or otherwise affects multiple memory locations, it's simple to use a design where the entangled locations are wrapped in a trivial containing class which then gives you a single reference that can be atomically swapped in lock-free fashion. Lock-free coding is a breeze in .NET, since its less hassle to memory-manage retry objects for the rare cases where the optimistic path fails.

Suffice it to say that, in my experience, there is no essential aspect of lock-free concurrency that I have not been able to achieve in C#/.NET/CLR, even if it's sometimes a bit rough around the edges, as you might ascertain from https://mcmap.net/q/665673/-c-interlocked-exchange.

Prot

Answer 3

The normal use of Interlocked.CompareExchange is in the pattern:

SomeType oldValue, newValue;
do
{
  oldValue = someField;
  newValue = [Computation based on oldValue]
} while (CompareExchange(ref someField, newValue, oldValue) != oldValue);

The basic idea is that if the field doesn't get changed between the time it's read into oldValue and the time the CompareExchange gets processed, then newValue will hold the value that should be stored into the field. If something else changes it during the computation, the results of the computation will be abandoned and the computation will be repeated using the new value. Provided that the computation is fast, the net effect is essentially to allow an arbitrary computation to behave as though it's atomic.

If you want to do a Compare-Exchange-style operation using Equals() equality, you should probably do something like:

SomeType newValue = desired new value;
SomeType compareValue = desired comparand;
SomeType oldValue;
do
{
  oldValue = someField;
  if (!oldValue.Equals(compareValue) return oldValue;
} while (CompareExchange(ref someField, newValue, oldValue) != oldValue);
return oldValue;

Note that if someField holds a reference to an object which would compare equal to compareValue, and during the comparison it is changed to hold a reference to a different object, that new value will be checked against compareValue. The process will be repeated until either an comparison reports that the value read from the field field was not equal to the comparand, or until the value in the field remains unchanged long enough for both the Equals() and CompareExchange methods to complete.

Drippy