C# Interlocked Exchange

Question

I have a bit of my game which looks like this:

public static float Time;

float someValue = 123;
Interlocked.Exchange(ref Time, someValue);

I want to change Time to be a Uint32; however, when I try to use UInt32 instead of float for the values, it protests that the type must be a reference type. Float is not a reference type, so I know it's technically possible to do this with non-reference types. Is there any practical way to make this work with UInt32?

Horsa

Answer 1

Although ugly, it is actually possible to perform an atomic Exchange or CompareExchange on an enum or other blittable value type of 64 bits or less using unsafe C# code:

enum MyEnum { A, B, C };

MyEnum m_e = MyEnum.B;

unsafe void example()
{
    MyEnum e = m_e;
    fixed (MyEnum* ps = &m_e)
        if (Interlocked.CompareExchange(ref *(int*)ps, (int)(e | MyEnum.C), (int)e) == (int)e)
        {
            /// change accepted, m_e == B | C
        }
        else
        {
            /// change rejected
        }
}

The counterintuitive part is that the ref expression on the dereferenced pointer does actually penetrate through the cast to the address of the enum. I think the compiler would have been within its rights to have generated an invisible temporary variable on the stack instead, in which case this wouldn't work. Use at your own risk.

[edit: for the specific type requested by the OP]

static unsafe uint CompareExchange(ref uint target, uint v, uint cmp)
{
    fixed (uint* p = &target)
        return (uint)Interlocked.CompareExchange(ref *(int*)p, (int)v, (int)cmp);
}

[edit: and 64-bit unsigned long]

static unsafe ulong CompareExchange(ref ulong target, ulong v, ulong cmp)
{
    fixed (ulong* p = &target)
        return (ulong)Interlocked.CompareExchange(ref *(long*)p, (long)v, (long)cmp);
}

