Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: sync/atomic: add Max/Min operators #63999

Open
mauri870 opened this issue Nov 8, 2023 · 3 comments
Open

proposal: sync/atomic: add Max/Min operators #63999

mauri870 opened this issue Nov 8, 2023 · 3 comments

Comments

@mauri870
Copy link
Member

mauri870 commented Nov 8, 2023

Recently I came across this TODO comment in runtime:

func (s *sweepClass) update(sNew sweepClass) {
// Only update *s if its current value is less than sNew,
// since *s increases monotonically.
sOld := s.load()
for sOld < sNew && !atomic.Cas((*uint32)(s), uint32(sOld), uint32(sNew)) {
sOld = s.load()
}
// TODO(mknyszek): This isn't the only place we have
// an atomic monotonically increasing counter. It would
// be nice to have an "atomic max" which is just implemented
// as the above on most architectures. Some architectures
// like RISC-V however have native support for an atomic max.
}

This sounds like a useful primitive to have when you need an atomic counter. This is similar to the accepted proposal for And/Or operators

Initially, as the comment suggests, we can use a similar stub implementation using a for loop and atomic Cas, but we should be able to write optimized assembly code per GOARCH.

We can check the machine code for such a routine in C and Go stub. For Risc-V we have AMOMAX and AMOMIN we can use, not sure about other arches.

There is a proposal to add atomic maximum/minimum to libstdc++. Quoting some of the motivations used there:

  • optimal implementation of lock-free shared data structures - as in the motivating example later in this paper
  • reductions in data-parallel applications
  • recording the maximum so far reached in an optimization process, to allow unproductive threads to terminate
  • collecting statistics, such as the largest item of input encountered by any worker thread.

For runtime/internal/atomic, we would need

Max
Max64
Maxuintptr
Min
Min64
Minuintptr

The proposed apis for sync/atomic would look something like this:

func MaxInt32(addr *int32, val int32) (old int32)
func MaxInt64(addr *int64, val int64) (old int64)
func MaxUint32(addr *uint32, val uint32) (old uint32)
func MaxUint64(addr *uint64, val uint64) (old uint64)
func MaxUintptr(addr *uintptr, val uintptr) (old uintptr)

func (*Int32) Max(val int32) (old int32)
func (*Int64) Max(val int64) (old int64)
func (*Uint32) Max(val uint32) (old uint32)
func (*Uint64) Max(val uint64) (old uint64)
func (*Uintptr) Max(val uintptr) (old uintptr)

func MinInt32(addr *int32, val int32) (old int32)
func MinInt64(addr *int64, val int64) (old int64)
func MinUint32(addr *uint32, val uint32) (old uint32)
func MinUint64(addr *uint64, val uint64) (old uint64)
func MinUintptr(addr *uintptr, val uintptr) (old uintptr)

func (*Int32) Min(val int32) (old int32)
func (*Int64) Min(val int64) (old int64)
func (*Uint32) Min(val uint32) (old uint32)
func (*Uint64) Min(val uint64) (old uint64)
func (*Uintptr) Min(val uintptr) (old uintptr)

Regarding the race detector, there are no fetch_max/fetch_min functions in tsan so that needs to be implemented as well, there shouldn't be a problem with this and I'm open to submit such changes to llvm upstream if that helps to move forward with this proposal.

Please feel free to share opinions and possible use cases for such a feature.

@gopherbot gopherbot added this to the Proposal milestone Nov 8, 2023
@mauri870
Copy link
Member Author

mauri870 commented Nov 8, 2023

@adonovan
Copy link
Member

For Risc-V we have AMOMAX and AMOMIN we can use, not sure about other arches.

  • Arm64 has LDSMAX.
  • PPC seems to have unsigned UMAX .
  • AMD64 will have to make do with read-modify-write.

See also #61236, whose first note mentions a Go implementation of AtomicMax also based on RMW.

@swatson314159
Copy link

I found this when googling the best way to achieve the following use case already stated:

collecting statistics, such as the largest item of input encountered by any worker thread.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Incoming
Development

No branches or pull requests

5 participants