[Second Review] SE-0410: Atomics

Evolution Proposal Reviews
62

I can see the argument that an atomic type is, in some sense, a fundamentally different kind of type from a struct or a class. It is not a reference type: first off, it is of great practical important to clients that it is stored inline and does not require an additional allocation; additionally, while its presence in memory is important, it can also be relocated just like any other non-copyable type; also it really could be meaningfully copyable, we just want that to be more explicit (for good reason). But at the same time, it doesn't follow the most important rule of a value type, which is that mutations of / exclusive access to component values always requires exclusive access to the containing value. (This is perhaps clearer with Locked<T> types, which generally have the same properties as Atomic<T>.)

This ability to do mutations of the component value without exclusive access to the containing value is what makes atomic types weird, but it's also their whole reason to exist. Swift's exclusivity rules are designed to allow normal accesses to value components to be safe and race-free. That logic works quite well in reverse: once you're enforcing the exclusivity rules, there's no point in using atomic accesses to value components, because there can't possibly be a racing thread anyway. Doing atomic operations on memory you have exclusive access to is just wasting resources in the memory subsystem. Atomic operations exist so that you can achieve some things safely without exclusive access to that memory.

So we've got these types that in some sense are fundamentally different from other types. It's fair to ask whether they ought to look different, either in declaration or in use. The declaration side is out of scope for this review: Atomic<T> is a single standard library type, and the LSG has agreed that we'll just treat it as a magical one for now. So in this proposal, we're just talking about how it feels to use an atomic type, e.g. to declare an atomic variable. In the future, we'll probably have some way to declare other atomic-like types which (as the name suggests) will probably behave just like Atomic<T>. The rules we pick here will probably be the rules for those other types, too.

Unfortunately, if we want to use special-case syntax for uses of atomic types, I think we have an unavoidable conflict here with the existing syntax for ownership.

Ownership in Swift is all about establishing either exclusive or shared access to memory. As Joe mentioned upthread, the most important reason, by far, that we might need exclusive access to memory is that it's ordinary memory and we want to mutate it. As a result, all of the keywords we've chosen for exclusive ownership are associated with mutation: mutating, inout, var, etc.

Notably, we use those mutation-oriented keywords even in generic code. Generic code can't directly mutate the value components of opaque values, because the basic rules for direct, concrete accesses depend on knowing what kind of value you're working with. Instead, generic code just enforces exclusive and non-exclusive accesses for abstract operations on opaque values, with no idea about whether those operations actually do any mutation.

For example, suppose you have the type struct Point2i { var x, y: Int }. If you assign p.y = 5 on a concrete variable of this type, Swift knows that you're assigning into a stored struct property, and it knows that's a mutation, and it knows specifically how to best enforce exclusivity for p for that operation. If you're in generic code, and there's a type parameter T that conforms to protocol PointLike { var x, y: Int { get set } }, the statement t.y = 5 is just invoking some abstract operation which may or may not do any mutation, and all we know about it is that it happens to require exclusive access to t. Nonetheless, it's reasonable to still talk about it as if it does mutation, as well as to use the same keywords as we do for operations that definitely do mutation.

Of course, Swift doesn't yet have generics over non-copyable types like Atomic<T>. We could choose to use rules that accommodate the possibility of non-copyable type parameters being atomic types, e.g. by using different, less mutation-centric keywords in such code. However, I think that would be a poor choice. It'd be even worse to put atomic types into an even-more-refined generic subset, making them not just normal non-copyable types, just so we can enforce the use of these special keywords. In both cases, we're just creating complexity to solve a non-problem, because the generic code doesn't need to care whether it's working with an atomic type. The basic concept I laid out above is good enough: the code is just forwarding opaque values around to abstract operations that it doesn't understand, locally enforcing exclusivity according to the declared requirements of the operations. It doesn't actually matter to map whether it's passing a borrowed Int to a function that'll print it or a borrowed Atomic<Int> to a function that'll do atomic operations there.

So if we want to impose different spellings on uses of atomic types, we need to understand that we're necessarily engaged in a line-drawing exercise. Someone who wants to understand how atomic types work under generics will have to internalize what Joe is saying about how normal mutation requires exclusive access but atomic mutation does not. The question is just whether it's a good idea to use special-case spellings in code that's concretely working with atomic types. The advantage of doing so is that it will probably better fit most people's intuition about mutability in concrete atomic code ā€” and it's fair to guess that the preponderance of code working with atomics will be working with Atomic<T> concretely. The disadvantage is that it adds complexity and might undermine people's ability to make that broader conceptual leap about ownership.

13 Likes
63

