Add DCAS overload of Interlocked.CompareExchange

[scalablecory]

A CAS that operates atomically on two pointers at once is useful for writing lock-free algorithms.

This would be an intrinsic for CMPXCHG8B, CMPXCHG16B, CASPAL instructions

Something like:

struct AtomicPair<TFirst, TSecond> where TFirst:class, TSecond:class
{
    public TFirst First;
    public TSecond Second;
}

struct AtomicPair<T> where T:class
{
    public T First;
    public nint Second;
}

struct AtomicPair
{
    public nint First;
    public nint Second;
}

class Interlocked
{
    // upon return, comparand is updated to the value that was in location1.
    public static bool CompareExchange(ref AtomicPair location1, AtomicPair value, ref AtomicPair comparand);
    public static bool CompareExchange<T>(ref AtomicPair<T> location1, AtomicPair<T> value, ref AtomicPair<T> comparand);
    public static bool CompareExchange<TFirst, TSecond>(ref AtomicPair<TFirst, TSecond> location1, AtomicPair<TFirst, TSecond> value, ref AtomicPair<TFirst, TSecond> comparand);
}

[stephentoub]

Our ConcurrentStack<T> is unable to reuse its nodes today due to typical ABA issues. That would be a good test bed to validate this API, with CS<T> maintaining a free list and using tagged pointers/references.

[scalablecory]

Our ConcurrentStack<T> is unable to reuse its nodes today due to typical ABA issues. That would be a good test bed to validate this API, with CS<T> maintaining a free list and using tagged pointers/references.

Unfortunately I don't know that ConcurrentStack could be updated to do this (at least, not without extra overhead) as GetEnumerator and Count depend on nodes not being recycled.

[stephentoub]

at least, not without extra overhead

We have a similar issue in ConcurrentQueue (whether to clear a dequeued element and allow its slot to be reused), and the extra meaningful overhead there is incurred only as part of the operations doing the iterating, e.g. GetEnumerator and Count, by setting a flag while such an operation is in progress and only performing the problematic operation if one isn't. They should be rare compared to push and pop.

A concurrent stack is the poster child for a primitive like this. It'd be a shame if ours couldn't use it.

[sunkin351]

Can we overload Interlocked.Exchange() in a similar fashion?