4 ms·
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-
by p0nce 7y ago
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.
- gpderetta 7y agoIn 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.
- p0nce 7y agoInteresting! 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.
- gpderetta 7y agoThink 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.