Should interlocked implementations based on CompareExchange use SpinWait?

Question

Below is an implementation of an interlocked method based on Interlocked.CompareExchange.

Is it advisable for this code to use a SpinWait spin before reiterating?

public static bool AddIfLessThan(ref int location, int value, int comparison)
{
    int currentValue;
    do
    {
        currentValue = location; // Read the current value
        if (currentValue >= comparison) return false; // If "less than comparison" is NOT satisfied, return false
    }
    // Set to currentValue+value, iff still on currentValue; reiterate if not assigned
    while (Interlocked.CompareExchange(ref location, currentValue + value, currentValue) != currentValue);
    return true; // Assigned, so return true
}

I have seen SpinWait used in this scenario, but my theory is that it should be unnecessary. After all, the loop only contains a handful of instructions, and there is always one thread making progress.

Say that two threads are racing to perform this method, and the first thread succeeds right away, whereas the second thread initially makes no change and has to reiterate. With no other contenders, is it at all possible for the second thread to fail on its second attempt?

If the example's second thread cannot fail on the second attempt, then what might we gain with a SpinWait? Shaving off a few cycles in the unlikely event that a hundred threads are racing to perform the method?

When there is only 1 Thread, you don't need any code handling synchronisation. But when you have multiple Threads you do need it. No matter how small the code is you are executing. Even a simple `increment` (3 Assembly instructions) can get race conditioned and return a false value — MindSwipe, Nov 04 '19 at 15:13
@MindSwipe OP isn't asking whether it's necessary to use Interlocked; rather, should he use SpinWait instead of just the empty loop body? — Matthew Watson, Nov 04 '19 at 15:20
You should probably just use `SpinOnce` to prevent a single-threaded OS from potentially being starved. See https://stackoverflow.com/questions/37799381/spinwait-in-lockless-update — Matthew Watson, Nov 04 '19 at 15:22
@MatthewWatson I know, hence I left a comment, not an answer. It was a comment to the sentence "After all, the loop only contains a handful of instructions, and there is always one thread making progress" pointing out that no matter how few instructions, there is always a chance for a race condition — MindSwipe, Nov 04 '19 at 15:28
@MindSwipe The race condition is already handled correctly by virtue of using `Interlocked`. For clarification, I am only interested in whether or not a `SpinWait` is meaningful, for example to _meaningfully_ save CPU cycles or (thanks @MatthewWatson!) prevent a single-threaded OS from being starved. — Timo, Nov 04 '19 at 15:44
Then I misunderstood you. Saying "[...] but my theory is that it should be unnecessary. After all, the loop only contains a handful of instructions [...]" makes it seem like you think it's unnecessary to use Interlock because there is only such a small set of instructions, or it does at least to me — MindSwipe, Nov 04 '19 at 15:50
Spinwait bascially calls the pause CPU instruction which shuts down parts of the current core. This saves some electricity although Task Manager would show 100% CPU utlization. Skylake has changed the latency of this instruction from 14ns to 140ns which allows for longer pause times. Apart from power consumption you should see no difference as long as you are not mixing threads with different scheduler priorities. — Alois Kraus, Nov 04 '19 at 15:56
@AloisKraus I understand that in theory, but my reasoning is that this loop succeeds _on the next attempt_, regardless of whether or not we wait. That's why I expect that `SpinWait` will not even reduce power consumption, as the same number of attempts will be performed anyway! (With two threads, that is one attempt for the first and two for the second thread.) — Timo, Nov 04 '19 at 16:12
@Timo, I think you may benefit from a spin lock on platforms where Interlocked is not supported by hardware but has to be emulated. — Nick, Nov 04 '19 at 17:13
You tagged [tag:spinwait] "A spin-wait loop is a technique used in multithreaded applications whereby **one thread waits for other threads** for protecting a critical section, for barriers, or for other synchronizations." That doesn't sound at all like what you are asking. — curiousguy, Nov 11 '19 at 08:17
@MatthewWatson You mean with green threads? 1) How could there be a problem w/ RMW asm instr w/ green threads? 2) How would `spinWait.SpinOnce()` solve it? — curiousguy, Nov 11 '19 at 08:20
@Nick Which modern arch (where you find impl for modern PL) doesn't have RMW asm instr? — curiousguy, Nov 11 '19 at 08:21
@curiousguy I believe that one thread waiting for other threads to access a critical section is exactly what I'm asking about: All threads want to assign `ref location`. `Interlocked.CompareExchange` lets only one thread do that at a time. "Losing" threads loop vigorously, and `SpinWait` can make that _less vigorously_. The question is whether that adds practical value in this scenario, as the operation is _so_ simple and fast (i.e. threads succeed in such rapid succession that spinning may be overkill). — Timo, Nov 12 '19 at 10:22
@curiousguy Critical section `ref location` (the contended place in memory), which must only be written to by one thread at a time. As the question indicates, my theory is that looping vigorously is fine, and I'm trying to make sure that theory is correct. — Timo, Nov 12 '19 at 10:30

