sync/atomic: add OR/AND operators for unsigned types

[aktau]

Update, Aug 16 2023: Current proposal at #61395 (comment).

---

Original related proposal: #31748

Use case: we have types with methods that set a value. These methods manipulate a bitset indicating that the value was set, which is used (e.g.) for data serialization. Users of this API know to use a lock to manage concurrently reading/writing the same field, but they are allowed to concurrently write to different fields. Given that the bitsets are logically shared between different fields, we must manipulate them atomically. Currently that takes the form of a CAS loop:

type MyStruct struct{
  x int32
  y int32
  // ...

  present uint32 // Contains "present" bits for 32 fields.
}

func (m *MyStruct) SetX(v int32) {
  m.x = v
  setPresent(&m.present[0], 1)
}

func (m *MyStruct) SetY(v int32) {
  m.y = v
  setPresent(&m.present[0], 2)
}

func setPresent(part *uint32, num uint32) {
	for {
		old := atomic.LoadUint32(part)
		swapped := atomic.CompareAndSwapUint32(part, old, old|(1<<(num%32)))
		if swapped {
			return
		}
		// Yield and then try the swap again.
		runtime.Gosched()
	}
}

// similar for clearPresent, but with AND.

But, on x86-64, there are atomic versions of AND/OR that do this in one go, as mentioned in #31748. Using this would not only make the setters faster, it would likely also allow inlining them: setPresent is too complex to inline.

cc @aclements @ianlancetaylor @randall77

[rsc]

But, on x86-64, there are atomic versions of AND/OR that do this in one go, as mentioned in #31748. Using this would not only make the setters faster, it would likely also allow inlining them: setPresent is too complex to inline.

setPresent should not be calling runtime.Gosched. There's nothing another goroutine is going to do to help move things along (unlike, say, waiting for a mutex to be unlocked).

If you remove the Gosched, it should be inlinable. At least, -m says this is inlinable:

func orcas(x *uint32, bit uint32) {
	for {
		old := atomic.Load(x)
		if atomic.Cas(x, old, old|bit) {
			break
		}
	}
}

I wrote this in runtime/atomic_test.go:

package runtime_test

import (
	"runtime/internal/atomic"
	"testing"
)

func BenchmarkCas(b *testing.B) {
	var x uint32
	for i := 0; i < b.N; i++ {
		for {
			old := atomic.Load(&x)
			if atomic.Cas(&x, old, old|1) {
				break
			}
		}
	}
}

func BenchmarkOr(b *testing.B) {
	var x uint32
	for i := 0; i < b.N; i++ {
		atomic.Or(&x, 1)
	}
}

The result is:

BenchmarkCas-16                  	154634635	         7.429 ns/op
BenchmarkOr-16                   	270709120	         4.462 ns/op

So this would be an x86-only optimization that wins less than 2X. I'm not sure this really makes sense given how unusual it typically is. The main argument I can see is inlinability, but it seems to be inlinable already if written efficiently.

[aktau]

I was wondering about runtime.Gosched() as well, I couldn't figure out why it would help. Thanks for highlighting that it is indeed unnecessary.

So this would be an x86-only optimization that wins less than 2X. I'm not sure this really makes sense given how unusual it typically is. The main argument I can see is inlinability, but it seems to be inlinable already if written efficiently.

A 2x win may still be significant, but I'll know more when I add a better benchmarking setup. But also I found LDSET/LDSETA/LDSETAL/LDSETL for ARM, quoting:

Atomic bit set on word or doubleword in memory atomically loads a 32-bit word or 64-bit doubleword from memory, performs a bitwise OR with the value held in a register on it, and stores the result back to memory. The value initially loaded from memory is returned in the destination register.

I think the "atomically" may be referring to the entire operation. To be honest the mnemonic doesn't make it sound like this is a bitwise or. Perhaps an ARM expert could chime in.

[rsc]

Thanks for the link to LDSETAL. That looks like it might be good enough, although we would have to think carefully about whether the acquire-release semantics it guarantees matches the sequentially consistent semantics we want for sync/atomic when limited to the OR operation. Perhaps it does but perhaps not.

[aclements]

But also I found LDSET/LDSETA/LDSETAL/LDSETL for ARM

That's correct. ARMV8.1 added instructions for atomic And (also, Min/Max, and, for some reason, Xor). LDCLR, LDCLRA, LDCLRAL, LDCLRL is the equivalent for atomic And.

[aclements]

A 2x win may still be significant

I'll note that there was also no contention in @rsc's benchmark. Typically, CAS loops collapse far worse under contention than direct atomic operations.

