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 Swap, CompareAndSwap #26728

Closed
carl-mastrangelo opened this issue Jul 31, 2018 · 10 comments
Closed

proposal: sync/atomic: add Swap, CompareAndSwap #26728

carl-mastrangelo opened this issue Jul 31, 2018 · 10 comments

Comments

@carl-mastrangelo
Copy link
Contributor

carl-mastrangelo commented Jul 31, 2018

(this is a fork of the discussion on https://go-review.googlesource.com/c/go/+/126295 )

This proposal is a combination of changes that are tightly coupled with each other that extend the functionality of atomic.Value. Normally these would be separate proposals, but it would be technically suboptimal to implement them as such.

Specifically, this proposal suggests that atomic.Value be changed in the following ways:

  1. Allow setting nil
  2. Allow changing the concrete type of the Value
  3. Add a CompareAndSwap method to Value
  4. Add a Swap method to Value.

The current API is the way it is due to implementation details, as indicated on the original change. https://codereview.appspot.com/120140044/ Discussion claims

If we allow storing of nil, it will complicate implementation of type-stability and will require Value to be 3 words.

Additionally, it also suggests a use case where an unset value has meaning, lending itself to disallow nil:

A polling goroutine updates a shared cache stored in an atomic.Value; http handlers use this cached data. In this scenario, if the polling goroutine fails, it is preferable to have no data than to have stale data. A natural way to tell the http handlers that the cached data is unavailable is to Store(nil), as opposed to having to create a sentinel value or add a pointless bool.

While this use case may be present, it is more cleanly handled by using a sentinel value, rather than forcing nil to be (and thus preventing it from being up to the user).

Reasons why this change is safe and valuable:

  • atomic.Value can be considered a type safe atomic interface{}, similar to the other atomic methods for unsafe.Pointer and the various integer types. However, unlike interface{}, Value prevents nil from being stored. This is surprising, and requires closely reading the docs. Also unlike interface{}, the concrete type cannot change. This too is surprising, and not actually a necessary requirement. Enabling these to be used is backwards compatible.

  • In some environments (like AppEngine), using unsafe is not possible, leaving only standard library packages for use. Doing typesafe atomics depends on the standard library providing this functionality.

  • CompareAndSwap and Swap are standard atomic operations, and are exposed for the other types in the atomic package. It is surprising that these do not exist. (from an API point of view, it is clear why they don't when looking at the implementation). These methods are invaluable for resolving code that may race without resorting to locks.

Alternatives considered

  • Using unsafe.Pointer. While the functionality can be duplicated by using unsafe.Pointer and the related atomic methods, this necessarily gives up type safety. It is infeasible to use on AppEngine, gopherjs, or in environments where unsafe is unavailable. While unsafe.Pointer is faster, the proposed Value changes are only minutely slower, and would not materially affect users. (users who did care about speed would not have used Value in the first place, and would instead prefer plain atomic.*Pointer methods).

  • Add CompareAndSwap and Swap, but leave nil and concrete type changes forbidden. Due the the proposals implementation, it would be difficult and complicated to prefer the original limitations. The proposals implementation is much simpler to read, understand by having all changes in a single proposal.

  • Expose this functionality in the third party package, and integrate it if it gets popular. Because atomics are already a niche subject, and the use cases are mostly solved by using Go's other concurrency primitives, It is unlikely that an external library would ever get enough adoption. Having a single, correct, well tested, and widely used implementation of atomic values would be best for the Go library and Go users. That location is in sync/atomic. As a side benefit, the Go compiler is in a unique position to rewrite code using sync/ atomic for optimization purposes; this would be unrealistic if it lived outside.

  • Do Nothing. If the proposal is rejected, the way users implement this functionality is with locks, using channels, or using unsafe.Pointer. The first two are heavier weight operations than atomics, and force the user to maintain an additional variable. (they may already have one, but maybe not). Using unsafe is more error prone than using Value directly which is also undesirable.

Implementation costs

The proposed API changes come with a proposed implementation. Currently, the Value code unpacks the provided interface{} into its component words, and does two, atomic loads / stores. The proposed change boxes the value as a pointer to an interface, which is then used inside of Value. This means that stores now allocate two words of memory, and reads must chase an additional pointer.

I believe these costs are acceptable for three main reasons:

  1. The use case of Value today is specifically for frequent reads and seldom writes. A slightly slower store will not have real world impact.
  2. Benchmarks of reads shows only minor performance difference (~0.1ns) between the two implementations.
  3. Users who do care about performance have a clear alternative (which they are likely doing already) by using the unsafe atomic operations.

I believe it is much more valuable to add this backwards-compatible, useful, unobtrusive, and simpler atomic code, and the performance difference is inconsequential.

cc: @dfawley @ianlancetaylor @dvyukov

@gopherbot gopherbot added this to the Proposal milestone Jul 31, 2018
@rsc
Copy link
Contributor

rsc commented Aug 6, 2018

This seems like a complete non-starter to me. You are completely replacing the API with a different API, one that requires additional per-operation allocations, when the current API seems just fine, all with very little justification as to why the new API is more compelling.

If all you need is Swap and CompareAndSwap, it seems to me that those are possible to implement without completely rewriting the internals.

And the few cases that truly need type mutability can always store a *interface{} into the atomic.Value.

@rsc rsc changed the title proposal: add atomic.Value.CompareAndSwap, Value.Swap, and expand functionality proposal: sync/atomic: add Value type mutability, Swap, CompareAndSwap Aug 6, 2018
@carl-mastrangelo
Copy link
Contributor Author

Hi @rsc,

I think I responded to most of your criticisms in the proposal. Would you mind including more technical detail about what specifically you don't like?

As a side note: I randomly looked through some usages of atomic.*Pointer in codesearch. In pretty much every case, using atomic.Value (with my proposed change) would have been more safe and equally as fast.

@rsc
Copy link
Contributor

rsc commented Aug 13, 2018

Expanding my earlier response:

  1. Operations in sync/atomic must not require memory allocation.
    It matters a lot that Go operations, especially very low-level ones like these,
    give programmers control over what allocates and what does not.
    It matters that code written to not allocate today should not start allocating tomorrow.
  2. Type mutability in atomic.Value seems useless/borderline harmful to me.
    If we'd had generics then atomic.Value would be an atomic.Value[T].
    Code in which a single atomic.Value changes its underlying type seems to me
    more complex and difficult to understand than code in which an atomic.Value
    has one specific (hopefully documented) underlying type.
  3. The forced memory allocation in Value.Store etc is being done to support type mutability.
    Given the previous two points, this is not the right tradeoff.
  4. CompareAndSwap and Swap can be implemented in the current code,
    without introducing type mutability and forcing memory allocation.
    If there is a compelling motivation for adding them, then let's do that by itself.

@carl-mastrangelo
Copy link
Contributor Author

carl-mastrangelo commented Aug 13, 2018

Operations in sync/atomic must not require memory allocation.
It matters a lot that Go operations, especially very low-level ones like these,
give programmers control over what allocates and what does not.
It matters that code written to not allocate today should not start allocating tomorrow.

It does matter I agree, which is why there is a clear and accessible way to avoid allocations already: atomic.*Pointer operations. atomic.Value should be about type safety. I don't understand why allocations are not allowed. I expected you to say something along the lines of "it might crash if allocations aren't allowed" or "it would be a surprising slowdown", but you didn't. Both of these are countered in the proposal, so I don't know what other reason there could be.

Type mutability in atomic.Value seems useless/borderline harmful to me.
If we'd had generics then atomic.Value would be an atomic.Value[T].
Code in which a single atomic.Value changes its underlying type seems to me
more complex and difficult to understand than code in which an atomic.Value
has one specific (hopefully documented) underlying type.

Again, I offer that atomic.Value is a parallel of interface{}, which does allow nil and type mutability. Additionally, other languages permit the equivalent type mutability in their atomics, which is useful. I'd like to call on your experience in other languages as reason why it's useful.

As a brief example, consider an atomic.Value which stores the last error set. error is an interface, and it would be cumbersome to have to assert that all errors stored in the value had identical types. That forces users to create a wrapper type for no reason.

CompareAndSwap and Swap can be implemented in the current code,
without introducing type mutability and forcing memory allocation.
If there is a compelling motivation for adding them, then let's do that by itself.

Continuing with the atomic.Value which stores an error: Try making an atomic.Value hold the first error, and ignore the rest. value.CompareAndSwap(nil, err) is tricky because there was never a previous store of nil. Additionally, if multiple CompareAndSwap race, it may be true that only one wins, but they may have had different types. I called out why all these changes are needed in a single proposal in the very first sentence.

By adopting this proposal, I don't think there is an example where code would be more bug prone, nor would the performance become measurably worse.

@rsc
Copy link
Contributor

rsc commented Aug 14, 2018

If we do CompareAndSwap and Swap, they will be subject to the same type-immutability constraints as Store. Racing CompareAndSwap is no different than racing Store.

Using an atomic.Value to store an error is a mistake. If that's what motivates all this angst, store a *error (or a *interface{}) instead. Yes, it's a little clumsy, because the API as written (even your new API) drops the interface wrapping, but that's a property of interface-based general APIs, not this one. It doesn't merit workarounds here.

Right now atomic.Value is suitable for users who want performance and type safety. The bad idea that if you want performance (no unexpected allocations) then you have to give up type safety is exactly what we were trying to address by adding atomic.Value in the first place. Under no circumstance should we be telling users "this code worked for you before, but not anymore, and oh by the way the fix is to introduce new uses of unsafe into your code."

@carl-mastrangelo
Copy link
Contributor Author

carl-mastrangelo commented Aug 14, 2018

If we do CompareAndSwap and Swap, they will be subject to the same type-immutability constraints as Store. Racing CompareAndSwap is no different than racing Store.

Agree.

Using an atomic.Value to store an error is a mistake. If that's what motivates all this angst, store a *error (or a *interface{}) instead.

This was the first example I found in our code that used Atomics, not a special case.

but that's a property of interface-based general APIs, not this one. It doesn't merit workarounds here.

Not sure how you can interpret it as not interface based. The only two methods of Value are interface{} based. The only thing that distinguishes it from the rest of the atomics is that it accepts interface{}. Calling the proposed methods as "workarounds" ignores the clear shortcomings in the API.

Right now atomic.Value is suitable for users who want performance and type safety.

Let's take a look at another usage of atomics and see if they are satisfied by the current API: sync.Map. This implementation is basically the same as my proposal, except that it doesn't use Value at all, and does use Pointer. It boxes the interface value, and uses an additional sentinel variable expunged to get around not being able to use nil. If this proposal is accepted, sync.Map could take advantage of Value.

Here is another example of Value's implementation warts appearing on the API, forcing an unnecessary cast:

cc.retryThrottler.Store((*retryThrottler)(nil))

These weren't even that hard to find. Look through atomic\.(Value|.*Pointer) on codesearch or godoc, and you'll see numerous examples where Value underperforms. Lot's of comments on Value's API. Lot's of places where unsafe.Pointer is used due to not being able to use nil.

Under no circumstance should we be telling users "this code worked for you before, but not anymore, and oh by the way the fix is to introduce new uses of unsafe into your code."

Could you clarify what you mean by "worked"? The proposal was specifically chosen to be backwards compatible with existing usage.

@bcmills
Copy link
Contributor

bcmills commented Sep 14, 2018

Add a CompareAndSwap method to Value

See #11260.

Add a Swap method to Value.

See #20164.

If this proposal is accepted, sync.Map could take advantage of Value.

sync.Map, being in the standard library, should ideally be more efficient than using individual Values. (That's #21031.)


Note @rsc's comment in particular:

If we'd had generics then atomic.Value would be an atomic.Value[T].

I think this proposal should wait until we figure out what (if anything) is happening with generics (#15292).

If we can add a type-parametric version of atomic.Value, that would probably address the awkwardness around nil and around changing concrete types: a typed atomic.Value should allow the concrete type to change if (and only if) the new type is assignable to the Value's type parameter.

@rsc
Copy link
Contributor

rsc commented Sep 19, 2018

Narrowing this proposal to "add Swap and CompareAndSwap", not changing the rest of the API.

Can anyone make a strong case for adding Swap and CompareAndSwap?

@rsc rsc changed the title proposal: sync/atomic: add Value type mutability, Swap, CompareAndSwap proposal: sync/atomic: add Swap, CompareAndSwap Sep 19, 2018
@dfawley
Copy link

dfawley commented Sep 25, 2018

Can anyone make a strong case for adding Swap and CompareAndSwap?

AppEngine code cannot use unsafe pointers, but it can use atomic.Value, so having Swap & CompareAndSwap in atomic.Value would be functionality that is otherwise inaccessible to some users.

It seems to me that environments where unsafe pointers are disallowed is the only real value of atomic.Value. atomic.Value is slower than unsafe pointer atomics, has less functionality, and the type information provided by it is mostly unnecessary, since its type can never change after initialization.

@rsc
Copy link
Contributor

rsc commented Oct 10, 2018

There aren't many environments that reject unsafe anymore, and we shouldn't contort the library for those.

It would be fine for someone who has a compelling use for these to create a new issue proposing to add Swap and CompareAndSwap (or to reopen this one, if you have permission). For now, given the lack of a real-world use case for them, we will err on the side of leaving it out.

@rsc rsc closed this as completed Oct 10, 2018
@golang golang locked and limited conversation to collaborators Oct 10, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants