Proposal: Atomic<T> (corefx)

[benaadams]

Atomic

Background

x64 has been able to do 128bit/16 byte Interlocked CompareExchanges for a while and its a cpu requirement to be able install Window 8.1 x64 and Windows 10 x64. Its also available on MacOS/OSX and Linux. Its availability would allow for more interesting lock-less algorithms.

Was trying to think if there was an easy fallback for https://github.com/dotnet/corefx/issues/10478 but since its struct-based there is nothing to lock.

So additionally it would be good to have a type Atomic which mirrors the C++ 11 atomic type, adds some .NET magic and can fallback to locks when the data width is not supported on the platform.

Proposed Api

Interface, struct, class, extenstions (and some reference manipulation types)

namespace System.Threading.Atomics
{
    public interface IAtomic<T>  where T : IEquatable<T>
    {
        T Read();
        T Read(MemoryOrder order);
        void Write(T value);
        void Write(T value, MemoryOrder order);

        T Exchange(T value);
        T Exchange(T value, MemoryOrder order);

        bool CompareExchangeWeak(T value, T comperand);
        bool CompareExchangeWeak(T value, T comperand, MemoryOrder order);

        bool CompareExchangeStrong(T value, T comperand);
        bool CompareExchangeStrong(T value, T comperand, MemoryOrder order);

        // MemoryOrder variants skipped for brevity

        // Unsafe transformations, bypass the atomicity
        T UnsafeTransform(AtomicTransform<T> transformation);
        T UnsafeTransform(AtomicTransformParam<T> transformation, T val);

        // Atomic transformations, Func should be pure and repeatable in case of retry

        // Pure transform
        T Transform(Func<T, T> transformation);
        T Transform<TState>(Func<T, TState, T> transformation, TState state);

        // Conditional transforms e.g. Increment but only while < N
        T Transform(Func<T, T> transformation, Func<T, bool> condition);
        T Transform<TState>(Func<T, T> transformation, Func<T, TState, bool> condition, TState state);

        // Same data transform, apply if value is what is expected
        T Transform(Func<T, T> transformation, T comperand);
        T Transform<TState>(Func<T, TState, T> transformation, TState state, T comperand);
    }

    public delegate T AtomicTransform<T>(ref T input);
    public delegate T AtomicTransformParam<T>(ref T input, T val);

    public enum MemoryOrder
    {
        Relaxed,
        Consume,
        Acquire,
        Release,
        AcquireRelease,
        SequentiallyConsistent
    }
}

Atomic struct

[Disallow(Stack,Boxing)]
public struct ValueAtomic<T> : IAtomic<T> where T : IEquatable<T>
{
    private T _data;
    // allocated if not supported lock-free natively
    private object _lock;

    [JitIntrinsic]
    public static bool IsLockFree { get; }

    public ValueAtomic(T value)
    {
        _data = value;
        _lock = IsLockFree ? null : new object();
    }

    public T Read();
    public T Read(MemoryOrder order);
    public void Write(T value);
    public void Write(T value, MemoryOrder order);
    public T Exchange(T value);
    public T Exchange(T value, MemoryOrder order);
    public bool CompareExchangeWeak(T value, T comperand);
    public bool CompareExchangeWeak(T value, T comperand, MemoryOrder order);
    public bool CompareExchangeStrong(T value, T comperand);
    public bool CompareExchangeStrong(T value, T comperand, MemoryOrder order);
    public unsafe T UnsafeTransform(AtomicTransform<T> transformation)
        => transformation(ref _data);
    public unsafe T UnsafeTransform(AtomicTransformParam<T> transformation, T val)
        => transformation(ref _data, val);
    public T Transform(Func<T, T> transformation);
    public T Transform<TState>(Func<T, TState, T> transformation, TState state);
    public T Transform(Func<T, T> transformation, Func<T, bool> condition);
    public T Transform<TState>(Func<T, T> transformation, Func<T, TState, bool> condition, TState state)
    {
        //T current = Read();
        //while (condition(current, state))
        //{
        //    T next = transformation(current);
        //    T prev = Interlocked.CompareExchange(ref _data, next, current);
        //    if (prev.Equals(current))
        //    {
        //        return next;
        //    }
        //    current = prev;
        //}
    }
    public T Transform(Func<T, T> transformation, T comperand);
    public T Transform<TState>(Func<T, TState, T> transformation, TState state, T comperand);

