Low-Level Atomic Operations

Evolution Pitches
81

That's a pretty clear answer, thank you.

I was indeed re-reading the pitch and was considering this quote:

we believe that the potential additional overhead of a class-based approach wouldn't be acceptable in the long term.

Thank you @ktoso!

1 Like
82

It looks like the set of protocols could be reduced a bit to simplify the design. NullableAtomic as a separate protocol could be avoided if we allowed multiple same-type-constrained protocol conformances directly on Optional, so that you could conform Optional where Wrapped == Foo directly to AtomicProtocol instead of indirectly conforming Foo to NullableAtomic. That might be a better way to go. Along similar lines, instead of making AtomicRepresentable be a separate protocol, we could instead provide a default implementation of AtomicProtocol for types that conform to RawRepresentable with a RawValue that conforms to AtomicProtocol, so that those types can declare conformance to AtomicProtocol and automatically pick up the implementation based on their raw value type

2 Likes
83

If we're going to support arbitrary types, we'll need a low-level protoco l that supports the atomic ops and a high-level one that supports arbitrary types (either by assuming representational compatibility, or by mapping in/out). As for Optional, part of the point of this proposal was that it didn't need language changes; it's an atomics model we can adopt now. We might be able to obsolete NullableAtomic in the future, but that's the idiom we have today, and I don't think we should try to pull in the larger feature of multiple conformances just to make this bit prettier.

2 Likes
84

That's not obvious to me. Can you explain why?

I see it the other way around. If we add an extra protocol now, we probably won't ever be able to take it back, and to me, supporting anything beyond Int and UInt is already "nice to have" above the fundamental functionality we're trying to expose. If some nice-to-have functionality can be done better and more simply with the right language support, the tradeoff of waiting for that language support seems like the right one. The fundamental limitation of conditional conformances today is that they shouldn't be able to introduce overlapping conformances, but overlapping is impossible with same-type constraints. Supporting multiple same-type-constrained conformances is AIUI "just" an implementation limitation, not really a new feature.

3 Likes
85

I suppose you're right, retracted. I like my two-protocol design because it means the zillion atomic operations don't have to appear on every atomic-compatible type, but it's not actually required, and Karoy's updated proposal doesn't use it. I agree that AtomicRepresentable could just be a default implementation in its current constrained form (AtomicStorage must match).

Multiple same-type-constrained conformances would complicate overload resolution and makes as? a search that can't be cached on a per-nominal basis. It might be something that gets added to the language, but I don't think it's an obvious addition, nor one that we ought to rely on getting in the near term.

While I agree that Int is the only thing people need to make atomic abstractions, there's been clear interest in this thread in doing more. I don't think NullableAtomic living forever is such a terrible cost that we should force people to use a third-party package to get that behavior in the mean time.

1 Like
86

I don't think same-type constraints are enough here -- in addition to allowing multiple conformances, we'd also need parameterized extensions:

extension Optional: AtomicProtocol where Wrapped == UnsafeRawPointer { ... }
extension Optional: AtomicProtocol where Wrapped == UnsafeMutableRawPointer { ... }

extension<Pointee> Optional: AtomicProtocol 
where Wrapped == UnsafePointer<Pointee> {...}

extension<Pointee> Optional: AtomicProtocol 
where Wrapped == UnsafeMutablePointer<Pointee> {...}

extension<Instance: AnyObject> Optional: AtomicProtocol
where Wrapped == Unmanaged<Instance>

This would be really, really nice, but I don't see how we could do this yet.

It's one additional protocol. The additional members it requires are indeed piling on top of the heap'o'junk created by AtomicProtocol, but I don't think that's a big deal. (I'd love to get rid of the ability to call AtomicProtocol's members outside generic contexts...)