Since I havenā€™t seen this mentioned yet: Iā€™m already so used to the fact that Windows/Intel use ā€œdouble-wordā€ for int32 and ā€œquad-wordā€ for int64 that I would honestly expect a type named DoubleWord to be a typealias to Int32 or UInt32, like WinAPIā€™s DWORD is.

3 Likes
64

"Word" in Swift consistently refers to a pointer-size value (cf. BinaryInteger.Words), so that ship already sailed. That said, WordPair is a better name for this type than DoubleWord, since in typical atomic usage it represents a pair of values at least as often as it represents a single double-wide integer value.

6 Likes
65

"Sharing" can happen even within a single thread through aliasing and reentrancy, for instance if you form a closure over a local variable, pass that closure off, then call some function which invokes the closure while you're also still using the local variable. This kind of single-threaded shared access is valid for a let of any type, but you're right that the validity of that sharing only covers the extent of the value itself (which for a class type, is only the pointer to the object instance but not the object itself; for a struct that contains pointers to unsafe-to-share buffers, only those pointers but not the memory they reference, and so on). Sendable expresses an additional guarantee that the contents of the value also don't allow you to reach any unsafe-to-share state, so both the value itself and anything it points to are safe to share. The full-blown Atomic type here is always both; in the fullness of time it could also be interesting to have a SingleThreadAtomic that's not Sendable but which still guarantees non-torn loads and stores to the storage, for safety relative to signal handlers, interrupts, and other same-thread interruptions. In the model being proposed, values of that type would also generally be used as lets.

5 Likes
66

I think it would be easier to justify them looking the same in use if they look different in declaration. We are already used to being able to mutate a let variable of a class, because it has reference semantics. If atomic types have 'inline reference' semantics, I think this is easier to explain. Using a new type of declaration would also fit with class/actor/struct which all have different use semantics (reference, isolation, value).

3 Likes
67

Who besides the standard library would implement such a type, though? Rust has core::cell::Cell<T>, which is a generalization of this concept. User-defined types can use Cell<T>, but is it even possible to implement Cell<T> outside of core?

68

(cell would make quite a nice keyword for the general concept of a type with inline storage but otherwise more like reference semantics)

69

Is cell T { var foo: Int } really so much of an improvement over struct T { let foo: Cell<Int> } that it justifies a new kind of type declaration? The only benefit I can think of is that you could assign a meaning to let in a cell.

I donā€™t think itā€™s worth blocking atomics on solving the general cell design problem.

2 Likes
70

To be clear, Iā€™m not suggesting that the proposal be blocked on this. Assuming that the surface syntax for the atomic types could be changed retroactively, this could be a Future Direction that helps concerns over var vs let at the use site.

71

The properties of this "cell" also carry over into any struct/enum types that contain it as a member. So if we do introduce a new kind of declaration for the primitive cell, then Atomic could still be implemented as:

private cell AtomicCell<T> { ... }

public struct Atomic<T>: ~Copyable { private let storage: AtomicCell<T>; ... }

so it "could be added later" without changing the outward interface of Atomic as proposed.

3 Likes
72

You just reminded me about something: the Atomic<Value: AtomicValue> type here is only conditionally Sendable:

The Atomic type is Sendable where Value: Sendable.

This is kind of weird - surely an atomic is always Sendable? But this constraint means things like Atomic<UnsafePointer<Int>> would not be Sendable, since pointers themselves are not.

Can we instead require the AtomicValue.AtomicRepresentation associated type to be Sendable, so that Atomic<T> becomes unconditionally Sendable?

73

An Atomic containing a non-sendable type can be used to transfer references to non-sendable data across threads, since thread 1 could store (using your example) a non-sendable pointer to the atomic, and thread 2 can load it. So, like a type containing pointers, the language rules around concurrency can't guarantee the safety of sharing the data, and it becomes the containing type's responsibility to use the pointer correctly and mark itself @unchecked Sendable if it does.

4 Likes
74

I think this is an important point. Atomic inherently has to operate outside of the confines of Sendable, because atomics is what other types typically need to use to implement their @unchecked Sendable conformances. This is the primary use case for atomics, and whether or not struct Atomic is Sendable is not at all relevant in this context.

I consider the conditional Sendable conformance on struct Atomic to be purely a convenience feature for the simplest cases, where we just want to treat an atomic value as a self-contained unit, like this silly example of a read access counter:

struct AccessCounted<Value: Sendable>
  : ~Copyable, Sendable 
{
  let _value: Value
  let _readCounter: Atomic<Int> = .init(0)

  init(_ value: Value) { _value = value }

  var value: Value {
    _readCounter.add(1, ordering: .relaxed)
    return _value
  }
}