    public static implicit operator T(ValueAtomic<T> atom) => atom.Read();
}

Atomic class (struct wrapper)

public class Atomic<T> : IAtomic<T> where T : IEquatable<T>
{
    private ValueAtomic<T> _atom;
    public static bool IsLockFree => ValueAtomic<T>.IsLockFree;

    Atomic(T value)
    {
        _atom = new ValueAtomic<T>(value);
    }

    public T Read()
        => _atom.Read();
    public T Read(MemoryOrder order)
        => _atom.Read(order);
    public void Write(T value)
        => _atom.Write(value);
    public void Write(T value, MemoryOrder order)
        => _atom.Write(value, order);
    public T Exchange(T value)
        => _atom.Exchange(value);
    public T Exchange(T value, MemoryOrder order)
        => _atom.Exchange(value, order);
    public bool CompareExchangeWeak(T value, T comperand)
        => _atom.CompareExchangeWeak(value, comperand);
    public bool CompareExchangeWeak(T value, T comperand, MemoryOrder order)
        => _atom.CompareExchangeWeak(value, comperand, order);
    public bool CompareExchangeStrong(T value, T comperand)
        => _atom.CompareExchangeStrong(value, comperand);
    public bool CompareExchangeStrong(T value, T comperand, MemoryOrder order)
        => _atom.CompareExchangeStrong(value, comperand, order);
    public unsafe T UnsafeTransform(AtomicTransform<T> transformation)
        => _atom.UnsafeTransform(transformation);
    public unsafe T UnsafeTransform(AtomicTransformParam<T> transformation, T val)
        => _atom.UnsafeTransform(transformation, val);
    public T Transform(Func<T, T> transformation)
        => _atom.Transform(transformation);
    public T Transform<TState>(Func<T, TState, T> transformation, TState state) 
    => _atom.Transform(transformation, state);
    public T Transform(Func<T, T> transformation, Func<T, bool> condition)
        => _atom.Transform(transformation, condition);
    public T Transform<TState>(Func<T, T> transformation, Func<T, TState, bool> condition, TState state)
        => _atom.Transform(transformation, condition, state);
    public T Transform(Func<T, T> transformation, T comperand)
        => _atom.Transform(transformation, comperand);
    public T Transform<TState>(Func<T, TState, T> transformation, TState state, T comperand) 
        => _atom.Transform(transformation, state, comperand);

    public static implicit operator T(Atomic<T> atom) => atom.Read();
}

Numeric Extensions

public static class AtomicNumericExtensions
{
    // For byte, short, ushort, uint, int, long, ulong, single, double

    public static int Add(this Atomic<int> atom, int value);
    public static int Subtract(this Atomic<int> atom, int value);
    public static int Multiply(this Atomic<int> atom, int value);
    public static int Divide(this Atomic<int> atom, int value);

    // For byte, short, ushort, uint, int, long, ulong

    public static int Increment(this Atomic<int> atom);
    public static int Increment(this Atomic<int> atom, int max);

    public static int Decrement(this Atomic<int> atom);
    public static int Decrement(this Atomic<int> atom, int min);

    public static int And(this Atomic<int> atom, int value);
    public static int Or(this Atomic<int> atom, int value);
    public static int Xor(this Atomic<int> atom, int value);
    public static int Not(this Atomic<int> atom);
}

Bool Extensions

public static class AtomicBoolExtensions
{
    public static bool TestAndSet(this Atomic<bool> atom);
    public static bool Clear(this Atomic<bool> atom);
}

Atomic Flagged References

public struct FlaggedReference<TRef>
    where TRef : class
{
    TRef Reference { get; set; }
    bool Flag { get; set; }
}

public static class AtomicFlaggedReferenceExtensions
{
    public static bool TestAndSet<TRef>(this Atomic<FlaggedReference<TRef>> atom);
    public static bool TestAndSet<TRef>(
                        this Atomic<FlaggedReference<TRef>> atom,
                        TRef expectedReference);
    public static bool Clear<TRef>(this Atomic<FlaggedReference<TRef>> atom);
    public static bool Clear<TRef>(
                        this Atomic<FlaggedReference<TRef>> atom,
                        TRef expectedReference);
}

