True, that would help immensely in creating MPMC data structures, but as these are SPSC there is no problem. Also to clarify, this is only for the indexes, the data members can be anything.

Using these intrinsics or inline assembly would break portability or create situations where platforms have different feature levels, which is not something I intend to do. I want the library to be compatible with everything from a tiny MCU to x86.

I've had good luck assuming double-word CAS, portability-wise. Old ARMs have 32 bit pointers, so 64 bit CAS is pretty good. The main problem is that some algorithms go from a bit under 64 bits for a nonce to a bit under 32, which starts to get into "this could hit in practice" territory.

Actually C++ only requires TriviallyComparable for std::atomic. The issue with 2CAS is that intel until very recently only provided cmpxchg16b[1] but no 128 atomic load and stores: SSE 128 bit memory operations were not guaranteed to be atomic (and in fact were observed not to be on some AMDs).

So a 128 bit std::atomic on intel was not only suboptimal as the compiler had to use 2cas for load and stores as well, but actually wrong as an atomic load from readonly memory would fault. So at some point the ABI was changed to use the spinlock pool. Not sure if it has changed since.

If you do it "by hand", when you only need a 2cas, a 128 bit load that is not atomic is fine as any tearing will be detected by the CAS and 'fixed', but it is hard for the compiler to optimize generic code.

[1] which actually does full 128bit compare and swap, you are probably confusing it with the Itanium variant.

> Not sure if it has changed since.

It hasn't, Clang/GCC emit a cmpxchg16b only if you opt-in with `-mcx16`, which changes the ABI.

128-bit aligned loads and stores are guaranteed to be atomic on all intel and amd cpus that support avx. And if your cpu doesn't support avx, it probably doesn't have enough cores that the performance of concurrent data structures matters that much.

The lack of DWCAS as a primitive in general is really annoying, C++ aside. RISC-V's -A extension has no form of it, either; you only get XLEN-sized AMO + LL/SC (no 2*XLEN LL/SC either!) I was going to try porting an old lock-free slab allocator to my hand-written RISC-V core, and it uses DWCAS in precisely the way you mention. Immediate roadblock.

It's one of those features that when you want it, you really really really want it, and the substitutions are all pretty bad in comparison.

> Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits

The instructions should compare 128 bits and swap 128 bits.

I don't know why 'good' algorithms would use these if they don't need to, because 128 bit operations are slower.

Not only that, 128 bit compare and swap doesn't work if it is not 128 bit aligned while 64 bit compare and swap will work even if they aren't 64 bit aligned.

On x86, any CAS on a misaligned address that crosses a cache line boundary can fault in the best case (if the mis-feature is disabled by the os) or cost thousands of clock cycles on all cores. So it "works" only for small values of "works".

That's over a cache line boundary, but 128 bit don't even work when they are unaligned, so you can't do things like swap two pointers, then move down 64 bits and swap two more pointers.