Contiguous Collection Protocols

Introduce Contiguous Collection Protocols

Introduction

This proposal introduces two new protocols, ContiguousCollection, and a mutable version MutableContiguousCollection. These protocols will allow generic code to make use of the withUnsafe{Mutable}BufferPointer idiom, as well as provide fast paths in the standard library for adopting types.

Motivation

Almost every feature of Array is made available via one of the protocols in the standard library, and so most code written against Array can be rewritten generically as an extension of one or more protocols.

The exceptions to this are the operations withUnsafeBufferPointer and withUnsafeMutableBufferPointer, which are only available on the concrete types. Given the usefulness of these methods, they should also be made available generically.

Proposed solution

Introduce two new protocols, with requirements representing the with-unsafe capabilities of Array & co:

/// A collection that supports access to its underlying contiguous storage.
public protocol ContiguousCollection: Collection
where SubSequence: ContiguousCollection {
  /// Calls a closure with a pointer to the array's contiguous storage.
  func withUnsafeBufferPointer<R>(
    _ body: (UnsafeBufferPointer<Element>) throws -> R
  ) rethrows -> R
}

/// A collection that supports mutable access to its underlying contiguous
/// storage.
public protocol MutableContiguousCollection: ContiguousCollection, MutableCollection
where SubSequence: MutableContiguousCollection {
  /// Calls the given closure with a pointer to the array's mutable contiguous
  /// storage.
  mutating func withUnsafeMutableBufferPointer<R>(
    _ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R
  ) rethrows -> R
}

Conformances will be added for the following types:

  • Array, ArraySlice and ContiguousArray will conform to MutableContiguousCollection
  • UnsafeBufferPointer will conform to ContiguousCollection
  • UnsafeMutableBufferPointer will conform to MutableContiguousCollection
  • Slice will conditionally conform:
    • to ContiguousCollection where Base: ContiguousCollection
    • to MutableContiguousCollection where Base: MutableContiguousCollection

In addition, the following customization point should be added to MutableCollection, with a default implementation when the collection is mutably contiguously stored:

protocol MutableCollection {
  /// Call `body(p)`, where `p` is a pointer to the collection's
  /// mutable contiguous storage.  If no such storage exists, it is
  /// first created.  If the collection does not support an internal
  /// representation in a form of mutable contiguous storage, `body` is not
  /// called and `nil` is returned.
  public mutating func withUnsafeMutableBufferPointerIfSupported<R>(
    _ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R
  ) rethrows -> R?
}

This customization point already exists with an underscore in the standard library (it just returns nil by default), and should be exposed to general users, with a default implementation when the collection conforms to MutableContiguousCollection.

Use of this entry point can provide significant speedups in some algorithms, e.g. our current sort which needs to move elements of a collection back and forth between some storage.

Source compatibility

These are additive changes and do not affect source compatibility.

Effect on ABI stability

These are additive changes and do not affect ABI stability.

Alternatives considered

Some collections are not fully contiguous, but instead consist of multiple contiguous regions (for example, a ring buffer is one or two separate contiguous regions). A protocol that exposed a collection of contiguous regions could be implemented on top of this protocol.

18 Likes

Note, this proposal includes some methods that are only useful in a generic context. For example, withUnsafeMutableBufferPointerIfSupported is pointless if you know you have an Array. Similarly, withUnsafeBufferPointer is pointless if you already have one.

These are probably more examples of the discussion we've had elsewhere of being able to fine-tune autocomplete suggestions and documentation depending on context, but should probably be discussed separately to this pitch itself.

1 Like

My understanding is that Array doesn't actually guarantee storage in contiguous memory (because of bridging, etc) and this is (part of?) the reason ContiguousArray exists. Further, my understanding is that an array will copy its elements to contiguous storage if necessary when providing a buffer pointer.

Despite this, the naming and documentation of this protocol strongly implies that internal storage is guaranteed to be contiguous (i.e. "access to its underlying contiguous storage"). This is not a trivial dissonance - it is a difference of guaranteed constant time access to the storage vs a potentially O(N) time and space cost to access the contiguous storage. IMO we should be explicitly clear in both naming and documentation what the intended semantics are.

Unless I am mistaken about the behavior of Array, I think if it is going to conform these protocols they should be renamed to something along the lines of ContiguouslyAccessibleCollection. The semantics could be that internal contiguous storage is possible (but not guaranteed). On the other hand, if the semantics should really be guaranteed constant time access to an internal buffer then Array should not conform.

2 Likes

As a side node this reminds me terrifyingly of NSArray - NSMutableArray, NSString - NSMutableString, NSData - NSMutableData… and the rest of the schlepp of this kind we have inherited from Objective-C Foundation. o_O
I thought we got rid of this marking mutability by the type name…?

2 Likes

This looks good. A few questions:

  1. Will _copyToContiguousArray and the like benefit from this? I found overriding this can make a big difference to custom data structures, even if they just wrap an Array for storage. The downside, of course, is that it's underscored so not necessarily source/binary-stable.

  2. I thought one of the motivations for this protocol was to remove the ArraySlice type entirely in favour of the conditional conformance on the regular Slice<T>. Does that just turn out not to be so performant, or what happened to that idea?

It's not quite the reason ContiguousArray exists.* To be fair, I don't think we've done the best job of explaining exactly the nature of Swift's Array. Array at its core is a contiguously stored block of memory, with one specific carved-out exception to grease the wheels of ObjC interop. This is very different from NSArray, which abstracts away the storage to a much greater degree, giving it flexibility to present an "array-like" interface to multiple different backings.