[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

[zephyrtronium]

This might be a stretch, but another option could be to rewrite the simplest form of the CAS loop to the corresponding atomic operation on platforms that support it, similar to how "intrinsics" for encoding/binary work. That way old code using the thing that works now benefits as well. New API would still be convenient, but I think atomic flag sets that want it are rare, and if it's intrinsified then it can live in any package. I am given to understand this would be harder than existing rewrite rules, though, because it spans more than a single basic block. It may also be hard to formulate proofs that the rewrite preserves semantics.

[aclements]

This might be a stretch, but another option could be to rewrite the simplest form of the CAS loop to the corresponding atomic operation on platforms that support it

@randall77 actually prototyped exactly this. I'm not necessarily opposed to having these rewrite rules, but I don't think they're a substitute for just giving people the API that they need. Often, when writing low-level code like this, the developer wants to say what they mean and have a good sense of what's actually going on, so having to express this operation through a rather opaque rewrite rule seems too subtle.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[mateusz834]

What new API additions were proposed here?

[rsc]

I guess we all assumed we knew what the API was but forgot to write it down. Oops!
I think the new API is take anything that says Add in the current sync/atomic package and s/Add/And/ and also s/Add/Or/.
So there would be both new top-level functions and new methods on Int32, Int64, Uint32, Uint64, and Uintptr.

[mauri870]

Anyone currently working on this one? I've made some progress already and would like to finish the work. If that is ok please feel free to assign the issue to me. Thanks.

[mauri870]

Brief update: with Go1.22 entering a freeze, I've adjusted the milestone to Go1.23. Given our time constraints, it seems adequate to postpone since so far we have only internal bits merged.

[gopherbot]

Change https://go.dev/cl/544455 mentions this issue: sync/atomic: public And/Or apis

[gopherbot]

Change https://go.dev/cl/584715 mentions this issue: cmd/compile: intrinsify atomic And/Or on arm64

[aclements]

@mauri870 , congrats on landing all of this for 1.23!

I know that there's some follow-up work to make these operations intrinsic across common platforms (e.g., CL 584715 does most of this work for ARM64). I just wanted to ask if you're planning on working on that.

[gopherbot]

Change https://go.dev/cl/586515 mentions this issue: sync/atomic: revert "public And/Or ops and race instrumentation"

[gopherbot]

Change https://go.dev/cl/586516 mentions this issue: internal/runtime/atomic: fix missing linknames

[mauri870]

@mauri870 , congrats on landing all of this for 1.23!

I know that there's some follow-up work to make these operations intrinsic across common platforms (e.g., CL 584715 does most of this work for ARM64). I just wanted to ask if you're planning on working on that.

Thanks, @aclements! Unfortunatelly I lack enough experience with the compiler to implement these, so I’m happy to leave that to the experts.

[ruyi789]

OR/AND write protection without comparison and calculation is pointless and has long been removed in my code

func OrSet8u(ptr *uint8, set uint8, unset uint8) (old uint8) {
x:
	old = *ptr
	if !Cas8u(ptr, old, (old&^unset)|set) {
		goto x
	}
	return
}
func OrSet32u(ptr *uint32, set uint32, unset uint32) (old uint32) {
x:
	old = *ptr
	if !Cas32u(ptr, old, (old&^unset)|set) {
		goto x
	}
	return
}

func OrSet32u_Old(ptr *uint32, set uint32, unset uint32, old uint32) bool {
	return Cas32u(ptr, old, (old&^unset)|set)
}

[gopherbot]

Change https://go.dev/cl/593855 mentions this issue: sync/atomic: correct result names for Or methods

[aktau]

Thanks for the great work @mauri870. We'll have to wait a bit before starting to use this new API because intrinsifying is critical for us to yield a performance improvement. On my workstation I've measured a 1.5x slowdown by replacing:

	for {
		old := atomic.LoadUint32(part)
		if atomic.CompareAndSwapUint32(part, old, old|(1<<(num%32))) {
			return
		}
	}

With:

atomic.OrUint32(part, 1<<(num%32))

The former inlines into the function, the latter doesn't:

...
               	callq	0x47f1e0 <sync/atomic.OrUint32.abi0>
...

<sync/atomic.OrUint32.abi0>:
; sync/atomic.OrUint32.abi0():
; ./sync/atomic/asm.s:106
                jmp	0x47f380 <internal/runtime/atomic.Or32.abi0>

<internal/runtime/atomic.Or32.abi0>:
; ./internal/runtime/atomic/atomic_amd64.s:229
                movq	0x8(%rsp), %rbx
                movl	0x10(%rsp), %ecx
                movl	%ecx, %edx
                movl	(%rbx), %eax
                orl	%eax, %edx
                lock
                cmpxchgl	%edx, (%rbx)
                jne	0x47f389 <internal/runtime/atomic.Or32.abi0+0x9>
                movl	%eax, 0x18(%rsp)
                retq

It's great to see how only the last mile remains to be done. Hopefully someone can pick it up.

[gopherbot]

Change https://go.dev/cl/594976 mentions this issue: cmd/compile: fix typing of atomic logical operations

[gopherbot]

Change https://go.dev/cl/594738 mentions this issue: cmd/compile: make sync/atomic AND/OR operations intrinsic on amd64

[randall77]

Intrinsic And/Or are in for arm64 and amd64. (arm64 was released with 1.23. amd64 will be released with 1.24.)
If other maintainers want to intrinsify for other architectures, go for it. I'm happy to review.