How to atomically negate an std::atomic_bool?

Question

The naive boolean negation

std::atomic_bool b;
b = !b;

does not seem to be atomic. I suspect this is because operator! triggers a cast to plain bool. How would one atomically perform the equivalent negation? The following code illustrates that the naive negation isn't atomic:

#include <thread>
#include <vector>
#include <atomic>
#include <iostream>

typedef std::atomic_bool Bool;

void flipAHundredThousandTimes(Bool& foo) {
  for (size_t i = 0; i < 100000; ++i) {
    foo = !foo;
  }
}

// Launch nThreads std::threads. Each thread calls flipAHundredThousandTimes 
// on the same boolean
void launchThreads(Bool& foo, size_t nThreads) {

  std::vector<std::thread> threads;
  for (size_t i = 0; i < nThreads; ++i) {
    threads.emplace_back(flipAHundredThousandTimes, std::ref(foo));
  }

  for (auto& thread : threads) thread.join();

}

int main() {

  std::cout << std::boolalpha;
  Bool foo{true};

  // launch and join 10 threads, 20 times.
  for (int i = 0; i < 20; ++i) {
    launchThreads(foo, 10);
    std::cout << "Result (should be true): " << foo << "\n";
  }

}

The code launches 10 threads, each of which flips the atomic_bool a larrge, even, number of times (100000), and prints out the boolean. This is repeated 20 times.

EDIT: For those who want to run this code, I am using a GCC 4.7 snapshot on ubuntu 11.10 with two cores. The compilation options are:

-std=c++0x -Wall -pedantic-errors -pthread

Answer 1

b = !b is not atomic because in the C++ source you have an atomic pure read of b (equivalent to b.load(), and then a separately-atomic assignment to b (equivalent to b.store()).

Nothing makes the entire combination into an atomic RMW operation in the C++ abstract machine, and there's no syntax for composing arbitrary operations into atomic RMW operations (other than putting it into a CAS retry loop).

---

There are two options to use:

1. Instead of atomic<bool>, use an integral type (e.g. atomic<int> or atomic<unsigned char>) which can be 0 or 1, and xor it with 1:

   std::atomic<int> flag(0);
   
   flag ^= 1;        //equivalent to flag.fetch_xor(1);
   

   Unfortunately, fetch_xor is not provided on atomic<bool>, only on integral types.

2. Perform a compare/exchange operation in a loop, until it succeeds:

   std::atomic<bool> flag(false);
   
   bool oldValue = flag.load();
   while (!flag.compare_exchange_weak(oldValue, !oldValue)) {}
   

   Unfortunately compilers for x86 won't typically optimize this loop into
   lock xor byte [flag], 1 in the asm; you'll get an actual cmpxchg retry loop. In practice cmpxchg retry loops are fine with low contention. In the worst case this is not wait-free, but is lock-free because at least one thread will make progress every time they all retry. (In practice it's more complicated with hardware arbitration for which core even gets access to the cache line to make an attempt.)

   If high contention is possible, prefer the integer version that lets you use an atomic xor.