Interlocked.CompareExchange using GreaterThan or LessThan instead of equality

Question

The System.Threading.Interlocked object allows for Addition (subtraction) and comparison as an atomic operation. It seems that a CompareExchange that just doesn't do equality but also GreaterThan/LessThan as an atomic comparison would be quite valuable.

Would a hypothetical Interlocked.GreaterThan a feature of the IL or is it a CPU-level feature? Both?

Lacking any other option, is it possible to create such a feature in C++ or direct IL code and expose that functionality to C#?

Answer 1

You can build other atomic operations out of InterlockedCompareExchange.

public static bool InterlockedExchangeIfGreaterThan(ref int location, int comparison, int newValue)
{
    int initialValue;
    do
    {
        initialValue = location;
        if (initialValue >= comparison) return false;
    }
    while (System.Threading.Interlocked.CompareExchange(ref location, newValue, initialValue) != initialValue);
    return true;
}

Answer 2

With these helper methods you can not only exchange value but also detect was it replaced or not.

Usage looks like this:

int currentMin = 10; // can be changed from other thread at any moment

int potentialNewMin = 8;
if (InterlockedExtension.AssignIfNewValueSmaller(ref currentMin, potentialNewMin))
{
    Console.WriteLine("New minimum: " + potentialNewMin);
}

And here are methods:

public static class InterlockedExtension
{
    public static bool AssignIfNewValueSmaller(ref int target, int newValue)
    {
        int snapshot;
        bool stillLess;
        do
        {
            snapshot = target;
            stillLess = newValue < snapshot;
        } while (stillLess && Interlocked.CompareExchange(ref target, newValue, snapshot) != snapshot);

        return stillLess;
    }

    public static bool AssignIfNewValueBigger(ref int target, int newValue)
    {
        int snapshot;
        bool stillMore;
        do
        {
            snapshot = target;
            stillMore = newValue > snapshot;
        } while (stillMore && Interlocked.CompareExchange(ref target, newValue, snapshot) != snapshot);

        return stillMore;
    }
}

Answer 3

This isn't actually true, but it is useful to think of concurrency as coming in 2 forms:

1. Lock free concurrency
2. Lock based concurrency

It's not true because software lock based concurrency ends up being implemented using lock free atomic instructions somewhere on the stack (often in the Kernel). Lock free atomic instructions, however, all ultimately end up acquiring a hardware lock on the memory bus. So, in reality, lock free concurrency and lock based concurrency are the same.

But conceptually, at the level of a user application, they are 2 distinct ways of doing things.

Lock based concurrency is based on the idea of "locking" access to a critical section of code. When one thread has "locked" a critical section, no other thread may have code running inside that same critical section. This is usually done by the use of "mutexes", which interface with the os scheduler and cause threads to become un-runnable while waiting to enter a locked critical section. The other approach is to use "spin locks" which cause a thread to spin in a loop, doing nothing useful, until the critical section becomes available.

Lock free concurrency is based on the idea of using atomic instructions (specially supported by the CPU), that are guaranteed by hardware to run atomically. Interlocked.Increment is a good example of lock free concurrency. It just calls special CPU instructions that do an atomic increment.

Lock free concurrency is hard. It gets particularly hard as the length and complexity of critical sections increase. Any step in a critical section can be simultaneously executed by any number of threads at once, and they can move at wildly different speeds. You have to make sure that despite that, the results of a system as a whole remain correct. For something like an increment, it can be simple (the cs is just one instruction). For more complex critical sections, things can get very complex very quickly.

Lock based concurrency is also hard, but not quite as hard as lock free concurrency. It allows you to create arbitrarily complex regions of code and know that only 1 thread is executing it at any time.

Lock free concurrency has one big advantage, however: speed. When used correctly it can be orders of magnitude faster than lock based concurrency. Spin loops are bad for long running critical sections because they waste CPU resources doing nothing. Mutexes can be bad for small critical sections because they introduce a lot of overhead. They involve a mode switch at a minimum, and multiple context switches in the worst case.

Consider implementing the Managed heap. Calling into the OS everytime "new" is called would be horrible. It would destroy the performance of your app. However, using lock free concurrency it's possible to implement gen 0 memory allocations using an interlocked increment (I don't know for sure if that's what the CLR does, but I'd be surprised if it wasn't. That can be a HUGE savings.