Atomic Versioned References

public struct VersionedReference<TRef>
    : IEquatable<VersionedReference<TRef>>
    where TRef : class
{
    TRef Reference { get; set; }
    long Version { get; set; }

    public bool Equals(VersionedReference<TRef> other)
        => ReferenceEquals(Reference, other.Reference) 
            && Version == other.Version;

    public static implicit operator TRef(VersionedReference<TRef> atom) => atom.Reference;
}

public static class AtomicVersionedReferenceExtensions
{
    public static VersionedReference<TRef> Increment<TRef>(
                    this Atomic<VersionedReference<TRef>> atom)
                    where TRef : class;
    public static VersionedReference<TRef> Increment<TRef>(
                    this Atomic<VersionedReference<TRef>> atom,
                    TRef expectedReference)
                    where TRef : class;
    public static VersionedReference<TRef> UpdateIncrement<TRef>(
                    this Atomic<VersionedReference<TRef>> atom,
                    VersionedReference<TRef> newRefExpectedVersion)
                    where TRef : class;
}

Atomic Tagged References

public struct TaggedReference<TRef, TTag>
    where TRef : class 
    where TTag : struct
{
    TRef Reference { get; set; }
    TTag Tag { get; set; }
}

public static class AtomicTaggedReferenceExtensions
{
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TaggedReference<TRef, TTag> newTaggedReference,
                    TRef expectedReference);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TRef newReference,
                    TRef expectedReference);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TTag newTag,
                    TRef expectedReference);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TaggedReference<TRef, TTag> newTaggedReference,
                    TTag expectedTag);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TRef newReference,
                    TTag expectedTag);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TTag newTag,
                    TTag expectedTag);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TRef newReference,
                    TaggedReference<TRef, TTag> expectedTaggedReference);
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TTag newTag,
                    TaggedReference<TRef, TTag> expectedTaggedReference);
    // essentially CompareExchange
    public static TaggedReference<TRef, TTag> Update<TRef, TTag>(
                    this TaggedReference<TRef, TTag> atom,
                    TaggedReference<TRef, TTag> newTaggedReference,
                    TaggedReference<TRef, TTag> expectedTaggedReference);
}

Atomic Double Reference

public struct DoubleReference<TRef> : IEquatable<DoubleReference<TRef>>
    where TRef : class
{
    TRef ReferenceLeft { get; set; }
    TRef ReferenceRight { get; set; }

    public bool Equals(DoubleReference<TRef> other)
        => ReferenceEquals(ReferenceLeft, other.ReferenceLeft) &&
            ReferenceEquals(ReferenceRight, other.ReferenceRight);
}

public static class DoubleReferenceExtensions
{
    public static DoubleReference<TRef> ExchangeLeft<TRef>(
                    this Atomic<DoubleReference<TRef>> atom,
                    TRef expectedRight) where TRef : class;
    public static DoubleReference<TRef> ExchangeRight<TRef>(
                    this Atomic<DoubleReference<TRef>> atom,
                    TRef expectedLeft) where TRef : class;
}

Transforms

The transforms give the flexibility to compose more complex atomic data structures; for example the int Add, Increment and Increment to limit can be implemented as

public static int Add<TAtomic>(this TAtomic atom, int value) 
    where TAtomic : IAtomic<int>
{
    return atom.UnsafeTransform(
        (ref int current, int inc) 
            => Interlocked.Add(ref current, inc), value);
}

public static int Increment<TAtomic>(this TAtomic atom) 
    where TAtomic : IAtomic<int>
{
    return atom.UnsafeTransform((ref int v) => Interlocked.Increment(ref v));
}

public static int Increment<TAtomic>(this TAtomic atom, int value, int max) 
    where TAtomic : IAtomic<int>
{
    return atom.Transform((current) => current + 1, (c, m) => c <= m, max);
}

Or an entirely new type that hadn't previously supported atomic updates, with new operations

public static Decimal Multiply<TAtomic>(this TAtomic atom, Decimal value)
   where TAtomic : IAtomic<Decimal>
{
    return atom.Transform((current, m) => current * m, value);
}