(I also tried using the undocumented C# keyword __makeref to achieve this, but this doesn't work because you can't use ref on a dreferenced __refvalue. It's too bad, because the CLR maps the InterlockedExchange functions to a private internal function that operates on TypedReference [comment mooted by JIT interception, see below])

---

[edit: July 2018] You can now do this more efficiently using the System.Runtime.CompilerServices.​Unsafe library package. Your method can use Unsafe.As<TFrom,TTo>() to directly reinterpret the type referenced by the target managed reference, avoiding the dual expenses of both pinning and transitioning to unsafe mode:

static uint CompareExchange(ref uint target, uint value, uint expected) =>
    (uint)Interlocked.CompareExchange(
                            ref Unsafe.As<uint, int>(ref target),
                            (int)value,
                            (int)expected);

static ulong CompareExchange(ref ulong target, ulong value, ulong expected) =>
    (ulong)Interlocked.CompareExchange(
                            ref Unsafe.As<ulong, long>(ref target),
                            (long)value,
                            (long)expected);

Of course this works for Interlocked.Exchange as well. Here are those helpers for the 4- and 8-byte unsigned types.

static uint Exchange(ref uint target, uint value) =>
    (uint)Interlocked.Exchange(ref Unsafe.As<uint, int>(ref target), (int)value);

static ulong Exchange(ref ulong target, ulong value) =>
    (ulong)Interlocked.Exchange(ref Unsafe.As<ulong, long>(ref target), (long)value);

This works for enumeration types also--but only so long as their underlying primitive integer is exactly four or eight bytes. In other words, int (32-bit) or long (64-bit) sized. The limitation is that these are the only two bit-widths found among the Interlocked.CompareExchange overloads. By default, enum uses int when no underlying type is specified, so MyEnum (from above) works fine.

static MyEnum CompareExchange(ref MyEnum target, MyEnum value, MyEnum expected) =>
    (MyEnum)Interlocked.CompareExchange(
                            ref Unsafe.As<MyEnum, int>(ref target),
                            (int)value,
                            (int)expected);

static MyEnum Exchange(ref MyEnum target, MyEnum value) =>
    (MyEnum)Interlocked.Exchange(ref Unsafe.As<MyEnum, int>(ref target), (int)value);

I'm not sure whether the 4-byte minimum is a fundamental to .NET, but as far as I can tell it leaves no means of atomically swapping (values of) the smaller 8- or 16-bit primitive types (byte, sbyte, char, ushort, short) without risking collateral damage to adjacent byte(s). In the following example, BadEnum explicitly specifies a size that is too small to be atomically swapped without possibly affecting up to three neighboring bytes.

enum BadEnum : byte { };    // can't swap less than 4 bytes on .NET?

If you're not constrained by interop-dictated (or otherwise fixed) layouts, a workaround would be to ensure that the memory layout of such enums is always padded to the 4-byte minimum to allow for atomic swapping (as int). It seems likely, however, that doing so would defeat whatever purpose there might have been for specifying the smaller width in the first place.

---

[edit: April 2017] I recently learned that when .NET is running in 32-bit mode (or, i.e. in the WOW subsystem), the 64-bit Interlocked operations are not guaranteed to be atomic with respect to non-Interlocked, "external" views of the same memory locations. In 32-bit mode, the atomic guarantee only applies globablly across QWORD accesses which use the Interlocked (and perhaps Volatile.*, or Thread.Volatile*, TBD?) functions.

In other words, to obtain 64-bit atomic operations in 32-bit mode, all accesses to those QWORD locations, including reads, must occur through Interlocked/Volatile in order to preserve the guarantees, so you can't get cute assuming (e.g.) that direct (i.e., non-Interlocked/Volatile) reads are protected just because you always use Interlocked/Volatile functions for writing.

Finally, note that the Interlocked functions in the CLR are specially recognized by, and receive special treatment in, the .NET JIT compiler. See here and here This fact may help explain the counter-intuitiveness I mentioned earlier.

Hydrophobic

I'm actually going to give this the accepted answer because I could easilt write a CompareExchange for UInt32 this way, which was the original question. – Horsa

It's nice to know this works, but I think your "use at your own risk" warning should be emphasized very strongly. If the next version of the compiler generated a temp here, it would silently introduce a bug that could be very hard to track down. I'm not a big unit-tester, but this kind of trick basically demands one. Still, a good thing to know about. Up-voted. – Susi

I haven't tested it, but I suspect this is possible without unsafe using DynamicMethod & IL-generation. (Since it is possible for enums, as shown here.) It's still a "hack", but I don't think it would depend on the compiler implementation. – Emilia

I went ahead and tested it - it works so I posted it as an answer. – Emilia

@Susi I disagree on a minor point. Should someone decide to use this (and your admonition is well noted), then in my experience it seems the CompareExchange sequence points would comprise the low-level foundation of a necessarily non-localized lock-free system design. Because if there aren't multiple contention points, you wouldn't bother at all. Should this be the case, then if it stopped working one day, the failure would likely present as catastrophic and not too hard to localize. – Hydrophobic

Answer 2

There's an overload for Interlocked.Exchange specifically for float (and others for double, int, long, IntPtr and object). There isn't one for uint, so the compiler reckons the closest match is the generic Interlocked.Exchange<T> - but in that case T has to be a reference type. uint isn't a reference type, so that doesn't work either - hence the error message.

In other words:

• Your current code works because it calls Interlocked.Exchange(ref float, float).
• Changing it to uint fails because there's no applicable overload. The exact error message is caused by the compiler guessing that you mean Interlocked.Exchange<T>(ref T, T).

As for what to do, the options are any of:

• Potentially use int instead, as Marc suggests.
• If you need the extra range, think about using long.
• Use uint but don't try to write lock-free code

Although obviously Exchange works fine with some specific value types, Microsoft hasn't implemented it for all the primitive types. I can't imagine it would have been hard to do so (they're just bits, after all) but presumably they wanted to keep the overload count down.

Entozoon

Interlocked should provide overloads for every non-trivial blittable 64-bit (or smaller) value type in the BCL and there's no excuse for anything less. Ironically, unlike native C/C++ (where compiler-optimization fetish weakens memory access guarantees to the general detriment of lock-free design), the iron-clad memory model in .NET actually enables—or even encourages—wider use of lock-free code in non-trivial ways. Given this heightened importance of atomic operations, if my workaround weren't available, the oversight would be downright appalling. – Hydrophobic

Answer 3

[edit:] Mea culpa and apologies to @AnorZaken since my answer is similar to his. I honestly didn't see it before posting mine. I'll keep this for now in case my text and explanations are useful or have additional insights, but credit for prior work properly goes to Anor.

---

Although I have another solution on this page, some people might be interested in a totally different approach. Below, I give a DynamicMethod which implements Interlocked.CompareExchange for any 32- or 64-bit blittable type, which includes any custom Enum types, the primitive types that the built-in method forgot (uint, ulong), and even your own ValueType instances--so long as any of these are dword (4-bytes, i.e., int, System.Int32) or qword (8-bytes, long, System.Int64) sized. For example, the following Enum type won't work since it specifies a non-default size, byte:

enum ByteSizedEnum : byte { Foo }     // no: size is not 4 or 8 bytes

As with most DynamicMethod implementations of runtime-generated IL, the C# code isn't beautiful to behold, but for some people the elegant IL and sleek JITted native code make up for that. For example, in contrast to the other method I posted, this one doesn't use unsafe C# code.

To allow automatic inference of the generic type at the call site, I wrap the helper in a static class:

public static class IL<T> where T : struct
{
    // generic 'U' enables alternate casting for 'Interlocked' methods below
    public delegate U _cmp_xchg<U>(ref U loc, U _new, U _old);

    // we're mostly interested in the 'T' cast of it
    public static readonly _cmp_xchg<T> CmpXchg;

    static IL()
    {
        // size to be atomically swapped; must be 4 or 8.
        int c = Marshal.SizeOf(typeof(T).IsEnum ?
                                Enum.GetUnderlyingType(typeof(T)) :
                                typeof(T));

        if (c != 4 && c != 8)
            throw new InvalidOperationException("Must be 32 or 64 bits");

        var dm = new DynamicMethod(
            "__IL_CmpXchg<" + typeof(T).FullName + ">",
            typeof(T),
            new[] { typeof(T).MakeByRefType(), typeof(T), typeof(T) },
            MethodInfo.GetCurrentMethod().Module,
            false);

        var il = dm.GetILGenerator();
        il.Emit(OpCodes.Ldarg_0);    // ref T loc
        il.Emit(OpCodes.Ldarg_1);    // T _new
        il.Emit(OpCodes.Ldarg_2);    // T _old
        il.Emit(OpCodes.Call, c == 4 ?
                ((_cmp_xchg<int>)Interlocked.CompareExchange).Method :
                ((_cmp_xchg<long>)Interlocked.CompareExchange).Method);
        il.Emit(OpCodes.Ret);

        CmpXchg = (_cmp_xchg<T>)dm.CreateDelegate(typeof(_cmp_xchg<T>));
    }
};

Technically, the above is all you need. You can now call CmpXchgIL<T>.CmpXchg(...) on any appropriate value type (as discussed in the intro above), and it will behave exactly like the built-in Interlocked.CompareExchange(...) in System.Threading. For example, lets say you have a struct containing two integers:

struct XY
{
    public XY(int x, int y) => (this.x, this.y) = (x, y);   // C#7 tuple syntax
    int x, y;
    static bool eq(XY a, XY b) => a.x == b.x && a.y == b.y;
    public static bool operator ==(XY a, XY b) => eq(a, b);
    public static bool operator !=(XY a, XY b) => !eq(a, b);
}

You can now atomically publish the 64-bit struct just as you would expect with any CmpXchg operation. This atomically publishes the two integers so that it is impossible for another thread to see a 'torn' or inconsistent pairing. Needless to say, easily doing so with a logical pairing is hugely useful in concurrent programming, even more so if you devise an elaborate struct that packs many fields into the available 64 (or 32) bits. Here's an example of the call-site for doing this:

var xy = new XY(3, 4);      // initial value

//...

var _new = new XY(7, 8);    // value to set
var _exp = new XY(3, 4);    // expected value

if (IL<XY>.CmpXchg(ref xy, _new, _exp) != _exp)  // atomically swap the 64-bit ValueType
    throw new Exception("change not accepted");

Above, I mentioned that you can tidy up the call site by enabling type inference so that you don't have to specify the generic parameter. To do this, just define a static generic method in one of your non- generic global classes:

public static class my_globals
{
    [DebuggerStepThrough, MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static T CmpXchg<T>(ref T loc, T _new, T _old) where T : struct => 
                                                 _IL<T>.CmpXchg(ref loc, _new, _old);
}

I'll show the simplified call site with a different example, this time using an Enum:

using static my_globals;

public enum TestEnum { A, B, C };

static void CompareExchangeEnum()
{
    var e = TestEnum.A;

    if (CmpXchg(ref e, TestEnum.B, TestEnum.A) != TestEnum.A)
        throw new Exception("change not accepted");
}

As for the original question, ulong and uint work trivially as well:

ulong ul = 888UL;

if (CmpXchg(ref ul, 999UL, 888UL) != 888UL)
    throw new Exception("change not accepted");

Hydrophobic

Answer 4

Perhaps use int instead of uint; there are overloads for int. Do you need the extra bit of range? If so, cast / convert as late as possible.

Lippizaner

Well I never use values less than zero (since it's storing time since the game started), however (2^32)/2 is still a very long game (it's storing milliseconds. I guess for now I'll just use ints and leave it at that. – Horsa

Answer 5

It is still a hack but it is possible to do this with IL-generation instead of using unsafe code. The benefit is that instead of relying on a compiler implementation detail it relies on the fact that the signed and unsigned types are of the same bit-length, which is part of the spec.

Here is how:

using System;
using System.Reflection;
using System.Reflection.Emit;
using ST = System.Threading;

/// <summary>
/// Provides interlocked methods for uint and ulong via IL-generation.
/// </summary>
public static class InterlockedUs
{
    /// <summary>
    /// Compares two 32-bit unsigned integers for equality and, if they are equal,
    /// replaces one of the values.
    /// </summary>
    /// <param name="location">
    /// The value to exchange, i.e. the value that is compared with <paramref name="comparand"/> and
    /// possibly replaced with <paramref name="value"/>.</param>
    /// <param name="value">
    /// The value that replaces the <paramref name="location"/> value if the comparison
    /// results in equality.</param>
    /// <param name="comparand">
    /// A value to compare against the value at <paramref name="location"/>.</param>
    /// <returns>The original value in <paramref name="location"/>.</returns>
    public static uint CompareExchange(ref uint location, uint value, uint comparand)
    {
        return ceDelegate32(ref location, value, comparand);
    }

    /// <summary>
    /// Compares two 64-bit unsigned integers for equality and, if they are equal,
    /// replaces one of the values.
    /// </summary>
    /// <param name="location">
    /// The value to exchange, i.e. the value that is compared with <paramref name="comparand"/> and
    /// possibly replaced with <paramref name="value"/>.</param>
    /// <param name="value">
    /// The value that replaces the <paramref name="location"/> value if the comparison
    /// results in equality.</param>
    /// <param name="comparand">
    /// A value to compare against the value at <paramref name="location"/>.</param>
    /// <returns>The original value in <paramref name="location"/>.</returns>
    public static ulong CompareExchange(ref ulong location, ulong value, ulong comparand)
    {
        return ceDelegate64(ref location, value, comparand);
    }


    #region ---  private  ---
    /// <summary>
    /// The CompareExchange signature for uint.
    /// </summary>
    private delegate uint Delegate32(ref uint location, uint value, uint comparand);

    /// <summary>
    /// The CompareExchange signature for ulong.
    /// </summary>
    private delegate ulong Delegate64(ref ulong location, ulong value, ulong comparand);

    /// <summary>
    /// IL-generated CompareExchange method for uint.
    /// </summary>
    private static readonly Delegate32 ceDelegate32 = GenerateCEMethod32();

    /// <summary>
    /// IL-generated CompareExchange method for ulong.
    /// </summary>
    private static readonly Delegate64 ceDelegate64 = GenerateCEMethod64();

    private static Delegate32 GenerateCEMethod32()
    {
        const string name = "CompareExchange";
        Type signedType = typeof(int), unsignedType = typeof(uint);
        var dm = new DynamicMethod(name, unsignedType, new[] { unsignedType.MakeByRefType(), unsignedType, unsignedType });
        var ilGen = dm.GetILGenerator();
        ilGen.Emit(OpCodes.Ldarg_0);
        ilGen.Emit(OpCodes.Ldarg_1);
        ilGen.Emit(OpCodes.Ldarg_2);
        ilGen.Emit(
            OpCodes.Call,
            typeof(ST.Interlocked).GetMethod(name, BindingFlags.Public | BindingFlags.Static,
                null, new[] { signedType.MakeByRefType(), signedType, signedType }, null));
        ilGen.Emit(OpCodes.Ret);
        return (Delegate32)dm.CreateDelegate(typeof(Delegate32));
    }

    private static Delegate64 GenerateCEMethod64()
    {
        const string name = "CompareExchange";
        Type signedType = typeof(long), unsignedType = typeof(ulong);
        var dm = new DynamicMethod(name, unsignedType, new[] { unsignedType.MakeByRefType(), unsignedType, unsignedType });
        var ilGen = dm.GetILGenerator();
        ilGen.Emit(OpCodes.Ldarg_0);
        ilGen.Emit(OpCodes.Ldarg_1);
        ilGen.Emit(OpCodes.Ldarg_2);
        ilGen.Emit(
            OpCodes.Call,
            typeof(ST.Interlocked).GetMethod(name, BindingFlags.Public | BindingFlags.Static,
                null, new[] { signedType.MakeByRefType(), signedType, signedType }, null));
        ilGen.Emit(OpCodes.Ret);
        return (Delegate64)dm.CreateDelegate(typeof(Delegate64));
    }
    #endregion
}

Credit to "hvd" for the IL-generation idea and similar code for a CompareExchange method for Enums, which can be found here.

There will be some overhead for generating the method on the first call, but the generated method is stored in delegate form so any subsequent calls should be very performant.

And to quote from the above link:

The generated IL is verifiable, at least according to PEVerify, as can be checked by making this use AssemblyBuilder and saving the result to a file.

Emilia

Answer 6

You cannot pass a casted expression by reference, you should use a temporary variable:

public static float Time;
float value2 = (float)SomeValue;
Interlocked.Exchange(ref Time, ref value2);
SomeValue = value2;

Upshaw

Oh, the cast was just to demonstrate what type that value is, I didn't realise you can't use casts there :O – Horsa

the second variable doesn't need to be a reference, look on the MSDN here: msdn.microsoft.com/en-us/library/5z8f2s39.aspx – Horsa

Making a copy of the variable defeats the purpose of Interlocked.Exchange. – Hydrophobic