Not sure what you mean by a single bit for a spin lock. It's a cas operation, which doesn't operate on a single bit.

Edit: I think I see what you're getting at, but the point from the article about cache invalidation for the naive implementation still is valid.

You can do it with a single bit: Read the whole unit (eg 64 bit), flip the big you need, and then do a Compare exchange which tries to replace the whole retrieved thingy with the modified one.

That obviously requires you to read the current state upfront, whereas a plan compare exchange from 0 to 1 on 32/64Bit avoids that.

That doesn't work since this isn't atomic anymore.

Of course it is. The mutating operation is the CAS which requires the existing value anyway.

Mmmm... I had to write this down.

    0: CAS_bit_n(void* adr, int n)
    1: while(true):
    2:   old <- read unit(adr)
    3:   new <- compute-new-value-with-changed-bit-n(old, n)
    4:   if CAS(adr, old, new):
    5:     break
    6:   else
    7:     continue

Indeed it seems it is correct if you retry.

In fact normally a failed CAS (know as IBM-style CAS) will update the old value anyway so no need to reload old inside the loop; in c++11:

  auto old = addr.load(std::memory_order_relaxed);
  while(not addr.compare_exchange_weak(old, old|1))
     ;

In fact you can set old to some random value and it will still convergence to the correct value, but is of course suboptimal.

Interesting! Now I'm interested if there has been one usage case for the single bit spinlock in practice. It seems appropriate if writes aren't too numerous (well leaving aside speed concerns). Or a case where std::mutex was too large?

I've always wondered how the wait list was implemented.

Think about a concurrent hashtable using chaining for collision resolution; distinct bucket chains can be updated concurrently, so you need a per bucket lock but you do not want a full std::mutex as it would increase the size of the bucket table by a large integer multiple. Instead, borrowing one bit from the chain pointer (you can easily arrange the least significant bit of the pointer to be always zero) is pretty much free.

Note: I wrote the above from the top of my head, I haven't actually had the need to implement a concurrent hashtable yet.