I have a very simple operation that needs to be done atomically:
if (a > b)
b = a
where a and b are ints
EDIT: and a is local.
Is there a fast way to do this in C#? I'd like to avoid locking manually if possible. I've looked at Interlocked.CompareExchange, but as I understand it, this only tests for equality.
Thanks!
The canonical way is to use interlocked compare-exchange in a loop:
int oldvalue, newvalue ;
do {
oldvalue = b ; // you'll want to force this to be a volatile read somehow
if( a > oldvalue )
newvalue = a ;
else
break ;
} while( interlocked replace oldvalue with newvalue in b does NOT succeed );
(Pseudocode because I don't bother to look up the correct way to do an interlocked exchange in C#).
As you see, unless you have overriding efficiency concerns, using plain old mutexes is far simpler and more readable.
Edit: This assumes that a is a local variable or at least not subject to asynchronous writes. It both of a and b can be modified behind your back, then there is no lock-free way of doing this update atomically. (Thanks to silev for pointing this out).
lock keyword or explicit mutexes. If that's the boundary condition (and I'm not really endorsing it, as should be clear), then using a loop is inevitable, at least with the x86 locking model. –
Sophia b and yet once to release the lock. All other things being equal, that puts a bigger load on the cache coherency protocol. (Not that I'm sure which protocols are used by contemporary hardware). –
Sophia Henning is correct. I will provide the details as they pertain to C#. The pattern can be generalized with the following function.
public static T InterlockedOperation<T>(ref T location, T operand)
{
T initial, computed;
do
{
initial = location;
computed = op(initial, operand); // where op is replaced with a specific implementation
}
while (Interlocked.CompareExchange(ref location, computed, initial) != initial);
return computed;
}
In your specific case we can define an InterlockedGreaterThanExchange function like this.
public static int InterlockedGreaterThanExchange(ref int location, int value)
{
int initial, computed;
do
{
initial = location;
computed = value > initial ? value : initial;
}
while (Interlocked.CompareExchange(ref location, computed, initial) != initial);
return computed;
}
Thread.MemoryBarrier which can be omitted because Interlocked.CompareExchange already generates one which prevents the read of location from getting lifted (by optimization) outside of the loop. You are right though, the x86 hardware has a tight guarantees, but the CLI (via the ECMA spec) has weak guarantees which means the optimization could take place at the JIT level. You have to code for the weaker model. That is why Thread.MemoryBarrier and the like exist in the first place. –
Zarate lock would be simpler and that is why I upvoted your answer, but a loop with a CAS operation would probably be faster especially in highly concurrent systems with many cores. –
Zarate There is no such atomic operation to execute both comparision and assignment in true atomic manner. In C# true atomic operations could be Interlocked operations like CompareExchenge() and Exchange() to exchange two integer values (32bit for 32bit architecture and 64-bit for 64 bit processor architecture).
Obviously simple assignment a = b is a two operations - read and write. So there is no possibility to do comparision + assignment in one atomic step... Does it possible in any other language/architecture, I mean true atomic? ;)
EDIT: Original question does not indicated that 'a' is local variable... uhhhggg such a small correction... any way I'll leave my answer as is because I believe in nature of true atomic operations and not in some kind of 'tricks' which has ambitions to be atomic
So to summarize:
a is local, so both a and b potentially could be accessed by an other threadobject lockObject = new object();
int a = 10;
int b = 5;
lock (lockObject)
{
if (a > b)
{
b = a
}
}
0. –
Brominate These are a couple of optimized "recipes" I came up with after reading other answers. Not directly related to the question, but adding here since this is where related searches landed. Tried to keep this to a > b or a >= b to match the original question. And to keep them general so as not to bias the descriptions away from other related problems. Both could be wrapped into methods.
bIf this is the only operation that is being done to b or b is otherwise monotonically increasing, you can optimize away the interlocked assignment and the retries where a > b == false:
int initial;
do
{
initial = b;
}
while ((a > initial) && Interlocked.CompareExchange(ref b, a, initial) != initial);
If a > b == false it won't be true after any retry (b is only getting larger) and the exchange can be skipped since b would be unaffected.
Action signal() should only be called once each time a local variable a (e.g., a system time sample) has increased by some constant threshold >= 1 since the last time signal() was called. Here, b is a threshold placeholder compared to a and set to a + threshold if a >= b. Only the "winning" thread should call signal().
var initial = b;
if ((a > initial) && Interlocked.CompareExchange(ref b, a + threshold, initial) == initial)
{
signal();
}
Here, b is again monotonic, but now we can optimize away the retry loop entirely since we only want to know if the local thread "won the race" with other threads while respecting threshold. This method will effectively "block" any other thread from signalling within the defined threshold.
This one will not work if you need a "strict" throttle--that is, the "smallest" a where a >= b--thus the "loose" in the title. This will also not work if you need to report only the last in a series of closely grouped as--what might be called "debouncing", related but distinct problem.
© 2022 - 2024 — McMap. All rights reserved.