5 ms·

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is working with a hand tied behind your back. With the wider version, it's trivial to write multi-producer multi-consumer stacks with no limits to the number of objects stored. It's also pretty easy (if you copy the published algorithm) to do the same with queues.

dnedic 3y ago
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.
- hedora 3y ago
  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.
gpderetta 3y ago
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.
- ot 3y ago
  > 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.
- moonchild 3y ago
  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.
aseipp 3y ago
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!) 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.
CyberDildonics 3y ago
> 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.
- gpderetta 3y ago
  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".
  - CyberDildonics 3y ago
    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.

dnedic 3y ago

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.

hedora 3y ago
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.

gpderetta 3y ago

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.

ot 3y ago
> 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.
moonchild 3y ago
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.

aseipp 3y ago

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!) 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.

CyberDildonics 3y ago

> 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.

gpderetta 3y ago
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".
- CyberDildonics 3y ago
  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.