Here's a run-down of when Array will be contiguously stored:

  • Arrays created in Swift will always be contiguously stored;
  • Arrays of structs and enums will always be contiguously stored;
  • Arrays on platforms without an Objective-C runtime (i.e. non-Darwin platforms) are always contiguously stored;
  • The only time an array won't be contiguously stored is if it is of classes and has been bridged from an NSArray
    • Even then, in many cases, the NSArray will be contiguously stored and can present a pointer at no or amortized cost

edit: accidentally hit post early, sorry, still writing...

This last case is what we call "lazy bridging". The hope is it will diminish over time, and in the long term, vanish altogether. I can't go into much detail about exactly how/when because that is a matter for Apple's internal platforms rather than Swift. But it should become at most an edge case at some point.

For all these reasons, I believe it would be a big mistake to bake the caveat into the name of the protocol. As the saying goes, protocols are not just bags of syntax. You must read and understand the guarantees they offer, and that can include documenting the edge cases such as lazily bridged arrays. This goes triple for unsafe operations. If you are calling a method with "unsafe" in the name, but don't read the documentation to understand exactly what you're doing, then far worse fates are likely to befall you than an accidentally quadratic loop.

Also bear in mind, this API is not intended to be used in a loop. The idea is, if you are optimizing (and this is for very low level optimizations, not to be undertaken lightly) then you should wrap the body of the bulk of your code in this method. If you are darting in and out of withUnsafeBufferPointer inside a hot loop, you are misusing the API. In almost all use cases, you are going to be performing an O(n) operation with the buffer, so in the rare cases it makes a copy, your algorithm remains O(n).

Finally, note that these caveats only apply to the un-mutable variant. The first thing an array does when you call a mutating method is ensure that it's uniquely referenced and contiguous, so even lazily bridged arrays will become contiguous at that point.

* ContiguousArray exists because the optimizer cannot eliminate the branch that checks for lazy bridging on each element fetch from an Array e.g. when iterating, when that array contains classes. So sometimes you might find that using a ContiguousArray yields a slight speed-up for some code. This is usually a nano-optimization, and also never applies on Linux or with arrays of structs.

12 Likes

This is all great detail, thanks Ben! After reading a detailed explanation of how narrow the edge case is, I agree with the name as it is proposed.

3 Likes

There's a good reason for the similarity between the naming of the Objective-C types and the Unsafe*BufferPointer types: they both have reference semantics.

In Swift we can indeed move away from having to represent mutability as part of the type name. Values types, mutating methods, and copy-on-write let us create types with value semantics. That way, both the vendor and recipient of a type can safely ignore the problems caused by mutation, because they both hold independent values. And local mutability can be controlled with let vs var.

But unsafe buffer pointers can't be value types. They have reference semantics by their very nature. Hence you need to represent whether they're mutable or not in the type system.

6 Likes

This seems a little smelly. Wouldn’t it be better to provide an optimized sort on the correct protocol to begin with, the same way we override .index(_:offsetBy:) on RandomAccessCollection?

1 Like

That approach doesn't scale. sort is just a single example – the point of adding this customization point is not to optimize just one method, but to optimize any algorithm which could benefit from access to an underlying storage buffer. Bear in mind, only the standard library can add customization points. So while it could add them for each of its own algorithms as needed (even though that bloats the witness tables, so is still not a good idea), users adding their own algorithms outside the standard library cannot.

I'm guessing that in the future we'd rather write this as a failable downcast to MCC. It's a shame this must become ABI, but there's no alternative if sort is to remain inlineable.

Also: Given that piecewise-contiguous collections are not supposed to support this protocol, doesn't it make sense that you can randomly access a collection with contiguous storage? Why not refine RandomAccessCollection?

1 Like

I'm in favour of this proposal.

SwiftNIO has defined a constrained version of this protocol for collections where the collection can expose its contents as UnsafeRawBufferPointers. A version where Element is UInt8 is likely to be very helpful.

In principle NIO's protocol differs slightly (Array<FooStruct> still conforms to NIO's ContiguousCollection protocol, as we can obtain the contiguous bytes of the storage). I think that NIO's broader application might not be a good thing, though: constraining ourselves to collections of UInt8s in most cases is likely to be a good thing.

Regardless, this is a thing that we've used a lot, and will likely continue to use in future, so +1.

+1 and what Cory says. The NIO version of this protocol isn't actually super smart (but good enough for our use-cases), would love to see the stdlib have ContiguousCollection as proposed.

Small thoughts:

  • It should be documented that successive calls to withUnsafeBufferPointer are not guaranteed to give you the same pointer, and that withUnsafeMutableBufferPointer is not guaranteed to give you the same pointer as a previous call to withUnsafeBufferPointer or vice versa. In practice this won't usually be different except for performing a copy-on-write, but I could see us wanting the flexibility for things like small strings where spilling to a stack buffer is a valid implementation strategy with negligible overhead. (A packed representation of some fixed-size or limited-size collection, for example.)

  • It's also worth documenting why the UnsafeMutableBufferPointer closure parameter is inout, since it confuses people.

  • withUnsafeMutableBufferPointer needs documentation about its guarantees (or lack thereof) if the closure throws.

  • Can ContiguousCollection and MutableContiguousCollection provide reasonable default implementations for the other Collection protocols, or is that a bad idea for performance reasons?

  • On that note, I also like the idea of ContiguousCollection refining RandomAccessCollection.

4 Likes

*answers self* It might be able to provide some (for example, a different iterator index type that just wraps Int) but it can't provide _read or _modify for subscripts, so maybe this isn't worth it.

1 Like

Yeah, also, once you are random-access and have an integer index, you get all the index advance/distance methods defaulted for you anyway.

Thanks Jordan, I took all that feedback into the proposal except the part about defaults.

1 Like