Low-Level Atomic Operations

[drexin (Dario Rexin)]

First of all thanks @lorentey for this incredibly detailed writeup. I'm really looking forward to finally having atomics in the stdlib.

I agree that having a default ordering would be easier to get started with, but I also think that atomics are a highly specialized feature and thus people should familiarize themselves with the functionality before using them. Making it explicit forces people to think about it, instead of just relying on a less than optimal default case.

As for the argument whether atomics should only be atomically accessible, I think it would be okay to start that way, but a lot of lock free algorithms benefit from writing non-atomically and then committing all the writes in a single atomic store at the end. So I think we should definitely offer this at some point.

[drexin (Dario Rexin)]

@glessard

• I am doubtful that there is another safe use of UnsafeAtomicUnmanaged.load beyond the one used in the pitched lazy reference. As I commented on github, load and store on that UnsafeAtomicUnmanaged perhaps shouldn't exist at all. The various exchange methods are sound, because one can ensure the refcount doesn't get decremented from 1 to 0 in a racing thread.

There are other use cases where this type is useful, for example single reader queues. If you think about it, UnsafeAtomicUnmanaged is pretty much the same as std::atomic for pointer types. Yes, you have to be careful when using it, but I think the name makes that very explicit.

[ktoso (Konrad 'ktoso' Malawski 🐟🏴‍☠️)]

@glessard

• Int64/UInt64 should be in the initial version, because Int is often insufficient on a 32-bit platform.

FYI in case you missed it, those are already included/covered
https://github.com/apple/swift/pull/27229/files#diff-c938716d1f6256da1ac82430457d71f2R14-R27

[gribozavr (Dmitri Gribenko)]

@glessard

• I don't understand the purpose of having both load-then-atomic-rmw and atomic-rmw-then-load operations, especially when the implementation of the latter is based on the former:

I think these operations are provided for convenience, to avoid duplicating the code in the caller.

@glessard

• Finally, if all this functionality must only be used as inline code, why does it need to be gated by ABI version?

Executable code might be all inlined into callers, but just declaring a public type has ABI impact because a type has a name (which will appear in name mangling of other ABI symbols), a type exposes metadata, and since there are inlineable functions that we want to be fast the type will be @frozen so its memory layout will be exposed etc.

[glessard (Guillaume Lessard)]

I see. Thanks

[lorentey (Karoy Lorentey)]

@jrose

I like the idea of a single generic struct + associated protocol, though I'd name it UnsafeAtomicPointer<Value> .

I feel quite strongly that Pointer is not a good suffix for these. UnsafeAtomicInt is no more a pointer than Unmanaged is, and reusing an existing name clashes with atomic pointer types.

How about using the suffix Handle for these new animals? Calling something a FooHandle is a good indication that it is a reference-like thing capturing a Foo value.