(Edit: the reason I don't think it's a big deal is that these extra functions won't pollute type namespaces for people unless they import the Atomics module. Cutting the number of members by half would be nice, but I think the eight AtomicProtocol requirements already do far more aesthetic damage on their own. Going from 0 to 8 is a far bigger deal than going from 8 to 16. :wink:)

This is definitely possible. I was worried the default implementations could potentially trigger for types that happen to be RawRepresentable but need custom atomics, making it more difficult to correctly implement AtomicProtocol. This is a rather esoteric concern though -- I don't object to removing AtomicRepresentable.

87

In fact, this is now implemented, and I updated the pitch to reflect this.

@glessard reminded me in a comment on GitHub that we aren't providing weak compare/exchange operations yet.

Given that we have failure orderings, it seems reasonable that we should add weak CAS, too. (This is allowed to spuriously fail in certain situations, so it must always be called in a loop.)

protocol AtomicProtocol {
  static func atomicWeakCompareExchange(
    expected: Self,
    desired: Self,
    at address: UnsafeMutablePointer<AtomicStorage>,
    ordering: AtomicUpdateOrdering,
    failureOrdering: AtomicLoadOrdering
  ) -> (exchanged: Bool, original: Self)
}

extension UnsafeAtomic {
  public func weakCompareExchange(
    expected: Value,
    desired: Value,
    ordering: AtomicUpdateOrdering
  ) -> (exchanged: Bool, original: Value)

  public func weakCompareExchange(
    expected: Value,
    desired: Value,
    ordering: AtomicUpdateOrdering,
    failureOrdering: AtomicLoadOrdering
  ) -> (exchanged: Bool, original: Value)
}

At the same time, I think it would make sense to remove the single-ordering compareExchange variant from AtomicProtocol (while keeping it for UnsafeAtomic). This will make even the simpler compareExchange invocations go through a fifteen-case switch statement; I hope that won't lead to undesirable effects in the optimizer.

2 Likes
88

<sigh> This will interfere with constant-evaluable orderings, unless the single-ordering variant nests its lower-level compare-exchange calls in yet another switch statement. While I'm sure the compiler would still happily constant-fold six inlined switch statements with a sum total of 75 cases, but doing that for every single-order cmpxchg seems too rich for my taste, so instead let's just have three compare-exchange variants:

  • Strong compare-exchange with a single memory ordering (5 cases)
  • Strong compare-exchange with separate success/failure orderings (15 cases)
  • Weak compare-exchange with separate success/failure orderings (15 cases)

This means we'll always have to spell out two orderings on a weak cas. (At least until we have a more full-featured constexpr facility.)

Update: This is now implemented as well.

1 Like
89

Note: The implementation is now fully annotated to constrain ordering arguments to compile-time constants, as described in the pitch. This requires @ravikandhadai's behind-the-scenes Sema diagnostics work in apple/swift#26969; if you want to take it for a spin, you'll need to integrate both PRs for now.

let counter = UnsafeAtomic<Int>.create(initialValue: 0)
...

// OK: Directly passing an ordering using one of the static factory properties
counter.wrappingIncrement(ordering: .relaxed)

// BAD: Passing a local variable, an expression or any other potentially
// non-constant value

let order = ...
counter.wrappingIncrement(ordering: order) 
// error: ordering argument must be a static method or property of 'AtomicUpdateOrdering'

counter.wrappingIncrement(ordering: moon.isFull ? .acquiring : .releasing) 
// error: ordering argument must be a static method or property of 'AtomicUpdateOrdering'

The set of supported constructs is intentionally very limited -- basically we are only allowed to pass in the small handful of provided static properties on each ordering struct.

I expect we'll be able to relax this restriction and allow any constant-evaluable expression when (if) Swift gains a general-purpose constexpr facility. For now, limiting to the simplest possible case helps preserving source compatibility no matter what shape this language feature may take in the future.

3 Likes
90

Quick feedback on this (and I have to admit that I haven't studied to the depth I would like)--

  • AtomicProtocol is fine, but I think it'd be more descriptive if it were AtomicPrimitive or something like that. It would better express the idea that the conforming type itself is not an atomic type but the ingredient in some way for an atomic type.

  • Similar feedback for AtomicInteger.

  • I think it's unfortunate at best and misleading at worst that UnsafePointer, which was explicitly designed to be non-nullable, now conforms to a protocol named NullableAtomic. Of course, a reader can check the documentation, but UnsafePointer is neither nullable nor atomic. Could this protocol be named AtomicOptionalPrimitive?

  • Is there some way to make the API naming more self-documenting in respect of the need to pair atomicStorage with deinitializeAtomicStorage? The pairing of allocate/deallocate, create/destroy provides at least a hint to the user of what needs to be done, but I worry that no reader who sees atomicStorage will be reminded of the need to pair it with something.

3 Likes
91

Hi Karoy,

I remain super excited about this, I have use-case that I'd love to adopt this in now, I wish it were already shipping :slight_smile:. I hope it can fit into the preview package someday.

Here are my thoughts w.r.t. the "2020-03-30/2" version. I'm sorry but I haven't read all the upthread comments:

  • Thank you for splitting the background information out to a separate file, it makes it much easier to read the proposal. I appreciate it!

  • I agree that Atomics should be a separate module but included as part of the standard compiler distro like the Swift module.

  • I love unification under a new singular UnsafeAtomic generic type, this is great.

  • I think the name should still capture that it is reference-y. Something like UnsafeAtomicPointer or UnsafeAtomicReference or UnsafePointerToAtomic seems like it would make more room for the ownership-enabled future where we could have a non-reference version of the same thing.

  • This naming issue is even more pressing if you intend to introduce a pattern that is followed by higher level types like mutexes etc. It is practical to use an extra layer of pointer indirection in the immediate future, but we really need to be set up to be able to eliminate this in the future.

  • I have a couple of concerns about UnsafeAtomicLazyReference: the notion of "lazily initializable but otherwise read-only" is orthogonal from the idea of atomics, and orthogonal from the idea of an object reference, why tie all of these together? In terms of rationale, why can't this be done with the existing types? Could this type be split out to a smaller and more focused proposal?

  • Perhaps this is just a writing thing but I'd recommend the " The Atomics Module" section include a few examples using optionals and IUOs with the pointer type. If this isn't supported, it should be.

  • Did you consider a design that makes the unsafe pointer shenanigans be owned by the caller? This could be an optional different mode, but it would mean that pretty much everything would be exposed as a static member as well as an instance member. For example, your AtomicCounter example has a separately allocated atomic, which is unnecessarily wasteful. It would be great if it could be written as something like this instead:

class AtomicCounter {
  private var _value = 0

  init() {
    UnsafeAtomic<Int>.initialize(address: &_value, to: 0)
  }

  deinit {
    _value.destroy(address: &_value)
  }

  func increment() {
    UnsafeAtomic<Int>.wrappingIncrement(address: &_value, by: 1, ordering: .relaxed)
  }

  func get() -> Int {
    UnsafeAtomic<Int>.load(address: &_value, ordering: .relaxed)
  }
}

This API is yuckier to use of course, but is an acceptable loss to get better performance in the low-level code that this API is designed for, and it seems to compose directly on top of your existing protocol design. Ownership should come along and make this much nicer some day, and people who don't mind the indirection can use the API as proposed.

Overall, I'm really excited to see progress in this area, thank you for driving this forward!!

-Chris

6 Likes
SE-0282: Low-Level Atomic Operations
SE-0282: Low-Level Atomic Operations
92

Karoy -- thank you for working on this! I agree with the feedback from Chris above, and I also wanted to add a few more comments.

All of these are covered by a single generic struct called UnsafeAtomic that implements a reference type holding a single, untagged primitive value:

WDYT about "holding a pointer to a single, untagged primitive value"?

On ABI-stable platforms, the five @frozen struct types introduced here ( UnsafeAtomic , UnsafeAtomicLazyReference , AtomicLoadOrdering , AtomicStoreOrdering and AtomicUpdateOrdering ) will become part of the stdlib's ABI with availability matching the first OS releases that include them.

The protocols and protocol conformances too.

Most methods introduced in this document will be force-inlined directly into client code at every call site. As such, there is no reason to bake them into the stdlib's ABI -- the stdlib binary will not export symbols for them.

This requires more discussion, I think -- because the protocol witness tables would still be ABI, @_alwaysEmitIntoClient can't change that, I think. Adding more requirements to protocols would also be subject to regular ABI evolution rules.

The Ownership Manifesto introduces the concept of non-copiable types that might enable us to efficiently represent constructs that require a stable (and known) memory location. Atomics and other synchronization tools are classic examples for such constructs

Ownership manifesto introduces move-only types, which still require the instance to be movable. Atomics and mutexes are pinned to a memory location (because multiple threads must use a shared memory location), so atomics and mutexes are not just non-copyable, but also non-movable. The ownership manifesto does not provide a solution for non-movable types IIRC.

struct AtomicLoadOrdering [...] These structs behave like non-frozen enums with a known (non-public) raw representation.

Could you add more discussion explaining this choice of a struct over an enum?

To prevent these issues, we are adding a special type checking phase that artificially constrains the memory ordering arguments of all atomic operations to compile-time constants. Any attempt to pass a dynamic ordering value (such as in the compareExchange call above) will result in a compile-time error.

I think the proposal should note that this is true only when working with a concrete type. When working with an unknown type from a generic context the compiler will allow a dynamic ordering value (in fact, the implementation takes advantage of it, for example, in the implementation of UnsafeAtomic itself).

2 Likes
93

Ah, good point. Still, I see parameterized extensions as an "obvious" language hole we ought to fill sooner rather than later (and in fact there is a PR in progress to add them). Although the atomic library may be a separate module, it still benefits users to keep the API surface as small as possible.

3 Likes
94

I'd had this objection before, but actually if you have unique ownership of an atomic, it's okay to move it. You just may not ever be able to guarantee unique ownership if it's accessible to other threads, but with some outside-of-the-compiler knowledge it'd be safe. Maybe that's still not safe enough, though.

3 Likes
95

Yep. For reference, Rust's atomic types (which I think we should ultimately base our design for "safe" atomics on) are movable: Compiler Explorer

4 Likes
96

Leaving room for the non-copiable variant is not a concern here -- the "proper" atomic generic will be called Atomic<Value>.

UnsafeAtomicPointer<Value> is uncomfortably close to UnsafeMutablePointer<Pointee>, to the point of confusion. UnsafePointerToAtomic<Value> lends itself to a general naming scheme, so let's go with that one.

struct UnsafePointerToAtomic<Value>
struct UnsafePointerToAtomicLazyReference<Instance>
struct UnsafePointerToUnfairLock

Again, this is a non-issue; the eventual move-only variants won't have any of these naming warts.

moveonly struct Atomic<Value>
moveonly struct AtomicLazyReference<Instance>
moveonly struct UnfairLock

I'll try adding more examples. Optionals are explicitly supported.

Supporting implicitly unwrapped optionals with UnsafePointerToAtomic<Value> isn't feasible. We aren't modeling IUOs in the standard library any more, and UnsafePointerToAtomic<Foo!> is not supported as syntax.

Modeling IUOs through a separate type would be possible, of course:

struct UnsafePointerToAtomicImplicitlyUnwrappedOptional<Wrapped: NullableAtomic> {
  func isNil(ordering: AtomicLoadOrdering) -> Bool
  func load(ordering: AtomicLoadOrdering) -> Wrapped // traps on nil
  ...
}

However, I feel that low-level atomics are tricky enough to use correctly without having to deal with arbitrary implicit behavior layered on top of them. I don't think having to spell out the ! (or having to manually implement such a type) is going to be a hardship -- so I don't think such a construct belongs in the stdlib.

Agreed. But the language provides no (reliable) way to retrieve the memory location of a class instance variable -- the above code has undefined behavior. I previously explored this area in Exposing the Memory Locations of Class Instance Variables.

The implicit inout-to-pointer conversion is not appropriate for atomics, and I feel it's harmful to the language in general. The problem is that there is no way to disallow this conversion from occurring through a temporary variable. (I attempted to spell this out in Interaction with implicit pointer conversions.) The fact that it mostly works in practice is a huge problem, because we have no reasonable suggestion to replace it for people who absolutely do need to do such things. (Including the stdlib, sometimes.)

The only currently supported way to define "inline" storage for atomics is through ManagedBuffer.withUnsafeMutablePointerToHeader and MemoryLayout.offset(of:). This is decidedly not pretty, even in the lucky case where the Header is a single atomic value.

3 Likes
97

I just need to stop here and thank every one of you for the patient and incredibly thoughtful feedback. The pitch has gone a long way since we started, and it's getting better as a result of these discussions.

This is a feature that scratches at language limitations at practically every turn -- I think it's only barely possible to do it in the language we have, but that just makes it even more timely to get it done. For example, here is a partial list of potential language features that may make atomics work better, just from the last couple days:

  • Move-only types (or even non-movable types)
  • Addressable instance variables
  • Type system support for compile-time evaluable functions
  • Parameterized extensions
  • Multiple conditional conformances to the same protocol
  • Non-frozen but fixed-layout enum types
  • Context-aware property wrappers
  • Protocols that forbid unspecialized use
  • Functions that can't be called through function references
  • Back-deployable types and protocols
  • Protocol conformances with availability
  • Back-deployable protocol conformances

Some of these may land soon. Some are definitely a way off. And some will never get done. As a library engineer, I find it incredibly difficult to balance hypothetical future language improvements against the need to solve problems within the language we have today. Thanks for pushing against the bad compromises!

Oh, right, I'll need to amend this section; it doesn't reflect the current design.

I really don't want to add more digressions if I can help it, but I'll try to clarify the paragraph. (These cannot be frozen enums because that would prevent us from adding more cases, but regular resilient enums can't freeze their representation, and the layout indirection interferes with guaranteed optimizations, especially in -Onone.)

This is not quite true -- the protocol requirements are annotated with the magical semantic attribute, too, and the compiler does verify that UnsafeAtomic passes the orderings directly to the underlying implementations. (A "constexpr"-constrained argument value counts as a compile-time constant itself.)

Of course, the constant checks won't actually enable constant folding if the implementation is called in an unspecialized generic context, and it is still possible to defeat the constant checks using function references. (The constexpr-constrained methods may also implement protocol requirements that don't have the same constraints.)

In an ideal language, the atomic protocols wouldn't allow unspecialized use, and the methods implementing atomic operations wouldn't be compatible with regular function references.

4 Likes
98

Doing this would make it much more difficult to implement wrappers like the IUO thing above:

struct UnsafePointerToAtomicImplicitlyUnwrappedOptional<Wrapped: NullableAtomic> { 
  func isNil(ordering: AtomicLoadOrdering) -> Bool 
  func load(ordering: AtomicLoadOrdering) -> Wrapped // traps on nil ... 
}

(These will be plenty difficult already, what with all the constant-constrained arguments...)

Without a standalone protocol, we'd need yet another language extension to support generalized conformance requirements:

struct UPTAIUO<Wrapped> where Optional<Wrapped>: AtomicProtocol { 
  // error: type 'Optional<Wrapped>' in conformance requirement does not
  //        refer to a generic parameter or associated type
}

This tells me that there is value in modeling optional-supporting atomicable values with a named protocol.

99

Until then, I put together a package that makes atomics-through-clang source-compatible with Karoy's implementation: GitHub - glessard/SwiftCompatibleAtomics: Swift atomics implementation, source compatible with Swift's (possible) future Atomics submodule

It works with Swift 4.1.x, 4.2.x, 5.0.x and 5.2.x.
It crashes downloadable 5.1.x toolchains :disappointed: (including Linux), though it works with Xcode 11.3.1 :man_shrugging:.

2 Likes
100

I feel this is unnecessarily unwieldy. UnsafeAtomic says what's on the tin, and details (e.g. that it wraps a pointer) are available in the documentation. UnsafeUnfairLock would be just fine, and no worse for not having the PointerTo naming.