Tagged pointers

[inspirit]

what is the reason to choose DCAS instead of Tagged pointers to solve ABA problem?
I assume tagged pointers should be faster at runtime due to easier atomic operation.

[skeeto]

A 16-byte alignment, which would typically be the case, leaves just 4
bits for the tag. Unlike a 32 bit counter, or especially a 64 bit
counter, that's certainly small enough to concern me about race
conditions. If a mere 16 updates are completed and a pointer re-used by
other threads within the cmpxchg loop, the ABA counter will wrap around
and the ABA test will incorrectly pass.

Also, while the current version relies on more advanced processor
features (DCAS), tagged pointers are formally-speaking non-portable:
there are no guarantees in the C standard about pointer representations.
(Though I'd be willing to bet that any implementation that supports DCAS
would also have a reasonable integer-like pointer representation.) Since
this is primary for demonstration purposes, I wanted to take the most
straightforward, correct approach.

As a side note, I was curious just how much slower DCAS is on x86_64.
According to this document,

http://www.agner.org/optimize/instruction_tables.pdf

Locked cmpxchg8b has a latency of 53 and locked cmpxchg16b has a latency
of 94, so it really is almost twice as slow.

[inspirit]

You can force alignment of the elements to free up to 16 bits for the counter.