Atomics

[Joe_Groff]

It might also be useful for Never to conform to AtomicValue, with itself as its AtomicStorageRepresentation, so that it can be used in generic substitutions to represent the lack of a value.

[Karl]

@Alejandro

The only thing I'm unsure of is Atomic<Value> because the compiler could complain this will require a metadata initialization at runtime, but we force inline everything anyway (even in debug) so in theory there will never be any runtime metadata needed to use atomics (unless you're using a generic atomic in which case no, very bad, don't do this ).

I thought we weren't interested in supporting generic atomics? Supporting Never might encourage that kind of use.

[Joe_Groff]

The Language Steering Group looked over this proposal today in preparation for considering it for review, and we had some additional comments. These may serve as additional topics for pitch or review discussion, or future directions, if the authors deem them out of scope for this proposal.

• The proposal still states that the AtomicValue and AtomicOptionalWrappable types should only be conformed to by the standard library. Now that this version of the proposal makes them explicit, is there a reason for this limitation? What happens if external code does implement its own conformances?

• The choice to only provide atomic operations that can be implemented lock-free makes sense, but it raises the question of how portable code can detect what atomic operations are available and provide alternative implementations based on different target platforms' capabilities. A full answer to that problem is likely out of scope for this proposal, but the authors' experience implementing this proposal might inform discussion of the features necessary to do so effectively.

• We may want to front-load existing additional standard library types conforming to AtomicValue if we have reason to believe they ever will, since making them conform later will have back deployment limitations. In addition to floats, mentioned as a future direction, and the UnsafeBufferPointer and Never cases mentioned in the thread above, are there any other standard library types that could be useful as atomic values? A couple that came to mind were OpaquePointer and ObjectIdentifier.

• Conversely, the proposal notes in the discussion of AtomicLazyReference that Atomic<Unmanaged<T>> is very difficult to use correctly. How strong are the use cases for it? Should it be provided at all?

• The AtomicIntNNStorage type names seem like something that could easily show up in code completion when someone types Atomic, and they might look like the types that the developer wants to use. We may want to namespace these and/or give them less appealing names.

• In addition to wrapping increment/decrement, should overflow-checked increment/decrement be provided as well? It should be possible to detect overflow without affecting the atomicity of the operation by checking the returned old value, and doing so correctly is fiddly enough that it seems worth a standard implementation.

[Alejandro (Alejandro Alonso)]

@Joe_Groff

The proposal still states that the AtomicValue and AtomicOptionalWrappable types should only be conformed to by the standard library. Now that this version of the proposal makes them explicit, is there a reason for this limitation? What happens if external code does implement its own conformances?

Yeah, now that everything is public and there is no implementation defined parts of the atomic API it makes sense to open the flood gates for these protocols and allow others to conform.

@Joe_Groff

The choice to only provide atomic operations that can be implemented lock-free makes sense, but it raises the question of how portable code can detect what atomic operations are available and provide alternative implementations based on different target platforms' capabilities.

The most immediate thing that occurs is double wide atomic support that is pretty architecture specific. Some compilation conditional like #if hasDoubleWideAtomics might suffice here.

Another big area for concern might be checking for wait-free operations. Currently we don't make a guarantee that things like wrappingIncrement are wait-free, but it may seem useful to at least query if the target we're compiling for has native support for those kinds of operations. Although the alternative code path wouldn't be wait-free, but maybe code bases may want to just unconditionally statically error in those cases.

@Joe_Groff

We may want to front-load existing additional standard library types conforming to AtomicValue if we have reason to believe they ever will, since making them conform later will have back deployment limitations. In addition to floats, mentioned as a future direction, and the UnsafeBufferPointer and Never cases mentioned in the thread above, are there any other standard library types that could be useful as atomic values? A couple that came to mind were OpaquePointer and ObjectIdentifier.

I think the following list of types would be great first candidates for AtomicValue / AtomicOptionalWrappable conformances. Anything besides those listed would have limited usability and may just be an attractive nuisance for doing the wrong thing.

extension Int8: AtomicValue {}
extension Int16: AtomicValue {}
extension Int32: AtomicValue {}
extension Int64: AtomicValue {}
extension Int: AtomicValue {}
extension UInt8: AtomicValue {}
extension UInt16: AtomicValue {}
extension UInt32: AtomicValue {}
extension UInt64: AtomicValue {}
extension UInt: AtomicValue {}

extension Bool: AtomicValue {}

extension Float16: AtomicValue {}
extension Float: AtomicValue {}
extension Double: AtomicValue {}

