@robryk In particular I really like how it only requires that you are able to reserve one bit per pointer for the tag (instead of making you install a permanent per-thread data of some sort)
Makes it suitable for shims in the style of libatomic lole
But it does make you install semi-permanent per-operation data (the descriptors cannot be cleaned up until way later -- if you wanted to clean them up immediately you'd be back up to 2k CASes -- and even if they could you'd need to let them stay at least dereferencable-but-with-arbitrary-content for nearly as long).
You mean MCAS implementation where two operations on disjoint memory locations also have disjoint set of memory locations they access? My intuition is that it would be completely impossible to do waitfreely (via some similar argument to the one for Omega(thread_count) memory bound for nontrivial waitfree data structures).
Hm~ why does the lower bound assume that critical steps are CASes and not simple atomic writes? That's probably true in the setup where the number of threads is not bounded, but otherwise I see no obvious reason for that to be true.
Scratch that, I'm reading too inattentively. Still seems slightly fishy in different ways, but I'm probably still reading too inattentively.
Do you understand what is the thing they're providing bounds on? The lower bound seems to be on number of CASes needed pessimistically under some interleaving of contended MCASes and the upper seems to be on number of CASes needed for _uncontended_ MCAS operations.
@robryk Wait, which lower bound? I only see them saying that their method needs k+1 CASes when uncontended but nothing else I see
As for the bound in section 3, the details escape my understanding but what I do understand is that they are claiming that a k-word MCAS needs to do at least k CASes, but otherwise it doesn't seem to get used elsewhere in the paper?
The abstract made me think that one can assign "worst-case(?) number of CAS per MCAS" to any implementation of MCAS and that they prove that: (a) lower bound for that is k (b) their implementation achieves k+1. That would be a near-optimality claim about their implementation. However, that's not the case, because there are actually two different such values: the one the lower bound (in the Impossibility section) talks about is not the one they show is equal to k+1 in their implementation.
In fact, one can probably show that any such implementation, for some adversarial scheduling and operation sequences, might need to do unboundedly many CASes for some MCAS operations (otherwise it would be waitfree).
@robryk re:waitfree, interestingly the paper refers to another MCAS paper that claims to be waitfree: https://www.researchgate.net/publication/271738671_A_Wait-Free_Multi-Word_Compare-and-Swap_Operation
The main downside seem to be that it doesn't have a dedicated "writefree" read operation; reads are basically just an MCAS with funny operands?
(Not on computer now so this is just based on a skim)
@robryk Is there something like that that can be made waitfree?