sync/atomic: add Uint64Pair

[haraldrudell]

I suggest CAS2 is implemented in the atomic package similar to atomic.align64, operational for hardware that supports it.

possibly also:

• atomic OR
• LL/SC Load-link/store-conditional

—

• With the 2022 memory model, go1.19 atomics became useful after years of unproductive near-sighted discussions
• However, wait-free algorithms now use CAS2, ie. 128-bit atomic, which is supported on most cpus but not in Go
• implementing CAS spinners in lock-free applications produces long thread wait-times or 100% cpu, so wait-free is better: threads are neither suspended or spinning. We will have 100 cores and 100 GiB RAM from Apple soon enough
• what is desired is a performant wait-free queue and wait-free free-list stack
• fast-path of wCQ Nikolaev Ravindran 2022 and wfq Yang Mellor-Crummey 2016
• this would enable an initial thread-pool to have wait-free and allocation-free data sink

darwin-arm64 darwin-amd64 linux-amd64

I think also atomic generics could do with another polish
Like this AtomicMax that is more flexible in what underlying integer types and named types can be used: https://github.com/haraldrudell/parl/blob/main/atomic-max.go

• by inventing align64 only in atomic, 64-bit things must go in atomic

[ianlancetaylor]

I think the proposal here is

// CompareAndSwapUint128 executes the compare-and-swap operation for a 128-bit
// integer, represented as a pair of 64-bit integers.
func CompareAndSwapUint128(addr *uint64, old1, old2, new1, new2 uint64) (swapped bool)

But see also #9455. If we adopt that, then this version of the function would no longer make sense. So perhaps the proposal here should be

// CompareAndSwapUint64Pair executes the compare-and-swap operation for a 128-bit
// integer, represented as a pair of 64-bit integers.
func CompareAndSwapUint64Pair(addr *uint64, old1, old2, new1, new2 uint64) (swapped bool)

Presumably hardware does not have a 128-bit CAS operation could implement this using something like the lock table in runtime/internal/atomic/atomic_arm.go.

[randall77]

Perhaps

func CompareAndSwapUint64Pair(addr *[2]uint64, old, new [2]uint64) (swapped bool)

On x86 at least, the hardware instructionCMPXCHG16B requires its argument to be 16-byte aligned. I'm not sure how we would enforce that. It sounds like #599 all over again.

[merykitty]

We could have atomic.Uint64Pair which can be enforced specially by the compiler to have 16-byte alignment. An API point to operate on arbitrary pairs of uint64 seems improbable.

[haraldrudell]

1. CAS2 atomic.CompareAndSwap is one required 128-bit instruction for wait-Free 2016+
2. The other is fetch-and-add FAA atomic.Add
3. LL/SC is only used if the other 2 do not exist and is actually more complicated, likely for some unusual platforms that are not arm64 or amd64
4. If there is none of that, it’s slow-path

There is a Go package that uses array of uint64, [2]uint64 in its api:
github.com/CAFxX/atomic128

Generally, the data used is not a 128-bit number but a composite of often two 64-bit numbers that are changed atomically as a pair

[CAFxX]

There is a Go package that uses array of uint64, [2]uint64 in its api: https://github.com/CAFxX/atomic128

FTR this was just out of necessity (due to the lack of uint128) more than anything else. It's true that both intel and arm define their DWCAS instructions as operating on pairs of 64-bit values, but that does not automatically mean we should expose that in our APIs (especially given the alignment requirements that are uncharacteristic of uint64s)

[rsc]

Which systems would support this function?

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group