score 3 · Accepted Answer · answered Nov 04 '19 at 17:27

3

My non-expert opinion is that in this particular case, where two threads occasionally call AddIfLessThan, a SpinWait is unneeded. It could be beneficial in case the two threads were both calling AddIfLessThan in a tight loop, so that each thread could make progress uninterrupted for some μsec.

Actually I made an experiment and measured the performance of one thread calling AddIfLessThan in a tight loop versus two threads. The two threads need almost four times more to make the same number of loops (cumulatively). Adding a SpinWait to the mix makes the two threads only slightly slower than the single thread.

answered Nov 04 '19 at 17:27

Theodor Zoulias

34,835
7
69
104

1

What effect does SpinWait have with one thread, eg is there a reason not to use it? – Ian Ringrose Nov 04 '19 at 17:51
2

@IanRingrose it makes it 15% slower. I declare a variable of type `SpinWait` inside the `AddIfLessThan` method, and although it is a value type and its `SpinOnce` method is never called, it still adds some overhead. – Theodor Zoulias Nov 04 '19 at 18:03
3

@TheodorZoulias: You could declare in your IL body to skip init of locals which should give your nearly the perf back. You need to emit the IL code for this because there is no language support for it yet. See https://github.com/dotnet/csharplang/blob/master/proposals/skip-localsinit.md When you want to spin once you can call Reset on it and then SpinOnce. – Alois Kraus Nov 05 '19 at 06:52
1

Thanks @TheodorZoulias! FYI, the two threads was just an example to illustrate my point. This is a class library and can be used as the consumer sees fit. The best we can do is make assumptions about the likelihood of race conditions with many threads. Given how little time the operation takes, I deem it unlikely that many threads will perform this operation overlapping with each other. – Timo Nov 05 '19 at 10:28
1

If you are updating a tight loop, you should probably consider making the value private and update once at the end of loop. If the shared value needs to kept more or less actual and the loop is extremely long, consider updating the value like you advance a progress bar, once every X ms. – curiousguy Nov 11 '19 at 08:24

score 2 · Answer 2 · answered Nov 04 '19 at 20:50

2

Two threads is just not a subject for SpinWait discussion. But this code doesn't tell us how many threads can actually compete for the resource and with relatively high number of threads using of the SpinWait can become beneficial. In particular with higher number of threads the virtual queue of threads, which are trying to successfully acquire the resource, gets longer and those threads which happen to be served in the end have good chances to exceed their time slice allocated by scheduler which in turn can lead to higher CPU consumption and may affect execution of other scheduled threads even with higher priority. The SpinWait has good answer to this situation by setting some upper limit of allowed spins after which the context switching is going to be executed. So it's a reasonable trade-off between necessity to make an expensive system call in order to trigger a context switching and uncontrolled user mode CPU consumption which is under the risk to impact the other threads execution in certain situations.

answered Nov 04 '19 at 20:50

Dmytro Mukalov

1,949
1
9
14

The two threads was just an example to illustrate my point. This is a class library. We should be able to deal with any realistic scenario, taking its likelihood into account. Given how little time the operation takes, I deem it unlikely that many threads will perform this operation overlapping with each other. – Timo Nov 05 '19 at 10:31
You make a fair point. I agree that, with a lot of threads, some threads would fail many before succeeding. However, part of me thinks that the operation is so tiny that, say, performing it 100 times is still peanuts. With this in mind, would you expect it to make the `SpinWait` overkill, or not? – Timo Nov 05 '19 at 10:34
2

