A problem with pthread mutex and std::mutex is that they are often very large which is problematic for very fine grained locking, while you only need one bit for a spin lock and can be embedded in other objects (say, a pointer) as long as you can spare one bit.

Of course you can roll your own proper mutex if you want to get your hands dirty with futexes. IIRC you only need two bits (one waiter bit and one locked bit).

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.

I believe the supposed beneficial case of blocking vs spinning can't be captured well by those categories, as it's "contended, but not for long" and "contended, but for longer". That's the reason for the "may have a bit of capped spinning before waiting in the scheduler".

Honestly I'm not so sure about the case for spinning; in x264 source you can see CRITICAL_SECTION is tuned to have a spincount of 0. This is a very optimized, multi-threaded app. They didnt want any spinning.

https://github.com/mirror/x264/blob/d4099dd4c722f52c4f3c1457...

In my own attempts I've been unable to measure the impact of the spinlock count, and took spincount = 40 like in https://trac.webkit.org/browser/webkit/trunk/Source/WTF/wtf/... ...who also took measurement from elsewhere. The default is 4000 on Windows!

I don't argue spinning isn't valuable ; what I say is that it's necessarily never the bottleneck (else your task size really is too small).

After all, if you spend all your time in synchronization, that means you probably need to have bigger tasks, not more clever synchronization primitives.

Besides OS where they are often needed, spinlocks can have their place in a few very specific (and most of the time isolated on dedicated computers), but I agree that too many people are trying to play with them now, without enough knowledge.