Allowing Atomic<Int> to be Sendable allows us to rely on built-in Sendable checking in these trivial cases, without having to deal with the (sometimes incredibly subtle) requirements of @unchecked Sendable. AccessCounted can safely become Sendable without doing any extra work.

[[Whether this is truly safe depends on one's opinions on what sort of race conditions Sendable is supposed to protect against. For example, this variant of the value getter would sometimes miscount overlapping accesses:

  var value: Value {
    let c = _readCounter.load(ordering: .relaxed)
    _readCounter.store(c + 1, ordering: .relaxed)
    return _value
  }

This code has a race condition by most definitions of this term. However, it never engages in undefined behavior: while it can produce incorrect results, it still operates entirely within Swift's abstract memory model. Sendable checking does not protect against logic bugs like this -- atomic operations can be tricky to use correctly, even in the "simplest" use cases.]]

8 Likes
75

I maintain my previous position regarding whether or not it fits within the language model and strongly suggest that the name of the exposed struct should be UnsafeAtomic

76

The atomic type we're proposing is not unsafe like the UnsafeAtomic in the swift-atomics package. The UnsafeAtomic there requires the user to manually manage their own memory either by calling its .create(_:) method and manually .destroy()ing it once you're done, or by manually managing the pointer passed in init(at:). Atomic does not require the user to worry about the memory management of the underlying contained value because Atomic will automatically clean it up.

5 Likes
77

But what truly unsafe behavior does this create, according to Swift's memory model? Concurrency can introduce race conditions and we don't consider that unsafe unless it breaks memory guarantees - logic errors are not the responsibility of the language.

1 Like
78

They are not, but when the purpose of the exposed structure is to provide concurrent-safe access, that line gets really blurry, really fast. Atomics, at best, work concurrently with the provided memory guarantees.

79

@lorentey brought up an interesting question recently of whether Atomic should be Sendable by default at all. Its sendability is already conditional on the type contained in the atomic, as discussed above, but even when passing around sendable values, atomics require the developer use the API correctly in order to get the desired behavior. It's a reasonable argument that working with Sendable types should mean you're in the "fearless concurrency", safe subset of the language, and atomics don't meet that bar, and any types that use atomics as part of their implementation should instead have to explicitly mark themselves as @unchecked Sendable to indicate that their own soundness is not statically guaranteed by the language.

12 Likes
80

Yes, this is the consequence of the Sendable race condition I found above:

struct AccessCounted<Value: Sendable>
  : ~Copyable, Sendable 
{
  let _value: Value
  let _readCounter: Atomic<Int> = .init(0)

  init(_ value: Value) { _value = value }

  var value: Value {
    let c = _readCounter.load(ordering: .relaxed)
    _readCounter.store(c + 1, ordering: .relaxed)
    return _value
  }
}

We can either choose to allow such faults to creep into Swift code without notice, or we can remove the conditional Sendable conformance from struct Atomic, and force people to declare such types as @unchecked Sendable, explicitly admitting that they are opting out of static safety. On reflection, this second option seems preferable to me. (Edit: but it would not really solve the core issue.)

People who need trivial atomic counters can simply construct them by rolling their own wrapper type that avoids bad operations:

struct AtomicCounter: ~Copyable, @unchecked Sendable {
  let _value: Atomic<Int>

  init(_ initialValue: Int = 0) {
    self._value = .init(initialValue)
  }

  borrowing func increment() -> (oldValue: Int, newValue: Int) {
    _value.wrappingAdd(1, ordering: .relaxed)
  }

  borrowing func load() -> Int {
    _value.load(ordering: .relaxed)
  }
}

Note though that this still doesn't guarantee that no race conditions will exist. Frustratingly, concurrency inherently messes up composability, making it difficult to guarantee the correctness of whole programs, even if the building blocks they're using are known to be correct.

The above atomic counter looks correct to me, and it feels like it ought to be okay to declare it Sendable. However, it still is subject to higher-order race conditions like the atomicity violation we saw in AccessCounted. For example, if someone wants to build an atomic counter that is restricted to even numbers, this broken implementation will still be allowed, without having to declare @unchecked Sendable:

struct AtomicCountBy2: ~Copyable, Sendable {
  let _value: AtomicCounter
  init() { _value = .init(0) }

  borrowing func increment() -> (oldValue: Int, newValue: Int) {
    let old = _value.increment().oldValue
    let new = _value.increment().newValue
    return (old, new)
  }  
}

Actors, locks etc are also subject to such atomicity issues.

2 Likes
81

Iā€™d push back against this, there is no use for an atomic that isnā€™t sent. Making them not Sendable means I canā€™t capture an atomic in two Tasks; I have to write my own type first. (Even if itā€™s a local type.)

6 Likes