Technically, this doesn't solve the ABA problem, since there is still a chance that $popcount$ overflows and loops around back to the original $popcount$ value, causing $pop$ to pass even though the state has changed. However the chance of this happening is extremely low given $popcount$ is 32-bit.

Perpendicular

Notice that actually it is not necessary that we use pop count. We could instead use any increasing counter. something like time stamp of the last successful pop request.

lol

That's not really any different from popcount. Any counter must be stored in a finite number of bits, and there is a maximum. The timestamp is stored in a 64-bit integer. So this just reduces the probability of error by a lot, but there is still a chance that it fails.

jrgallag

Using timestamps wouldn't be Y2K safe!

memebryant

@Perpendicular, it's not even necessary for it to be increasing, it's just necessary for it to be different for a "sufficiently long" number of operations. Additionally, here we assume $2^{32}$ is sufficiently large enough, but in practice people seem willing to use as little as $2^9$ (MS SList implementation on non cmpxchg16b platforms).

Technically, this doesn't solve the ABA problem, since there is still a chance that $popcount$ overflows and loops around back to the original $popcount$ value, causing $pop$ to pass even though the state has changed. However the chance of this happening is extremely low given $popcount$ is 32-bit.

Notice that actually it is not necessary that we use pop count. We could instead use any increasing counter. something like time stamp of the last successful pop request.

That's not really any different from popcount. Any counter must be stored in a finite number of bits, and there is a maximum. The timestamp is stored in a 64-bit integer. So this just reduces the probability of error by a lot, but there is still a chance that it fails.

Using timestamps wouldn't be Y2K safe!

@Perpendicular, it's not even necessary for it to be increasing, it's just necessary for it to be different for a "sufficiently long" number of operations. Additionally, here we assume $2^{32}$ is sufficiently large enough, but in practice people seem willing to use as little as $2^9$ (MS SList implementation on non

cmpxchg16bplatforms).