When the struct was 16 bytes _data would need to be 16 byte aligned to allow lock free use with LOCK CMPXCHG16b where available. Might be easier to enforce alignment than with https://github.com/dotnet/corefx/issues/10478?

VersionedReference and FlaggedReference should be 16 byte aligned in Atomic (don't need to be outside), as should TaggedReference when the struct is <= 16 bytes.

[davidfowl]

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/package-summary.html

[benaadams]

Maybe a CompareExchange variant that takes a Func<T, T>?

bool Transform<TVal>(Func<TVal, TVal> transformation, T comperand) where TVal : struct, T;

Added

[joshfree]

cc @sergiy-k

[clrjunkie]

I think in this case it’s ok skip the interface name suffix convention so things don’t read weird.

Consider changing ValueAtomic to AtomicValue.

Furthermore, the api really abstracts a memory location consider renaming to AtomicVariable
(I think atomic value generally means something that can’t be further divided)

Consider adding 'Extensions' suffix to Extension Method classes.

[benaadams]

I think in this case it’s ok skip the interface name suffix convention so things don’t read weird. Consider changing ValueAtomic to AtomicValue.

There are 3 types, IAtomic, Atomic (class) and ValueAtomic (struct). The ValueAtomic follows the naming of ValueTuple and ValueTask for the struct based versions of Tuple and Task.

IAtomic is so generic constraints can be used for the two types in the extension methods.

Ideally I'd like ValueTask to be a heap+ref return only (array of ValueTask) struct. It would have a similar problem to SpinLock in stack space (e.g. no purpose and error though copying).

the api really abstracts a memory location

It can represent any type at any size; just will fallback to a lock when it can't be covered by a CAS or equivalent (e.g. TSX/LLSC).

Consider adding 'Extensions' suffix to Extension Method classes.

Done

[GSPP]

An alternative design would be to add the following:

1. Add all these methods in the form of static methods.
2. Support specifying memory alignment for structs.

That's more flexible than demanding that a certain type must be used.

[benaadams]

Add all these methods in the form of static methods ... That's more flexible than demanding that a certain type must be used.

Doesn't allow fallbacks; if I had a 16 byte struct it may support CAS on x64, but not x86, a 64 byte struct may support an atomic update with TSX on Intel Skylake but not on earlier cpus, AMD or ARM.

As a user I just want an atomically updating data structure without worrying how its done; whether CAS, LLSC, Transactional memory etc.

As a power user I may want to know if IsLockFree and use a different strategy if not.

With the Atomic type set; I could define a 256 byte struct and have it happily be atomically updated by just enclosing it in the type.

Atomic<struct256byte> LargeStruct = new Atomic<struct256byte>();
var val = LargeStruct.Read();
val.x = 15;
val.name = "www";
LargeStruct.Write(val);

An if that became an lock-free operation at some point on a platform the framework could be updated to take advantage of it and no user code would need to change.

[clrjunkie]

The ValueAtomic follows the naming of ValueTuple and ValueTask for the struct based versions of Tuple and Task.

Why? How are these related to this api?

It can represent any type at any size; just will fallback to a lock when it can't be covered by a CAS or equivalent (e.g. TSX/LLSC).

So it abstracts a location in memory.. seems natural to call it as such (e.g AtomicVariable)

p.s

Not planning to over argue about it... food for your thought

[benaadams]

The ValueAtomic follows the naming of ValueTuple and ValueTask for the struct based versions of Tuple and Task.

Why? How are these related to this api?

As there are two types:

Atomic<decimal> objectAtomicDecimal = new Atomic<decimal>();
ValueAtomic<decimal> valueTypeAtomicDecimal = new ValueAtomic<decimal>();

The class type (heap) to be passed as parameter; the valuetype to be embedded in class (heap) or used in arrays (heap).

[clrjunkie]

Aha... didn't pay quite attention to the Atomic class (wrapper)

[clrjunkie]

@benaadams

BTW.. I don't recall encountering code where an atomic variable was passed around as an argument for anything other then passing it to an interlocked method... even while reading through java code I only recall noticing their atomic abstraction used at the field level. Have you encountered any usage that justifies the 'class version'? Might worth posting an example here to be included in the api doc's as "sample usage". Genuinely interested.

[GSPP]

There's no need for a copy of the struct to put it on the heap. The framework has Box<T> for putting anything on the heap.