// New name for DoubleWord which will be discussed
// in a revision to the proposal soon.
extension WordPair: AtomicValue {}

extension Duration: AtomicValue {}

extension Never: AtomicValue {}

extension UnsafeBufferPointer: AtomicValue {}
extension UnsafeMutableBufferPointer: AtomicValue {}
extension UnsafeRawBufferPointer: AtomicValue {}
extension UnsafeMutableRawBufferPointer: AtomicValue {}

extension UnsafePointer: AtomicOptionalWrappable {}
extension UnsafeMutablePointer: AtomicOptionalWrappable {}
extension UnsafeRawPointer: AtomicOptionalWrappable {}
extension UnsafeMutableRawPointer: AtomicOptionalWrappable {}
extension Unmanaged: AtomicOptionalWrappable {}
extension OpaquePointer: AtomicOptionalWrappable {}
extension ObjectIdentifier: AtomicOptionalWrappable {}

extension Optional: AtomicValue where Wrapped: AtomicOptionalWrappable {}

We did discuss whether it truly makes sense for Unsafe*BufferPointer to conform to AtomicValue and we do feel its usefulness is limited and may lead to doing the wrong thing. However, if anyone should provide this conformance it should be the standard library and it's simple enough to add. Conversely, one can make the same argument for other types within the standard library that "could" be atomic that the standard library should be the only definer of the conformance, but we feel this list is a good balance between usefulness and currency types within the stdlib.

@Joe_Groff

Conversely, the proposal notes in the discussion of AtomicLazyReference that Atomic<Unmanaged<T>> is very difficult to use correctly. How strong are the use cases for it? Should it be provided at all?

We think Unmanaged's conformance to AtomicValue is still useful despite it being difficult to use correctly. One of the examples of its usefulness is the fact that AtomicLazyReference is quite simply an Atomic<Unmanaged<T>?> underneath the hood. Similar atomic constructs could be made that utilizes this conformance and the standard library should be the one to define it.

@Joe_Groff

The AtomicIntNNStorage type names seem like something that could easily show up in code completion when someone types Atomic, and they might look like the types that the developer wants to use. We may want to namespace these and/or give them less appealing names.

These types are generally unusable from outside the standard library anyway because of their very limited API surface area (I don't think they even have anything public to begin with). We can add API to these types to make them usable for use in AtomicValue conformances by trafficking in various integer types, but we can tell users to hook onto an integer's atomic representation. It's really a question of do we want conformers of AtomicValue to look like:

struct MyIntWrapper {
  var value: Int
}

extension MyIntWrapper: AtomicValue {
  typealias AtomicRepresentation = AtomicStorage8

  static func encodeAtomicRepresentation(
    _ wrapper: consuming MyIntWrapper
  ) -> AtomicRepresentation {
    AtomicStorage8(wrapper.value)
  }

  ...
}

or

struct MyIntWrapper {
  var value: Int
}

extension MyIntWrapper: AtomicValue {
  typealias AtomicRepresentation = Int.AtomicRepresentation

  static func encodeAtomicRepresentation(
    _ wrapper: consuming MyIntWrapper
  ) -> AtomicRepresentation {
    Int.encodeAtomicRepresentation(wrapper.value)
  }

  ...
}

Note that the original intention behind exposing the storage types was to have a single storage type that types like UInt8, Int8, and Bool for example could all hook onto. We can still preserve this as an implementation detail. By hiding these types and making users use something like Int.AtomicRepresentation we can solve the naming problem for these things entirely. We still need WordPair (previously named DoubleWord) as a type to hook the AtomicValue conformance and as a portable name. That being the case it seems reasonable to expect users to define their conformances in terms of the primitive integer type's atomic representation (or word pair's) as that would be the most portable way of achieving an Int sized storage for example. We don't currently have a public compilation conditional to query int/pointer size so it'd be unreasonable to expect folks to write something akin to:

#if somethingHere
typealias AtomicRepresentation = AtomicStorage64
#else
typealias AtomicRepresentation = AtomicStorage32
#endif

Of course, we could then define another atomic storage type like AtomicStorageSize or whatever, but we already have this name as Int.AtomicRepresentation.

@Joe_Groff

In addition to wrapping increment/decrement, should overflow-checked increment/decrement be provided as well? It should be possible to detect overflow without affecting the atomicity of the operation by checking the returned old value, and doing so correctly is fiddly enough that it seems worth a standard implementation.

