Is a comparison an atomic operation?

Question

Is the following comparison an atomic action? I.e., can it be reduced to a single CPU instruction?

char flag = 2;

for(;;)
{
    if (!flag) // <-- this
        break;

    // sleep
}

Here's what I'm doing:

int main()
{
    sf::Mutex Mutex;
    char flag = 2;

    coordinatorFunction(flag);

    for(;;)
    {
        if (!flag)
            break;

        // sleep
    }
}

void workerFunction(void* a)
{
    char* p = static_cast<char*>(a);

    // work

    GlobalMutex.Lock();
    --*p;
    GlobalMutex.Unlock();
}

void coordinatorFunction(char& refFlag)
{
    sf::Thread worker1(&workerFunction, &refFlag);
    sf::Thread worker2(&workerFunction, &refFlag);

    worker1.Launch();
    worker2.Launch();
}

I think it'll always have to be read into a register before doing the compare, since you've passed on a pointer to it. So no, it wont be atomic. That's what I think, I don't know for sure. I believe there are ways to do atomic compare-and-write, though (not within the C++ language itself I guess).. — falstro, Apr 24 '11 at 19:55
It doesn't follow that if something can be reduced to a single CPU instruction, then it is atomic. Firstly not all CPU instructions on all architectures are atomic, and secondly just because something can be reduced to an instruction that is atomic doesn't mean it will be. — Steve Jessop, Apr 24 '11 at 20:00

score 7 · Accepted Answer · answered Apr 24 '11 at 19:56

7

This is the wrong way to go about it.

Your main thread is burning up CPU cycles as fast as it can, doing nothing but waiting for flag to reach zero. This test will fail every time it's attempted, except the last one. Instead of doing it in this manner, use the "join" facility that your thread objects most likely have to make the main thread suspend itself until all the workers complete.

This way, not coincidentally, you won't care if the test is atomic because you will not need it at all.

answered Apr 24 '11 at 19:56

Jon

428,835
81
738
806

Damn. I should have thought of that. Thanks. – Truncheon Apr 24 '11 at 20:02
I'm trusting that the original code isn't doing a busy wait :) – seand Apr 24 '11 at 20:04

score 2 · Answer 2 · answered Apr 24 '11 at 19:53

2

None of C++ operations is guaranteed to be atomic operation.

answered Apr 24 '11 at 19:53

Nawaz

353,942
115
666
851

score 2 · Answer 3 · answered Apr 24 '11 at 19:53

2

In C++ nothing is guaranteed to be atomic.

answered Apr 24 '11 at 19:53

David Heffernan

601,492
42
1,072
1,490

score 2 · Answer 4 · answered Apr 24 '11 at 19:57

No. As far as I know, C++ makes no guarantees on what is atomic and what is not - that is platform specific. Even if your platform guarantees that a comparison can be made atomically, there's no guarantee that your C++ compiler will choose that instruction.

However, in practice, a comparison of a simple value type such as a char, int, float, etc is likely to be atomic. You still need to be aware of possible reordering of instructions however, both at the compiler level and the processor level. In this case, that may not matter, but in the general case, it can and does. You also need to be aware that a comparison-then-branch is not atomic even if the comparison is - so 2 threads can both enter the same block of code if you are trying to use a flag to regulate that access.

If you want proper guarantees, there are various Interlocked functions on Windows and the atomic builtins on gcc.

score 1 · Answer 5 · answered Apr 24 '11 at 19:52

1

No, C++ makes no guarantees that any operation is atomic. The code in your question might well be compiled into a load from memory into a register, which might itself take multiple instructions, followed by a test.

answered Apr 24 '11 at 19:52

So do I need to change the code to make it thread safe, or is it already? – Truncheon Apr 24 '11 at 19:59
@Truncheon The term "thread-safe" is pretty meaningless - thread-safety is entirely context-dependant. But in general, any resource (variable, whatever) that is accessed from multiple threads must be protected by some sort of lock. Left to their own devices, compilers never generate "thread-safe" code. – Apr 24 '11 at 20:04

score 1 · Answer 6 · answered Apr 24 '11 at 19:55

The comparison is not atomic because it make take several machine language instructions to do it (load the from memory into a register etc.) Also due to memory model flexibility and caching the thread doing the test may not "see" the results of another thread right away.

You might be safe doing a simple test if the variable is marked volatile but this will be platform-specific. As others noted C++ itself makes no guarantee on this.

user541686 · Answer 7 · 2011-04-24T20:00:26.793

1

No.

A comparison involves reading both pieces of data as well as performing the actual comparison. The data can change in between the read and the compare instructions, so it's not atomic.

However, because you're comparing for equality, the _InterlockedCompareExchange instrinsic (which is for the lock cmp xchg instructions in x86) might do what you need, although it will involve replacing the data.

edited Apr 24 '11 at 20:00

answered Apr 24 '11 at 19:55

user541686

205,094
128
528
886

However, on many platforms if the comparison is against zero, there is a dedicated opcode to perform that. This means that if the value is already in a register it can indeed be done atomically. – Kylotan Apr 24 '11 at 19:58
@Kylotan: I don't think it matters, you still need to read it into a register and *then* compare. The issue isn't the comparison, it's the in-between state. But if you have pointers to memory (instead of values in a register) then yes, that's correct; I've updated my answer. – user541686 Apr 24 '11 at 19:59
*if* the value is already in a register, but how would you guarantee that? – seand Apr 24 '11 at 20:01
You wouldn't. I'm not arguing against the 'No' part of this answer. :) I'm just saying the comparison doesn't always involve reading 2 pieces of data. – Kylotan Apr 24 '11 at 20:04
What matters when comparing with any constant is not that the data might change between the read and compare instructions, but rather that it might change between the time it is read and the time one *acts upon the result of the comparison*. Provided the read is atomic, since the comparison will have no observable effects until one acts upon it, there would be no meaningful sense in which the comparison would be atomic or not. Of course, if the read is not atomic, the comparison won't be either. – supercat Apr 13 '12 at 02:31

score 0 · Answer 8 · edited May 23 '17 at 12:22

The question you should be asking is "is -- atomic"? Thats all that matters here. You want to do something when flag reaches 0.

You don't care about this scenario:

1. Main thread reads flag, and it is 1.
2. Worker changes flag with --
3. Main thread doesn't see that flag is actually 0.

Because in 1 ns, the main thread loops around and tries again.

You do care that -- is not atomic and two threads changing it at the same time will skip decrements:

1. Thread A reads flag, flag is 2
2. Thread B reads flag, flag is 2
3. Thread A decrements its copy of flag, 2, and writes to flag, flag is 1
4. Thread B decrements its copy of flag, also 2, and writes to flag, flag is 1.

You lost a decrement. you want to use __sync_fetch_and_sub(&flag, 1) which will atomically decrement flag.

Finally, spinning around a sleep is not the best way to do it. You want to either wait on a condition, wait on a signal. Have the worker threads raise the condition or the signal when they realize they have decremented flag to 0.

Is a comparison an atomic operation?

8 Answers8