There are other uses, such as in lock free data structures, like persistent stacks and avl trees. They usually use "cas" (compare and swap).

The reason, however, that locked based concurrency and lock free concurrency are really equivalent is because of the implementation details of each.

Spin locks usually use atomic instructions (typically cas) in their loop condition. Mutexes need to use either spin locks or atomic updates of internal kernel structures in their implementation.

The atomic instructions are in turn implemented using hardware locks.

In any case, they both have their sets of trade offs, usually centering on perf vs complexity. Mutexes can be both faster and slower than lock free code. Lock free code can be both more and less complex than a mutex. The appropriate mechanism to use depends on specific circumstances.

Now, to answer your question:

A method that did an interlocked compare exchange if less than would imply to callers that it is not using locks. You can't implement it with a single instruction the same way increment or compare exchange can be done. You could simulate it doing a subtraction (to compute less than), with an interlocked compare exchange in a loop. You can also do it with a mutex (but that would imply a lock and so using "interlocked" in the name would be misleading). Is it appropriate to build the "simulated interlocked via cas" version? That depends. If the code is called very frequently, and has very little thread contention then the answer is yes. If not, you can turn a O(1) operation with moderately high constant factors into an infinite (or very long) loop, in which case it would be better to use a mutex.

Most of the time it's not worth it.

Answer 4

What do you think about this implementation:

// this is a Interlocked.ExchangeIfGreaterThan implementation
private static void ExchangeIfGreaterThan(ref long location, long value)
{
    // read
    long current = Interlocked.Read(ref location);
    // compare
    while (current < value)
    {
        // set
        var previous = Interlocked.CompareExchange(ref location, value, current);
        // if another thread has set a greater value, we can break
        // or if previous value is current value, then no other thread has it changed in between
        if (previous == current || previous >= value) // note: most commmon case first
            break;
        // for all other cases, we need another run (read value, compare, set)
        current = Interlocked.Read(ref location);
    }
}

Answer 5

Update to the later post I made here: we found a better way to make the greater comparison by using additional lock object. We wrote many unit tests in order to validate that a lock and Interlocked can be used together, but only for some cases.

How the code works: Interlocked uses memory barriers that a read or write is atomic. The sync-lock is needed to make the greater-than comparison an atomic operation. So the rule now is that inside this class no other operation writes the value without this sync lock.

What we get with this class is an interlocked value which can be read very fast, but write takes a little bit more. Read is about 2-4 times faster in our application.

Here the code as view:

See here: http://files.thekieners.com/blogcontent/2012/ExchangeIfGreaterThan2.png

Here as code to copy&paste:

public sealed class InterlockedValue
{
    private long _myValue;
    private readonly object _syncObj = new object();

    public long ReadValue()
    {
        // reading of value (99.9% case in app) will not use lock-object, 
        // since this is too much overhead in our highly multithreaded app.
        return Interlocked.Read(ref _myValue);
    }

    public bool SetValueIfGreaterThan(long value)
    {
        // sync Exchange access to _myValue, since a secure greater-than comparisons is needed
        lock (_syncObj)
        {
            // greather than condition
            if (value > Interlocked.Read(ref  _myValue))
            {
                // now we can set value savely to _myValue.
                Interlocked.Exchange(ref _myValue, value);
                return true;
            }
            return false;
        }
    }
}

Answer 6

All interlocked operations have direct support in the hardware.

Interlocked operations and atomic data type are different things.. Atomic type is a library level feature. On some platforms and for some data types atomics are implemented using interlocked instructions. In this case they are very effective.

In other cases when platform does not have interlocked operations at all or they are not available for some particular data type, library implements these operations using appropriate synchronization (crit_sect, mutex, etc).

I am not sure if Interlocked.GreaterThan is really needed. Otherwise it might be already implemented. If your know good example where it can be useful, I am sure that everybody here will be happy to hear this.

Answer 7

Greater/Less than and equal to are already atomic operations. That doesn't address the safe concurrent behavior of your application tho.

There is no point in making them part of the Interlocked family, so the question is: what are you actually trying to achieve?