[Pitch #2] Safe Access to Contiguous Storage

Evolution Pitches
1

We are proposing a new abstraction for safe, direct access ot memory: Span. This is a substantial update to our earlier pitch, "Safe Access to Contiguous Storage", and is a companion to the Non-Escapable Types proposal.

Some of the changes in this version are:

  • The type's name is changed to Span. As a name, Span is short, pithy, precedented, and composable.

  • We add an untyped counterpart to Span: RawSpan, along with a motivating parser example and parsing utilities for RawSpan.

  • The Indexing model is simplified to use integer offsets.

  • Most of the Collection-like API is removed, and we use the slicing alternative adopted for UnsafeBufferPointer in SE-0437 Noncopyable Standard Library Primitives. This leaves more room to get forthcoming Sequence-like and Collection-like improvements right.

We have added a prototype of Span to a branch of the swift-collections package. This branch requires a recent Swift development toolchain.

Full proposal: Safe Access to Contiguous Storage (#2307)

Safe Access to Contiguous Storage

Introduction

We introduce Span<T>, an abstraction for container-agnostic access to contiguous memory. It will expand the expressivity of performant Swift code without comprimising on the memory safety properties we rely on: temporal safety, spatial safety, definite initialization and type safety.

In the C family of programming languages, memory can be shared with any function by using a pointer and (ideally) a length. This allows contiguous memory to be shared with a function that doesn't know the layout of a container being used by the caller. A heap-allocated array, contiguously-stored named fields or even a single stack-allocated instance can all be accessed through a C pointer. We aim to create a similar idiom in Swift, without compromising Swift's memory safety.

This proposal is related to two other features being proposed along with it: Nonescapable types (~Escapable) and Compile-time Lifetime Dependency Annotations, as well as related to the BufferView roadmap forum thread. This proposal is also related to the following proposals:

  • SE-0426 BitwiseCopyable
  • SE-0427 Noncopyable generics
  • SE-0377 borrowing and consuming parameter ownership modifiers
  • SE-0256 {Mutable}ContiguousCollection protocol (rejected, superseded by this proposal)

Motivation

Swift needs safe and performant types for local processing over values in contiguous memory. Consider for example a program using multiple libraries, including one for base64 decoding. The program would obtain encoded data from one or more of its dependencies, which could supply the data in the form of [UInt8], Foundation.Data or even String, among others. None of these types is necessarily more correct than another, but the base64 decoding library must pick an input format. It could declare its input parameter type to be some Sequence<UInt8>, but such a generic function significantly limits performance. This may force the library author to either declare its entry point as inlinable, or to implement an internal fast path using withContiguousStorageIfAvailable(), forcing them to use an unsafe type. The ideal interface would have a combination of the properties of both some Sequence<UInt8> and UnsafeBufferPointer<UInt8>.

The UnsafeBufferPointer passed to a withUnsafeXXX closure-style API, while performant, is unsafe in multiple ways:

  1. The pointer itself is unsafe and unmanaged
  2. subscript is only bounds-checked in debug builds of client code
  3. It might escape the duration of the closure

Even if the body of the withUnsafeXXX call does not escape the pointer, other functions called inside the closure have to be written in terms of unsafe pointers. This requires programmer vigilance across a project and potentially spreads the use of unsafe types, even when it could have been written in terms of safe constructs.

We want to take advantage of the features of non-escapable types to replace some closure-taking API with simple properties, resulting in more composable code:

let array = Array("Hello\0".utf8)

// Old
array.withUnsafeBufferPointer {
  // use `$0` here for direct memory access
}

// New
let span: Span<UInt8> = array.storage
// use `span` in the same scope as `array` for direct memory access

Proposed solution

Span will allow sharing the contiguous internal representation of a type, by providing access to a borrowed view of an interval of contiguous memory. A view does not copy the underlying data: it instead relies on a guarantee that the original container cannot be modified or destroyed during the lifetime of the view. Span's lifetime is statically enforced as a lifetime dependency to a binding of the type vending it, preventing its escape from the scope where it is valid for use. This guarantee preserves temporal safety. Span also performs bounds-checking on every access to preserve spatial safety. Additionally Span always represents initialized memory, preserving the definite initialization guarantee.

By relying on borrowing, Span can provide simultaneous access to a non-copyable container, and can help avoid unwanted copies of copyable containers. Note that Span is not a replacement for a copyable container with owned storage; see the future directions for more details (Resizable, contiguously-stored, untyped collection in the standard library)

Span is the currency type for local processing over values in contiguous memory. It is the replacement for any API currently using Array, UnsafeBufferPointer, Foundation.Data, etc., that does not need to escape the value.

RawSpan

RawSpan allows sharing the contiguous internal representation for values which may be heterogenously-typed, such as in decoders. Since it is a fully concrete type, it can achieve better performance in debug builds of client code as well as a more straight-forwards understanding of performance for library code.

Span<some BitwiseCopyable> can always be converted to RawSpan, using a conditionally-available property or a constructor.

Please see the full proposal for the Detailed Design, Alternatives Considered and Future Directions sections.

47 Likes
2

I think this could be phrased better.

Of course, please correct me if I'm misunderstanding, but I believe what you're trying to say is that an unspecialised generic function is not as efficient as a specialised one, or one which operates on a concrete type (because unspecialised functions still have witness table indirection that hasn't been optimised out). If that is what was meant, it's worth noting that the internal fast path does not need to use an unsafe type. For instance, this would be a legitimate (albeit somewhat limited) implementation of a fast path:

public func parse(_ input: some Sequence<UInt8>) {
  // Downcast to common concrete types
  // to encourage specialisations for them.
  if let arrayInput = input as? Array<UInt8> {
    return _parseImpl(arrayInput)
  } else if let dataInput = input as? Data {
    return _parseImpl(dataInput)
  }
  return _parseImpl(input)
}

internal func _parseImpl(_ input: some Sequence<UInt8>) {
  // ...
}

My understanding is that this is approximately how the @_specialize attribute works.

But when I read the paragraph I quoted, it comes across like you're saying generics are just inherently slow, or that we're actually looking for the performance of unsafe buffer pointers. This same paragraph was in the previous draft and when I read it months ago, it came across the same way.

That said, I think the overall point you're making is sound: that there exists a very large class of collections which have contiguous storage, and when generic algorithms are compiled, we want them to be treated as equivalent at a very low level (controlling specialisation behaviour is a very low level thing that doesn't often bubble up in to the high level language semantics IMO). I've been doing this in my libraries for years (using wCSIA and a bounds-checked buffer pointer rather than as? casts, but conceptually serving the same purpose), but for me the motivation hasn't been performance - all the code is still generic, and it's @inlinable so it could be specialised - instead, the motivation is code size.

For a parser distributed as a Swift package, I don't want the final application binary to have separate copies of the parsing logic if the input data happens to be a Array<UInt8>, Data, UnsafeBufferPointer<UInt8> (e.g. a C string), etc - I want those to collapse to a single specialisation because the final binary will have to lug those around.

More broadly, while I support the overall direction, I am very concerned about the lack of a Collection interface. I've shown how I use this pattern currently (with generic code), and to me it is very important that this remains something of a low-level implementation detail that does not leak in to interfaces unless contiguous storage specifically is required, and that I can continue to write generic code which works with both Span-providing collections and non-contiguous (or non-updated) collections.

I understand that we still need to work out whether or how Collection can be adapted to non-copyable types. I believe that work should be a prerequisite for actually adding this type to the standard library.

1 Like
3

Also, I believe all of the typed operations on RawSpan are unsafe. For instance:

  • func view<T: BitwiseCopyable>(as: T.Type) -> Span<T> is not safe.

  • func load<T>(fromByteOffset offset: Int = 0, as: T.Type) -> T

  • func loadUnaligned<T: BitwiseCopyable>(fromByteOffset offset: Int = 0, as: T.Type) -> T

A programmer error could use these functions to construct an enum with an invalid bit-pattern (doesn't match any defined case), and I don't believe the language makes any guarantees that such values would be handled consistently. Your code might go down all kinds of bizarre and non-sensical execution paths and it could even change between compiler versions (in other words, UB). The load operation itself would be fine; it's the result which could be problematic.

It's good to offer them, but I think they should have unsafe in the name. We are relying on the programmer to manually reason about the type-safety of what they're doing.

3 Likes
4

view(as:) and loadUnaligned(as:) are both limited to BitwiseCopyable types and, as such, it is possible for them to produce invalid values (that is, values that an initializer would never produce). I believe that possibility is marked by the particle "raw" in the type name, just like UnsafeRawPointer. There are different types of unsafety and I believe it is useful to use different words for each when possible. (I noted that there is a stern warning only for the versions that don't check bounds – this needs a better balance.) In the case of load<T>(as:), there is no constraint on the type, and that's significantly more unsafe. We could add a BitwiseCopyable constraint on this as well, thereby limiting the fully-unconstrained load operation to being used via UnsafePointer in a withUnsafeBytes() closure.

2 Likes
5

These are the first non-escapable types to be pitched, but we do not yet know in which order things will land in the standard library. But we need some concrete things to build upon.

Span, ~Escapable types and ~Copyable types need to be prototyped and used so that the generalized Sequence-like and Collection-like don't get designed in a vacuum. Pitching and prototyping the feature also allows the adventurous like you to try things out and point out mistakes and omissions!

7 Likes
6

I don't think "raw" quite communicates the severity of the problem - we use "raw" for lots of things that are perfectly safe (the one developers are most likely to be familiar with is RawRepresentable and its rawValue property).

And yes, there are many ways operations can be unsafe - but the way we have used "unsafe" in Swift has had a consistent meaning; that being:

  1. The operation has certain preconditions.

  2. Those preconditions are not automatically enforced (at compile-time or run-time) and require manual reasoning by the programmer.

  3. Violating the operation's preconditions may cause undefined behaviour.

It has never been limited to issues of lifetimes or bounds-checking.

In this case, I think the operation absolutely fits the bill for being labelled as unsafe. It is essentially the operation which we currently call unsafeBitCast, but being exposed on a type whose entire reason for being is that it is supposedly safe.

I don't think BitwiseCopyable has any bearing on this. As I described in a recent thread, I don't think it actually provides safety. The other operations could even drop the BitwiseCopyable constraint and I don't think they would be any less safe.

Here's an example of this happening. We switch over an enum with 4 cases, which the compiler optimises to a table lookup, assuming it will only ever see those 4 values. By constructing an invalid enum case, we deference past the end of the table. When executing on Godbolt, I find that if the function containing the switch is @inline(never) we just read a value from random memory, and if it isn't, it appears to crash (but I don't believe that is guaranteed).

It troubles me that this could be done without any notice at the call site, on a type which claims to be safe. In real code you likely wouldn't see that the loaded value clearly does not correspond to an enum case.

For sure - I do appreciate the progress that is being made, and it is exciting. It's particularly nice that there is a working prototype to experiment with.

What I'm saying is that I hope this doesn't progress all the way to a full review and acceptance before we have a clearer picture of what non-copyable collection interfaces will look like. As far as I can tell, there have been no public discussions on that topic, while this is already the second pitch for Span.

In other words, I'm saying that in my opinion, there is a preferred order in which things land in the standard library.

5 Likes
7

We need an AnyBitPattern protocol to constrain these kinds of things to.

8

I'm not sure there would be a way to enforce the meaning of AnyBitPattern; maybe what's needed is to limit it to a small number of standard library types: the floating point types and the integer types.

9

We have at least a few critical motivations for Span

  • guaranteed, predictable performance (including debug builds)
  • code size
  • supporting library evolution

We need to do everything we can to limit reliance on @inlinable.

7 Likes
10

I think a crucial question is whether doing that is considered undefined behavior. What semantics does Swift assign to enum instances that do not correspond to any of the enum cases? Do we assign predictable, consistent semantics to their behavior, or not?

If such instances wreak havoc (for example, by violating the compiler's assumptions on switch statements being exhaustive), then we have an issue.

6 Likes
11

It is indeed havoc-wreaking undefined behavior for enums (or even just Bool) to be given an invalid representation.

8 Likes
12

To throw it out there: ByteDecodable?

13

There's no way to enforce the semantics of any protocol. If you think it's especially hazardous we could have the conformance automatically inferred with an opt-out, but, honestly, I think enough types have invariants that it should just be completely opt-in.

14

For type layout traits, it is possible for the compiler to reason about and enforce them (as it does for BitwiseCopyable). It would be theoretically possible to reason about types that are both bitwise-copyable and always valid for any bit pattern since they are transitively made up of IntNN, FloatNN, etc. (Whether it's important enough to do so, versus letting the developer do what they need to, is a separable question.)

4 Likes
15

We need to take one step at a time. These are not baby steps -- they are huge leaps, and each of them needs focused attention.

New container patterns are certainly coming, and they will heavily build on non-escapable types. Span will play a particularly prominent role in them. We cannot pitch them without having introduced these concepts first.

I fully expect that Span will ship alongside the first wave of new container protocols, as a unit.

It is crucial to note that "Span-providing" and "non-contiguous" aren't mutually exclusive concepts. We intend Span to be the basic unit of iteration of all borrowing sequences.

At long last, Span gives us an opportunity for data structures to directly expose their contents in their actual native form: as piecewise contiguous series of storage buffers.

A very significant limitation with the classic Sequence is that it insists on iterating over elements one by one. This can induce slowdowns up to a factor of 100x or more for interfaces that take generic sequences. This provides a horrible excuse for API designers to avoid using generics, or to spend effort on trying to manually specialize common cases (like you describe). Sequence itself attempts to mitigate this with a ragtag assortment of one-off hooks like _copyToContiguousArray, _copyContents or _customContainsEquatableElement. The reason these remained forever stuck in the limbo of underscores is that they are hyperfocused on an overly narrow set of cases (and to be honest, they don't do a particularly great job at those, either). The performance issues they patched were important enough that removing them wasn't ever an option, but they are also not general enough solutions to consider making official.

Span gives us a safe way to iterate over arbitrary contiguous chunks of storage instead, promising to generally resolve this critical performance bottleneck, especially in unspecialized generic code. For a taste, imagine if IteratorProtocol was defined like this:

protocol IteratorProtocol<Element> {
  associatedtype Element
  mutating func nextChunk(maximumCount: Int) -> depends(self) Span<Element>
}

This introduces a two-tiered iteration process: we iterate over native storage chunks, separately iterating over the elements of each. Crucially, the lower layer is operating over Span, a tiny, transparent type that can always be specialized -- allowing iteration on that level to proceed at full speed, entirely avoiding dynamic dispatch.

9 Likes
16

Bounds checking

Span and RawSpan have validateBounds methods. UTF8Span has equivalent boundsCheck methods. Can these share the same name, or be moved to a Range extension?

Span and RawSpan also have assertValidity methods, which are currently implemented with a precondition. The caller's file and line aren't given.

6 Likes
17

Good points!

My beef with the name validateBounds is that (1) despite its promise, it is actually validating an index, not the bounds, and (2) it is a predicate, but it doesn't read like one. The latter issue also applies to UTF8Span.boundsCheck.

FWIW, in swift-collections, I have recently found a need to introduce similar functionality, and I ended up calling the predicate isValid(_: Index). This would not work directly for Spans, as they use Int as their index -- but isValidIndex(_: Int) might be an option to consider. The sibling method for validating a range of indices may perhaps be called isValidSubrange(_: Range<Int>), as that is the term we've established for such ranges.

Note: defining these APIs would set a clear pattern for other types to emulate, but it would probably not be a good idea to make them general requirements of any protocol. Index validation is tricky to do efficiently; it is generally best to do it as an integral part of actual accesses, not as a standalone operation. Very often, the outcome of index validation is not just a yes/no result, but also some direct reference to a part of the underlying container representation that can be directly used to access the addressed item -- a pure isValidIndex predicate would discard all this work, only to redo it from scratch when the validated index actually gets used.

(Alternatively, we can of course choose not to provide these members at all -- the swift-collections case wasn't simply about avoiding having to spell out a trivial range check.)

I'd personally prefer to avoid spending API surface on variants that simply assert on the validity of an index -- it raises too many complications:

  • Is the client happy to use precondition or would they prefer assert?
  • Inability to customize the runtime error message that the function emits on failure.
  • Having to pollute the API signature with #file/#line arguments.

It seems okay to me to let clients invoke precondition themselves if that is what they want to do. The swift-collection example also defines func validate(_: Index), and it suggests validateIndex/validateSubrange for naming. But I regret adding Rope.validate; I think it would work better as an internal helper rather than public API. (Luckily, the module that defines it isn't source stable yet.)

4 Likes
18

A little offtopic:
Type Inout<T: ~Copyable>: ~Copyable, ~Escapable uses subscript() -> T for dereferencing.
It seems to me that we need a more user-friendly syntax for dereferencing instead of []

19

I have a few questions:

  • In what cases do we expect people to use the unsafe pointer initializers? Presumably, only when they are working with unsafe pointers to begin with, like if they got an unsafe pointer from somebody else, or if they are implementing their own collections on top of unsafe pointers? And everyone else already using (for instance) Array can use Array.storage?
  • What are the Law of Exclusivity implications of using spans? Does borrowing prevent mutations to the owner binding? (Not fully up-to-date on this)
  • Is it correct that the parser example is the motivation for RawSpan, but that parsing utilities are not part of this proposal?

I also wanted to say that I agree with @Karl that BitwiseCopyable is not a strong-enough constraint to make view, load and loadUnaligned type-safe because BitwiseCopyable types can have bit patterns that that don't correspond to any value, and whose subsequent use would be undefined behavior. I also agree that "raw" isn't a strong-enough marker to indicate a possibly-havoc-wreaking operation: Raw is also used in "RawRepresentable", and it's not a naughty word there.

Included types include enums (as the case was made here) but also unsafe pointers. There's a few of us who've been privately asking for a stronger constraint (specifying that all bit patterns have a well-defined interpretation) that would resolve this issue. To steal the proposed name, "AnyBitPattern" could match integer types, floating-point types, and aggregates that only contain AnyBitPattern values (including aggregates of aggregates, etc). This category importantly includes many RawRepresentable structures, and on the blessed day that Swift gets fixed-size arrays, it would include those too.

Still, there's a migration path to eventually constrain view and friends more (deprecate BitwiseCopyable version, create AnyBitPattern version, create unsafeView/unsafeLoad/etc versions for when you do need to read out something unverifiable; then let people sort out their deprecation warnings), and on balance Span solves urgent problems, so I wouldn't necessarily hold it up for it. I still think that we need to have heightened awareness of these things to avoid accidentally baking unsafe interfaces into primitives that are intended to be safe almost all around. My biggest complaint with UnsafeBufferPointer is that it's easy to over-estimate its safety. It would be best to not create more "safe" primitives whose safety is over-estimated.

6 Likes
20

Yeah, the memory referenced by a Span is borrowed and can't be inout-ed while the span is alive.

5 Likes