Yeah, we can provide overflow-checked increment/decrement operations. There does need to be a line though because while we can implement overflow-checked increment/decrement (which hardware does not have support for) we could in theory also provide things like multiply, divide, floating point add/subtract, etc. Checked increment/decrement makes sense to add because we're adding the wrappable versions which have hardware support for.

[Joe_Groff]

@Alejandro

These types are generally unusable from outside the standard library anyway because of their very limited API surface area (I don't think they even have anything public to begin with). We can add API to these types to make them usable for use in AtomicValue conformances by trafficking in various integer types, but we can tell users to hook onto an integer's atomic representation. It's really a question of do we want conformers of AtomicValue to look like:

It seems like there are going to fewer conformers to AtomicValue than users of atomics, and the steering group's concern was for the user experience. Namespacing the representations under corresponding integer types again might be a good way to avoid polluting the top-level namespace when you look for Atomic; maybe nesting the storage types under an AtomicStorage enum namespace could be another approach?

@Alejandro

Yeah, we can provide overflow-checked increment/decrement operations. There does need to be a line though because while we can implement overflow-checked increment/decrement (which hardware does not have support for) we could in theory also provide things like multiply, divide, floating point add/subtract, etc. Checked increment/decrement makes sense to add because we're adding the wrappable versions which have hardware support for.

Even if it's not directly supported by hardware, atomic counters are a fairly common use case, and overflowing can be disastrous for the same reasons any other overflowing counter is. And on classic x86 at least, I believe LOCK XADD does set flags and could be used to implement the overflow check with hardware support (although I know LLVM doesn't expose atomic overflow-checked builtins).

[Karl]

@Joe_Groff

Namespacing the representations under corresponding integer types again might be a good way to avoid polluting the top-level namespace when you look for Atomic; maybe nesting the storage types under an AtomicStorage enum namespace could be another approach?

The SIMD types are nested within the integer types; for instance, there is a UInt8.SIMD32Storage type. We could use that as precedent.

[scanon (Steve Canon)]

@Joe_Groff

I believe LOCK XADD does set flags and could be used to implement the overflow check with hardware support

Unfortunately it's a little bit more subtle. LOCK XADD still writes the updated value when overflow happens, which means that the wrapped result would be observable between the update and when the flag check actually occurs later on, which is probably undesirable for most use cases--the point of using a checked increment would be to guarantee the invariant that wrapping is never observed. I think in practice these have to be implemented with compare-exchange on current HW (this is a good example for why we should provide it, though--it's pretty subtle to get right!)

[Alejandro (Alejandro Alonso)]

Back with another round of revisions!

1. I've added some more conformances to AtomicValue in the standard library. Namely the floating point types (excluding Float80), the unsafe buffer types, never, opaque pointer, object identifier, and duration.
2. I've clarified in the proposal text that on 32 bit platforms, UInt64, Int64, and Double only conform to AtomicValue when there is support for double wide atomics. On all platforms that do not support double wide atomics, Unsafe*BufferPointer, and WordPair do not conform to AtomicValue. Finally, Duration only conforms on 64 bit platforms that have double wide support.
3. I've hid the atomic storage types under {U}Int*.AtomicRepresentation. While we've stated we don't like hiding API, these types were somewhat useless from the outside and their public name is already available through the .AtomicRepresentation. I've included another sample conformance in the proposal by going through Int.encodeAtomicRepresentation for example.
4. Renamed wrappingIncrement/wrappingDecrement to wrappingAdd/wrappingSubtract. This change was done because other APIs on integer types are all called adding*/subtracting* and we wanted to preserve symmetry here with the rest of the library. This means the function no longer has a default parameter of = 1 for the operand and must be explicit: wrappingAdd(1, ordering: .relaxed).
5. Checked add/subtract. An overflow checked version of the above was added to trap at runtime when trying to add more than {U}Int*.max/subtract less than {U}Int*.min. These are named: add(_:ordering:) and subtract(_:ordering:). Used like: counter.add(1, ordering: .relaxed).
6. Renamed DoubleWord to WordPair. Similar to feedback from Joe regarding the user experience of atomics, we feel DoubleWord may confuse those with the actual Double type in the standard library. WordPair directly conveys the semantic meaning of this type and shouldn't be something that pops up from code completion regularly. I added the DoubleWord name as an alternative considered.
7. Removed the ThenLoad suffix from AtomicLazyReference.storeIfNil. The last revision merged the loadThenX and xThenLoad methods, so to be consistent remove this suffix from this method as well.

I apologize that there's seemingly a lot of changes still being made, but some of these are "mostly" minor tweaks I really appreciate all of the feedback so far, and think we've landed on something that's a really nice improvement over the original proposed API!