@Timo, the only answer is measurement, especially considering that this is going to be a library code which should be able to deal with various load and hardware scenarios I presume. For better fairness and thus for better throughput using the `SpinWait` is better strategy (with relatively small cost of dozens of microseconds) than not using that unless you exclude in advance a possibility of high low load scenarios, so finding a load point at which the throughput can be affected would give you a hint whether you need it or not (note that it also may depend on number of cores). – Dmytro Mukalov Nov 05 '19 at 11:20
With that many threads w/ need of a common resource for such long time so frequently that one is going to consume its time slice, I would either consider making private copies of the resource (to be synced later) or even abandon threads. – curiousguy Nov 11 '19 at 08:27
@curiousguy As stated 4 comments up, this is a class library. Of course the _consuming code_ could use a case-specific approach. The point of the class library, however, is to be resilient to various use cases. That's why the question remains in which situations the `SpinWait` adds value. So far, those seem to be (A) the single-core case, and (B) _possibly_ the very-high-contention case. – Timo Nov 12 '19 at 10:28
@Timo I still have no idea what is spinning and what is high contention case. – curiousguy Nov 12 '19 at 10:39
@curiousguy the private copy approach has very limited applicability (in particular, it's reasonable only when expected number of writes is much higher than expected number of reads, which is difficult to predict for a library usage) with high complexity of the read scenario. As for the abandoning threads, in cases when the computational scalability is needed (which is supposed to be true in this specific case) this is rather harmful suggestion as vast majority of modern devices use more than one core. – Dmytro Mukalov Nov 13 '19 at 13:16
@DmytroMukalov The "vast majority of modern devices" runs more than one program and not shipping a MT program doesn't mean that other cores won't be used. Suggesting that because there are many cores all programs should try to use as much as possible is rather harmful suggestion, as many programs could end up using much more CPU time and slowing down computers. – curiousguy Nov 13 '19 at 14:28
@curiousguy, you seem to talk about overall device utilization which has nothing to do with a specific program scalability. The computers are for computations and not using the all cores when I you potentially could do that means limiting the scalability of your program (please note, I stated it before when scalability is required). As for slowing down this seems to be a speculation there because it's mainly related to misusing of concurrency (but not with multi-threading itself) which can lead to oversubscription, unfairness, high contention and other negative things which impact performance. – Dmytro Mukalov Nov 13 '19 at 14:45
@curiousguy, if you are using multi-threading improperly it most likely will tend to affect the performance but this is rather subject of the implementation than question of whether to do that or not because using same logic the best suggestion would be not to develop any program at all as you can develop it improperly and it may `slow down a computer` or even worse get it down. – Dmytro Mukalov Nov 13 '19 at 14:49
@DmytroMukalov 1) High contention is what we were debating in the 1st place. 2) A good OS will limit the "damages" possibly done by a program. I'm just saying that not all programs need MT even if they are CPU intensive and running a MT program on more cores can turn the perf from good enough to catastrophic in a difficult to predict way. – curiousguy Nov 13 '19 at 15:04
@curiousguy, if you read my comments carefully you should notice that I repeated word `scalability` couple of times. Of course not all programs even those which imply heavy computations need multi-threading (even more the multi threading isn't always possible to apply) but those which need computational (not I/O) scalability require multi-threading. – Dmytro Mukalov Nov 13 '19 at 15:12
@curiousguy, As for the items: 1) yes, contention is somewhat related to subject and there receipts how to address such problems without falling back to a single threading (i.e without affecting required quality attributes) and 2) this is very broad statement regarding the OS - there are plenty of ways how a program can be harmful with no chance that a damage can be prevented by OS and as for the second part you seem to confuse reason of the potential problems - not MT by itself leads to the problems but misusing of it can be source of the problems. – Dmytro Mukalov Nov 13 '19 at 15:16

Should interlocked implementations based on CompareExchange use SpinWait?

2 Answers2