Low-Level Atomic Operations

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.

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

<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

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

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

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

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

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

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

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

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

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

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.

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

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.

Maybe the conversation has moved on, but I'd find the wedging of the word Pointer into this a needless bit of verbosity (not to mention UnsafePointerTo is a really tortured term) and much prefer the original names. The word Unsafe is right there in your face as a clear indication you need to understand what you're doing and suffices to cover all the bases including the fact that these are reference types.

I don't see how "unsafe" implies "reference". There's no referencyness in, say, unsafelyUnwrapped.

1 Like

I didn't say it implied reference. I said it implied you need to know what you are doing, including whether it's a value or reference type. That said, I don't think comparing methods and types is much of a guide either way.

2 Likes

(I'll just innocently whisper into this parenthetical that I find Unmanaged to be a terrific name for an unsafe reference construct, and it carries neither an Unsafe honorific nor an in-your-face indication that it is referency. While we are at it, most class names do not scream "I'm a reference type, tremble before me", either.

We should have more names like Unmanaged.)

2 Likes

IUO is intentionally not a first class type in the core language, so I'm not sure that abstractions that try to make it so for atomics are a compelling use case, but if someone thought so, it seems like it could be done like this:

struct AtomicIUO<O: AtomicProtocol> { ... }

extension<Wrapped> AtomicIUO where O == Optional<Wrapped> { /* optional-specific API */ }

I'll say again that anything beyond ints is really "nice to have", so I'm hesitant to double the API surface for convenience features.

1 Like