"Handle" has some legacy baggage, but previous uses are roughly in the same ballpark and none of them apply to current Swift. (Here I'm following the de facto standard practice of studiously ignoring FileHandle. )

I'm also inclined to argue that the Handle suffix should imply memory unsafety, so that we can loose the Unsafe prefix:

struct AtomicHandle<Value: PrimitiveAtomic> {
  static func create(initialValue: Value) -> Self
  func destroy()

  init(at address: UnsafeMutablePointer<Value>)
}

struct UnfairLockHandle {
  static func create() -> Self
  func destroy()

  init(at address: UnsafeMutablePointer<os_unfair_lock>)

  func lock()
  func unlock()
} 

Note that this Handle/create/destroy/init(at:) mess is really only needed because we cannot have the design we really want yet. However, I think we ought to have a better (low-level) representation for synchronization constructs than classes.

None of this business will apply to the eventual non-copiable atomic types. Those will be neither value nor reference types, which implies we have the freedom to name them without any such warts:

moveonly struct AtomicInt {
  init(_ value: Int)
  deinit
  func load(ordering: AtomicLoadOrdering = .sequentiallyConsistent) -> Int
  ...
}

moveonly struct UnfairLock {
  init()
  deinit
  func lock()
  func unlock()
}

If we had non-copiable types today, we would probably not be adding pointer-based atomics (or at least we would definitely not be adding them in the first round), because we wouldn't want to design the underlying layout of atomic types directly into the public API. (init(at:) is a critical part of the Handle concept; I find it really hard to convincingly argue against supporting "inline" storage (however ugly it is to implement with ManagedBuffer).)

[Chris_Lattner3 (Chris Lattner)]

To add one more +1 for a generic type like UnsafeAtomicPointer<Value> (however it gets named), it would be very nice for this to work with Implicitly Unwrapped Optionals as well.

[lorentey (Karoy Lorentey)]

@jrose

• Does create need an ordering argument, or is it guaranteed that anyone who's managed to acquire the atomic reference has already performed some kind of synchronization? (Worried about memory being deallocated and reused, thus leading to other threads getting ahold of the address and seeing an old value there.)

Good question! This is hitting directly at the issue of mixing atomic and nonatomic accesses, and how exactly UnsafeAtomic values get passed to other threads.

I think it's okay to require that any mechanism that communicates the atomic handle to other threads will involve appropriate acquire-release fences that order the handle's nonatomic initialization before any atomic load. (After all, std::atomic's constructor is also nonatomic.)

@jrose

• It would be nice™ if a global initialized with create and never destroyed could be promoted to a static allocation by compiler magic.

Yes! But I think it's fine if this only ever gets implemented through non-copiable types. (Incidentally, there is a rudimentary level of compiler support for extracting the stable memory location of the storage backing a global variable (within the same module at least).)

@jrose

• UnsafeAtomicLazyReference.initialize(to:) feels like the wrong level of abstraction to me. What do you think about this instead? This is definitely the most common idiom I've seen for initializing a lazy singleton.

func getIfPresent() -> Instance? {
  return underlying.load()
}

// Filled out more in my UnsafeAtomicPointer prototype.
func getOrCreate(_ constructor: () -> Instance) -> Instance {
  if let value = getIfPresent() { return value }
  let newValue = constructor()
  let (exchanged, existingValue) = underlying.compareExchange(nil, newValue) // omitting refcounting logic for now
  return exchanged ? newValue : existingValue
}

I don't hate getOrCreate, but it does make it a lot less clear what atomicity means. It can also be surprising that the closure can get executed on multiple threads at once -- this isn't how e.g. dispatch_once works.

@jrose

• Relatedly, I think destroy should be named deallocate , to match UnsafeMutablePointer. It's only UnsafeAtomicLazyReference that does any additional work anyway. (You may have seen me put that into my API prototype.)

We could go with allocate/deallocate, but the pointer operations aren't a perfect match: create includes both allocation and initialization, and some cases of destroy also perform deinitialization. (UnsafeAtomicLazyReference in the initial batch)

[jrose (Jordan Rose)]

@lorentey

@jrose

I like the idea of a single generic struct + associated protocol, though I'd name it UnsafeAtomicPointer<Value> .

I feel quite strongly that Pointer is not a good suffix for these. UnsafeAtomicInt is no more a pointer than Unmanaged is, and reusing an existing name clashes with atomic pointer types.

I'd say UnsafeAtomicInt is more of a pointer than Unmanaged is. Unmanaged does not add an extra level of indirection on top of its base value; UnsafeAtomicInt does. (That is, Unmanaged<NSObject> has the same level of indirection as NSObject, but UnsafeAtomicInt does not have the same level of indirection as Int.)

That said, the name "Pointer" is more relevant if you have a generic wrapper anyway.

[lorentey (Karoy Lorentey)]

@ktoso

• It has happened to myself or peers multiple times that an atomic operation on the "default" ordering slipped through during review, what should have been an acquire/release etc. Things work and "look fine" but one always has to exert the special mental energy that "never use the default ordering", as on the level of data structures where one cares for those primitives it often is (and should be) a thoughtful decission which ordering to use. If it is sequential, then it is so for a reason, not because "I didn't think about orderings".

I agree that defaulting to sequential consistency will be undesirable in most production use of atomics. Sequential consistency seems to be the exception, not the rule -- so it should stick out in code review.

On the other hand, as a student of these things, I do deeply understand that concurrent programming on this level of abstraction is extraordinarily difficult to learn, and sequential consistency does provide an easier-to-understand model.

Question is: are the benefits that a default memory ordering will bring for beginners outweigh the drawbacks for scarred veterans? I believe this may require guidance from the Core Team.

[jrose (Jordan Rose)]

@lorentey

Question is: are the benefits that a default memory ordering will bring for beginners outweigh the drawbacks for scarred veterans? I believe this may require guidance from the Core Team.

One weird but possible option would be to put the defaulted versions in a separate module. import SimplifiedAtomics

(I'm somewhat convinced by now that having to use a linter to find a misused default argument for atomics isn't great. I did make the same mistake with @_implementationOnly, where it was too easy to miss one and so we had to add a warning for inconsistency.)

[lorentey (Karoy Lorentey)]

@ktoso

minor: The spelling of create surprised me a bit. In reviews I'm always told to stick to make... consistently, though grepping through some codebases now I guess create is also being used sometimes... No strong preference, just surprised me now.

ManagedBuffer.create is the closest analogue I could find in the stdlib to these create functions -- it's not a perfect match, but in both cases, the factory combines allocation and initialization.

In ManagedBuffer's case, this needed to be done through a static factory rather than an initializer because of complications with tail allocation; for UnsafeAtomic*, the factory is a stand-in for an eventual non-copiable type's initializer.

[Pierre_Habouzit]

One thing missing from the pitch and implementation, which I think is required, is a primitive for yielding the processor when implementing busy-wait loops. I think the examples provided are all suboptimal and actually need a PAUSE instruction at the end of each iteration. I'm by no means an expert, but I know it's considered best-practice and that at least one CPU vendor [1] advices for it.

This is not something we should expose. it is something that some low level OS primitives might want to use to implement higher level constructs, but basically unless you are the kernel and can disable preemption, in the context of a heterogenous priority environment, building anything around an atomic busy loop (spinlocks being the most obvious example) is incorrect for both performance and power.

I'm strongly opposed to this making it the standard library "just because", instead the library should provide better higher level construct that the OS has a chance to be able to optimize for you, and provide the adaptive spinning in a controlled way (only the OS can do that safely, the library can't).

[lorentey (Karoy Lorentey)]

@gribozavr

The proposed abstractions seem to allow atomic operations on non-atomic objects. Usually, the atomics abstraction combines the storage and the operations in one type, and ensures that users can't perform non-atomic accesses to the storage. The proposed abstractions don't guarantee that. I understand why this is designed like that -- some use cases would want to control precisely where their atomics are allocated and laid out in memory.

Yes, this is exactly right -- the technical possibility of mixing atomic/nonatomic access is an unfortunate side effect of the requirements and limitations we need to work with.

@gribozavr

How to fix: just specify that if a storage location is accessed with an atomic operations, all accesses except initialization must be atomic. We can relax it later.

This sounds good to me! We'll probably need to allow nonatomic deinitialization, too. (I think this is fine by the same reasoning nonatomic initialization is.)

@gribozavr

Names. I wanted to echo the comments above that UnsafeAtomicInt is not an int itself, but it is a pointer. Consider UnsafeMutablePointerToAtomicInt (similarly for other types), or, if we adopt a "universal" atomic pointer type, UnsafeMutablePointerToAtomic<Pointee> .

I find that UnsafeMutablePointerToAtomic<UnsafeMutablePointer<Foo>> would be a terribly long-winded and confusing way to spell an atomic pointer type.

How about AtomicHandle<UnsafeMutablePointer<Foo>>?

@gribozavr

UnsafeAtomicLazyReference.initialize(to:) is a "maybe-initialize" operation, unlike other existing operations in the standard library called "initialize". I think this difference in semantics should be reflected in the name, like initializeIfNil(to:) . Or should it even use the word "initialize"? The memory is already initialized to nil , this operation changes nil to non- nil -- we call that operation "store" or "set". So maybe setIfNil(to:) ? Or even ifNilSet(to:) , or ifNilStore(_:) ?

Good point. I like the ifNil suffix, but I'd prefer to go with storeIfNil -- it would be nicely symmetric with load.

(What do people think of calling it storeOnce?)

@gribozavr

Explore the feasibility of a "semi-universal" pointer-to-atomic type. I would very much like us to explore a design where the user must know about as few types as possible, and where atomics compose with existing standard library types, something along the lines of SwiftNIO, or the design that Jordan posted in this thread.

Stay tuned! I'm working on integrating feedback into a practical implementation for this.

@gribozavr

Nullability and mutability of UnsafeAtomicMutablePointer<Pointee> . I would prefer to see a more detailed argument why the pointee should be nullable. Similarly regarding mutability. If we can't make a convincing argument, then I think we should provide more variants of these types. It is important to note that adopting a generic type UnsafeMutablePointerToAtomic<Pointee> would allow us to avoid the question altogether and allow each user to specify whether they want a nullable/non-nullable pointer, mutable/non-mutable pointer.

The primary problem is that any generic atomic handle type will want to constrain its type parameter to some protocol. For example, assuming that we're happy to say that primitive atomics have the same memory layout as their corresponding value type:

protocol PrimitiveAtomic {
  static func atomicLoad(
    at address: UnsafeMutablePointer<Self>, 
    ordering: AtomicLoadOrdering
  ) -> Self
  ...
}

struct AtomicHandle<Value: PrimitiveAtomic> { 
  static func create(initialValue: Value)
  func destroy()
  init(at address: UnsafeMutablePointer<Value>)

  func load(ordering: AtomicLoadOrdering) -> Value {
    Value.atomicLoad(at: _address, ordering: ordering)
  }
  ...
}

extension Int: PrimitiveAtomic { ... }
extension UInt: PrimitiveAtomic { ... }
...
extension UInt8: PrimitiveAtomic { ... }

extension UnsafeMutablePointer: PrimitiveAtomic { ... }
extension Unmanaged: PrimitiveAtomic { ... }

This is all well and good so far. But optional pointers and optional unmanaged references pose a problem:

extension<Pointee> Optional: PrimitiveAtomic 
where Wrapped == UnsafeMutablePointer<Pointee> {
  ...
}
extension<Instance> Optional: PrimitiveAtomic
where Wrapped == Unmanaged<Instance> {
  ... 
}

We don't have generalized extensions, and even if we had implemented them, Optional wouldn't be able to conform to PrimitiveAtomic twice.

We could work around this by marking these types as "atomicable" through Optional:

protocol OptionalPrimitiveAtomic: PrimitiveAtomic { 
  static func atomicLoadOptional(
    at address: UnsafeMutablePointer<Self>, 
    ordering: AtomicLoadOrdering
  ) -> Self?
}
extension Unmanaged: OptionalPrimitiveAtomic { ... }
extension UnsafeMutablePointer: OptionalPrimitiveAtomic { ... }
extension Optional: PrimitiveAtomic where Wrapped: OptionalPrimitiveAtomic {...}

However, I don't believe the additional complexity of OptionalPrimitiveAtomic is worth it, especially when I consider that the most practical atomic pointer/reference types will likely be one-off implementations around double-wide atomics.

@gribozavr

Only providing wrapping semantics of arithmetic. I understand that there is a desire to provide direct access to the underlying CPU instructions that don't perform overflow checks. However, I think we should discuss providing both wrapping and trapping variants of atomic arithmetic, with trapping semantics being default.

This is fine! It's really the other way round -- the desire is to provide direct API for commonly available dedicated atomic instructions, not to preclude operations that aren't directly implemented in hardware. The requirements in the Motivation section merely state that if direct processor support is available, then it should be used, and that implementation artifacts (like switches over orderings) get eliminated.

@gribozavr

Explain in more detail what implementations are acceptable. You specified that a implementation must be lock-free. What about wait freedom? Regardless of what the answer is, the proposal should be explicit about the intent: whether a compare-exchange loop is an acceptable implementation is important to users.

Good point. The intent is that there is no requirement for wait-freedom. (If, say, loadThenBitwiseAnd isn't directly available for, say UInt64 values on some architecture, then the operation must still be implemented by a compare/exchange loop.) I'll clarify this.

@gribozavr

Explore which of the proposed operations are implementable on supported architectures. It would be great if the proposal confirmed if the proposed operations are implementable, and if not, listed the operations that will be missing on certain architectures.

(FWIW, I'm not aware of any type or operation that wouldn't be implementable on the architectures we currently support. The current implementation assumes that all fixed-width integer types are layout compatible with their atomic variant, which seems to hold true as well -- even for things like UInt64 on 32-bit platforms. We may need to restrict availability of double-wide atomics though, esp. if we support Linuxen running on older 64-bit CPUs without CMPXCHG16B.)

@gribozavr

Exposing atomics as a separate module. I would like the proposal to discuss the pros and cons of including atomics into the standard library module vs. exposing them as a separate module. Some thoughts from me: adding atomics to the standard library means that they would be imported into every Swift program, most of which are not going to use atomics. On the other hand, putting atomics into a separate module means that the standard library implementation won't be able to use them. It is almost as if we want a "submodule" that is imported on demand.

Yep, Atomics would be an excellent use case for submodules. (The stdlib will be fine though -- atomics aren't boundary types, so it can simply continue to maintain its own internal atomics implementation, with no measurable impact to its performance or (hopefully) code size. Stdlib engineers will suffer a little bit, but putting up with such things is practically part of the job description! )

[lorentey (Karoy Lorentey)]

Note: since we have create/destroy, there is no need to ever extract the pointer to the underlying memory location from an UnsafeAtomic* value, so I'm removing the address property.

(Code that uses init(at:) will be able to regenerate the pointer later through the same method it used to get the pointer at the time of the init(at:) call. (This may be necessary to correctly deinitialize the storage.))

[Chris_Lattner3 (Chris Lattner)]

@lorentey

Question is: are the benefits that a default memory ordering will bring for beginners outweigh the drawbacks for scarred veterans? I believe this may require guidance from the Core Team.

I think there is a strong and reasonable argument to be made that nothing about this API is really suitable for beginners. Optimizing for predictability seems like a higher priority than progressive disclosure of complexity. I was one of the people that suggested a default argument, and I retract that suggestion!

-Chris

[ktoso (Konrad 'ktoso' Malawski 🐟🏴‍☠️)]

This is not something we should expose. it is something that some low level OS primitives might want to use to implement higher level constructs, but basically unless you are the kernel and can disable preemption, in the context of a heterogenous priority environment, building anything around an atomic busy loop (spinlocks being the most obvious example) is incorrect for both performance and power.

Thanks for chiming in!

Yeah, I hear the argument against spin-loops in general and it's a solid one AFAICS. It's definitely not a thing that "has to" be included in an initial atomics pitch so seems like it'd be fine to skip those here until we have proven they'd really help. If we ever end up in a design / use case that'd want to use one, I'm happy to be then proven wrong and do something better

For reference: My "oh nice!" reaction on PAUSE was based on that pause was recently exposed in the JVM to much rejoice of people implementing queues and messaging systems ( JEP 285: Spin-Wait Hints ) – however that proposal and use case very Intel centric when one thinks about it.

I'd be (personally) happy to not have pause exposed in this initial pitch, and revisit it with proper discussion and use cases when the time comes.

@Chris_Lattner3

Optimizing for predictability seems like a higher priority than progressive disclosure of complexity. I was one of the people that suggested a default argument, and I retract that suggestion!

Very glad the argument resonates, and thanks for reconsidering the suggestion Predictability / readability are indeed paramount in those APIs

[drexin (Dario Rexin)]

I agree with @Pierre_Habouzit on PAUSE. Whether there is a more useful alternative available is heavily platform dependent. As @lorentey mentioned, ARM has WFE/SEV, where the thread at least gets paused until an event is signaled. On x86 there is MONITOR/MWAIT, that waits for a change on a specific memory location, but that is unfortunately only available at privilege level 0, so of no use here. Intel recently added UMONITOR/UMWAIT, but AFAIK that is only available on some Atom processors at the moment. With Excavator, AMD added MONITORX/MWAITX, which seems to be pretty much equivalent to UMONITOR/UMWAIT. Both take a timeout and wake up either when the watch triggered, or the timeout was exceeded.

Given that all of this is very platform dependent, I don't think it's feasible to expose this in the stdlib.

[lorentey (Karoy Lorentey)]

@lorentey

However, I don't believe the additional complexity of OptionalPrimitiveAtomic is worth it, especially when I consider that the most practical atomic pointer/reference types will likely be one-off implementations around double-wide atomics.

I think I'm starting to convince myself that it's worth it.

It would also be desirable to have a RawRepresentable extension to allow a limited set of custom atomic types:

protocol AtomicProtocol {
  associatedtype AtomicStorage = Self
  static func atomicLoad(at address: UMP<AtomicStorage>) -> Self
}

extension Int: AtomicProtocol {...}
extension UInt: AtomicProtocol {...}
...
extension UInt8: AtomicProtocol {...}

// ⚛︎ ⚛︎ ⚛︎
protocol NullableAtomicProtocol: AtomicProtocol {
  static func atomicLoadOptional(at address: UMP<AtomicStorage>) -> Self?
}
extension Optional: AtomicProtocol where Wrapped: NullableAtomicProtocol {
  typealias AtomicStorage = Wrapped.AtomicStorage
  static func atomicLoad(at address: UMP<AtomicStorage>) -> Self {
    RawValue.atomicLoadOptional(at: address)
  }
}
extension UnsafeMutablePointer: NullableAtomicProtocol {...}
extension Unmanaged: NullableAtomicProtocol {...}

// ⚛︎ ⚛︎ ⚛︎
protocol AtomicRepresentable: AtomicProtocol, RawRepresentable
  where AtomicStorage == RawValue {}
extension AtomicRepresentable {
  static func atomicLoad(at address: UMP<RawValue>) -> Self {
    Self(rawValue: RawValue.atomicLoad(at: address))!
  }
}

// ⚛︎ ⚛︎ ⚛︎
struct AtomicHandle<Value: AtomicProtocol> {
  init(at: UMP<Value.AtomicStorage>)
  static func create(initialValue: Value)
  func destroy()

  func load() -> Value {
    Value.atomicLoad(at: _address)
  }
}  

This way, AtomicHandle can support:

// Integer types:
let counter = AtomicHandle<Int>.create(initialValue: 42)
let cnt32 = AtomicHandle<UInt32>.create(initialValue: 23)

// Optional and non-optional pointers:
let ptr1 = AtomicHandle<UnsafeMutablePointer<Node>>.create(initialValue: ...)
let ptr2 = AtomicHandle<UnsafeMutablePointer<Node>?>.create(initialValue: nil)

// Optional and non-optional unmanaged references:
let ref1 = AtomicHandle<Unmanaged<Foo>>.create(initialValue: Unmanaged.passRetained(Foo()))
let ref2 = AtomicHandle<Unmanaged<Foo>?>.create(initialValue: nil)

// Custom atomicable types:
enum State: Int, AtomicRepresentable {
  case starting
  case running
  case stopped
}
let state = AtomicHandle<State>.create(initialValue: .starting)
...

It is my sad duty to report that supporting implicitly unwrapped optionals doesn't seem feasible without reintroducing dedicated type(s) for such things. (Which I'm not willing to do.)

This requires three more protocols than I originally planned on adding, but I really like where it's going.

(These protocols/generics would be like FixedWidthInteger in that unspecialized usages won't work very well at all.)

[dfunckt]

Hello Pierre, thanks for chiming in, I really appreciate your input.

This is not something we should expose. it is something that some low level OS primitives might want to use to implement higher level constructs, but basically unless you are the kernel and can disable preemption, in the context of a heterogenous priority environment, building anything around an atomic busy loop (spinlocks being the most obvious example) is incorrect for both performance and power.

I see your point and completely agree. What I have in mind however is not necessarily spinlocks (with os_unfair_lock, there really is no need for custom spinlocks) but any algorithm that includes a compareAndExchange operation which typically needs to be retried. Do you suggest retrying is bad in general and should be avoided? I don't think you do, and I also don't think it can be avoided altogether (otherwise we should just not even expose compareAndExchange).

I'm strongly opposed to this making it the standard library "just because", instead the library should provide better higher level construct that the OS has a chance to be able to optimize for you, and provide the adaptive spinning in a controlled way (only the OS can do that safely, the library can't).

Agreed. I personally don't care if we expose PAUSE specifically, my point is that it's important to expose something (anything really) that can hint to the OS that we're in a busy loop context (FWIW, Rust exposes a spin_loop_hint() top-level function) and, more importantly, that we shouldn't punt this for later. Otherwise, what we'll end up with is exactly what you want to prevent: badly performing and energy inefficient code that also adversely affects the rest of the system, because people will either have to write their own PAUSE/backoff/etc. strategy or just ignore it altogether and write naive busy-wait loops.