Rationalizing Sequence.SubSequence


(Ben Cohen) #1

One last ABI-related protocol pitch....

There have been a number of pitches over recent months about Sequence. Should it be single or multi-pass? If it's single-pass, how is it different from IteratorProtocol? If it's multi-pass, should it be deprecated altogether? Can that be done in a source-compatible way?

There are also outstanding issues about the future of the language. How will sequences of move-only types work? Should iterators be move-only? Will we have co-routine-based generators instead of iterators, and should they replace Sequence or should Sequence be how you get a generator?

The core team discussed this recently and agreed that given the impending ABI stability deadline, it is not practical to try and resolve these issues before Swift 5. Instead, we should try and amend Sequence reduce it's ABI impact as much as possible, so that we will have as much flexibility in the future to either deprecate or amend it as needed without hampering finalizing other aspects of the ABI or adding functionality to the standard library (such as collection conformance for existing sequence-only types).

So this pitch is about reducing the ABI impact of Sequence. Specifically, about how Sequence and SubSequence interact. It recommends eliminating the associated type from Sequence, moving it up to start at Collection.

Current usage

Today, Sequence declares several methods that return a SubSequence:

func dropFirst(_:) -> SubSequence
func dropLast(_:) -> SubSequence
func drop(while:) -> SubSequence
func prefix(_:) -> SubSequence
func prefix(while:) -> SubSequence
func suffix(_:) -> SubSequence
func split(separator:) -> [SubSequence]

You don't have to implement them to implement a Sequence. They all have default implementations for the default type for SubSequence.

But if you think about how you'd implement them generically on a single-pass sequence, you'll quickly realize there is a problem. They all call for completely different return types in their implementation. For example, the ideal way to implement dropFirst would be to return a wrapper type that first drops n elements, then starts returning values. prefix would ideally be implemented the other way around: return elements until you've returned n, then stop. suffix and dropLast need to consume the entire sequence to get to the end, buffering as they go, then return what they buffered. drop(while:) needs to eagerly drop non-matching elements as soon as it's called (because the closure is not @escaping), which means it needs to buffer one element in case that's the first one it needs to return later. prefix(while:) also needs to eagerly search and buffer everything it reads.

But the protocol requires all these methods return the same type – SubSequence. They can't return specific types for their specific needs. In theory, that could be resolved by having them all return [Element], but that would be wasteful of memory in cases like prefix(_:).

The way the std lib works around this is to make the default SubSequence an AnySequence<Element>. So internally, there is a DropFirstSequence type, that is created when you call dropFirst on a Sequence. But it is type-erased to be the same type as returned by prefix, suffix etc., which also return their own custom types, but type erased.

Unfortunately this has two major consequences:

  • performance is bad: type-erased wrappers are an optimization barrier; and
  • it blocks conditional conformance going from Sequence to Collection.

Additionally, it makes implementing your own custom SubSequence that isn't AnySequence extremely hard, because you need to then implement your own version of all these methods, even split. So in practice, this is never done.

Type erasure performance

There is a prototype in this PR that replaces the customization points on Sequence with regular extensions that each return a specific type.

To see the performance problem, here is how the benchmarks improve if you return a non-type-erased type instead:

Performance: -O

TEST OLD NEW DELTA RATIO
Improvement
DropWhileSequence 2214 29 -98.7% 76.34x
PrefixSequenceLazy 2265 52 -97.7% 43.56x
PrefixSequence 2213 52 -97.7% 42.56x
DropFirstSequenceLazy 2310 59 -97.4% 39.15x
DropFirstSequence 2240 59 -97.4% 37.97x

Performance: -Osize

TEST OLD NEW DELTA RATIO
Improvement
DropWhileAnySeqCRangeIter 17631 163 -99.1% 108.16x
DropFirstAnySeqCRangeIterLazy 21259 213 -99.0% 99.81x
PrefixAnySeqCRangeIterLazy 16679 176 -98.9% 94.77x
PrefixAnySeqCntRangeLazy 15810 168 -98.9% 94.11x
DropFirstAnySeqCntRangeLazy 15717 213 -98.6% 73.79x
DropWhileSequence 2582 35 -98.6% 73.77x
DropFirstSequenceLazy 2671 58 -97.8% 46.05x
DropFirstSequence 2649 58 -97.8% 45.67x
PrefixSequence 2705 70 -97.4% 38.64x
PrefixSequenceLazy 2670 70 -97.4% 38.14x

These performance improvements are all down to how well the optimizer can eliminate the wrapper abstractions when there isn’t the barrier of type erasure in the way. In -Onone builds, you don’t see any speedup.

How does it block conditional conformance?

The problem with SubSequence really became clear when conditional conformance was implemented. With conditional conformance, it becomes really important that an associated type be able to grow and take on capabilities that line up with the capabilities you are adding with each new conformance.

For example, the Slice type that is the default SubSequence for Collection grows in capabilities as it’s base grows. So for example, if the Base is a RandomAccessCollection, then so can the Slice be. This then works nicely when you add new conformances to a Collection that uses Slice as it’s SubSequence type. For more detail on this, watch Doug’s explanation in our WWDC Swift Generics talk (starts at about minute 26).

But the default type for Sequence.SubSequence is AnySequence, which is a conformance dead end. You cannot add additional capabilities to AnySequence because there is nothing to drive them: the type erases all evidence of it’s wrapped type – that’s it’s point.

This in turn forces two implementations of types that would ideally have a single unified implementation. For example, suppose you wanted to write something similar to EnumeratedSequence from the standard library, but have it be a Collection as well when it could support it.

First you start with the basic type (note, all this code takes shortcuts for brevity):

struct Enumerated<Base: Sequence> {
  let _base: Base
}
extension Sequence {
  func enumerated() -> Enumerated<Self> {
    return Enumerated(_base: self)
  }
}

And add Sequence conformance:

extension Enumerated: Sequence {
  typealias Element = (Int,Base.Element)
  struct Iterator: IteratorProtocol {
    var _count: Int
    let _base: Base.Iterator
    mutating func next() -> Element? {
      defer { _count += 1 }
      return _base.next().map { (_count,$0) }
    }
  }
  func makeIterator() -> Enumerated<Base>.Iterator {
    return Iterator(_count: 0, _base: _base.makeIterator())
  }
}

Then, you’d want to add Collection conformance when the underlying base is also a collection. Something like this:

extension Enumerated: Collection where Base: Collection {
  struct Index: Comparable {
    let _count: Int, _base: Base.Index
    static func < (lhs: Index, rhs: Index) -> Bool {
      return lhs._base < rhs._base
    }
  }
  var startIndex: Index { return Index(_count: 0, _base: _base.startIndex) }
  var endIndex: Index { return Index(_count: Int.max, _base: _base.endIndex) }
  subscript(i: Index) -> Element {
    return (i._count, _base[i._base])
  }
}

You’d then follow through with conformance to RandomAccessCollection too when the base was. You can see this pattern used throughout the standard library.

But this code won’t compile. The reason is that Collection requires that SubSequence also be a collection (and BidirectionalCollection requires it be bi-directional, and so on). This all works perfectly for Slice, the default value for SubSequence from Collection down, which progressively acquires these capabilities and grows along with the protocols it supports. But AnySequence can’t, as described above. It blocks all further capabilities.

Because of this, if you want to support collection-like behavior, you’re back to the bad old days before conditional conformance. You have to declare two separate types: EnumeratedSequence and EnumeratedCollection, and define the enumerated function twice. This is bad for code size, and also leaks into user code, where these two different types appear.

Why is Sequence like this?

The reason why Sequence declares this associated type and then forces all these requirements to return it is to benefit from a specific use case: writing a generic algorithm on Sequence, and then passing a Collection to it. Because these are customization points, when Collection is able to provide a better implementation, that generic algorithm can benefit from it.

For example, suppose you pass an Array, which provides random-access, into an algorithm that then calls suffix. Instead of needing to buffer all the elements, requiring linear time and memory allocation, it can just return a slice in constant time and no allocation.

You can see this in the regressions from the same PR:

Performance: -O

TEST OLD NEW DELTA RATIO
Regression
DropLastAnySeqCntRangeLazy 9 20366 +226163.8% 0.00x
SuffixAnySeqCntRangeLazy 14 20699 +147739.4% 0.00x
DropLastAnySeqCntRange 9 524 +5721.6% 0.02x
SuffixAnySeqCntRange 14 760 +5328.2% 0.02x

Performance: -Osize

TEST OLD NEW DELTA RATIO
Regression
DropLastAnySeqCRangeIterLazy 3684 20142 +446.7% 0.18x
SuffixAnySeqCRangeIterLazy 3973 20223 +409.0% 0.20x
SuffixAnySeqCntRangeLazy 5225 20235 +287.3% 0.26x
DropLastAnySeqCntRangeLazy 5256 20113 +282.7% 0.26x
DropFirstAnySeqCntRange 15730 20645 +31.2% 0.76x

What is happening in these is a random-access collection (a CountableRange) is being put inside the type-erasing AnySequence, then suffix or dropLast is being called on it. The type-erased wrapper is then forwarding on the call to the wrapped collection. Fetching the suffix of a countable range is incredibly fast (it basically does nothing, ranges are just two numbers so it’s just adjusting the lower bound upwards), whereas after removing the customization points, the suffix function that’s called is the one for a Sequence, which needs to iterate the range and buffer the elements.

This is a nice performance tweak, but it doesn’t justify the significant downsides listed above. It is essentially improving generic performance at the expense of concrete performance. Normally, these kind of generic improvements come at just a tiny cost (e.g. slight increase in compile time or binary size) rather than a significant runtime performance penalty.

Proposed Solution

Remove the SubSequence associated type from Sequence. It should first appear from Collection onwards.

Remove the methods on Sequence that return SubSequence from the protocol. They should remain as extensions only. Each one should return a specific type best suited to the task:

extension Sequence {
  public func dropFirst(_ k: Int = 1) -> DropFirstSequence<Self>
  public func dropLast(_ k: Int = 1) -> [Element]
  public func suffix(_ maxLength: Int) -> [Element]
  public func prefix(_ maxLength: Int) -> PrefixSequence<Self>
  public func drop(while predicate: (Element) throws -> Bool) rethrows -> DropWhileSequence<Self>
  public func prefix(while predicate: (Element) throws -> Bool) rethrows -> [Element]
  public func split(
    maxSplits: Int = Int.max,
    omittingEmptySubsequences: Bool = true,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [ArraySlice<Element>]
}

DropFirstSequence, DropWhileSequence and PrefixSequence already exist in the standard library in underscored form.

This will also have the useful side-effect that these methods can also be removed as customization points from Collection as well, similar to removing prefix(upTo:) in SE-0232, because there’s no longer any reasonable customization to be done on a per-collection basis.

Doing this will have considerable benefits to code size as well. For example, the CoreAudio overlay that declares a handful of collections reduces in size by 25% after applying these changes.

Once done, this change will allow the following simplifying changes and enhancements to standard library types:

  • LazySequenceProtocol and LazyCollectionProtocol can be collapsed into a single protocol.
  • The following type can be collapsed, dropping the collection variant (with a typealias provided for source compatability):
    • FlattenSequence and Collection
    • LazySequence and LazyCollection
    • LazyMapSequence and Collection
    • LazyFilterSequence and Collection
    • LazyDropWhileSequence and Collection
    • LazyPrefixWhileSequence and Collection
    • LazyMapSequence and Collection
  • The following types can be extended to support Collection:
    • EnumeratedSequence
    • JoinedSequence
    • Zip2Sequence

ABI and Source Compatibility

This is an ABI-breaking change, so must happen before 5.0 is released.

This is also source-breaking, in that any code that relies on Sequence.SubSequence will no longer work. For example:

extension Sequence {
 func dropTwo() -> SubSequence {
   return dropFirst(2)
 }
}

There are no examples of this kind of code in the compatibility suite. Unfortunately there is no way to remove an associated type in a way that only affects a specific language version, so this would not be something you could handle as part of upgrading to 5.0.

Additionally, any sequences that define a custom SubSequence of their own will no longer work. This is really a non-problem, because doing so is almost impossible (it means you even have to implement your own split).


(Thomas Roughton) #2

The trade-offs definitely seem worthwhile. Moving to concrete rather than type-erased types does mean that any code that relied upon an AnySequence return type breaks (e.g. if it passed the result to a different function), but if that encourages people to write those functions in a generic manner instead I think that’s a net positive.

One tangential question: these varied return types seem like they would be best represented using opaque result types. If opaque result types were later added to the language, am I correct in thinking that switching the returned sequences to be opaque would be a source- but not ABI-breaking change?


(Greg Titus) #3

+1!

I'd suggest replacing the associatedtype SubSequence declaration in Sequence with something like the following.

    @available(*, unavailable, message: "SubSequence no longer exists see release notes, etc")
    typealias SubSequence = Never

(You can't set the availability of an associated type, but an unavailable type of some kind with that name gives the opportunity to provide a nicer error message to any user code that uses it.)


(Dennis Vennink) #4

This is a major improvement.

For the list of changes and enhancements; note that DropFirstSequence, DropWhileSequence and PrefixSequence can conform to LazySequenceProtocol when Base conforms to LazySequenceProtocol (closing SR-5754).

Very exciting!


#5

How exactly will this work for Collection?

Will the methods you listed (like suffix) be added as requirements on Collection that return a SubSequence, or are they only going to exist as extension methods on Sequence that return a concrete type?


(Ben Cohen) #6

This is mentioned, but it could probably be more explicit. The equivalent methods would remain as extensions, returning SubSequence, but not as requirements on the protocol. So they wouldn't be customization points. There's no good reason for them to be – the only reasonable implementations are brief and straightforward calls to subscript.

There is a reasonable case to be made that they should not be there at all – that instead of shadowing the Sequence versions, they could be removed and only the Sequence version remain. This would be a simpler model, but give up performance, especially for thing like suffix. I would guess that it would also be a lot more extensively source-breaking than the equivalent Sequence change. Luckily, so long as we drop the customization points, we can make this change later in an ABI-stable way, so it doesn't need to be considered as part of this proposal.


(Xiaodi Wu) #7

On balance, this pitch may be for the best. However, it's a major drawback that we're resorting to shadowing in such a way that an algorithm generic over Collection which calls a method would get something done hundreds of times faster than an algorithm generic over Sequence which appears to call the same method (but in fact calls a shadowed one).

Now, based on the -O performance data:

  • drop(while:), dropFirst(_:) and prefix(_:) improve dramatically when we abandon type erasure
  • dropLast(_:) and suffix(_:) regress dramatically

These are mutually exclusive, and they sort into two logical groups: those methods that are about elements at the beginning and those that are about elements at the end--which makes sense.

I haven't fully thought this through, but would that not suggest that there is some middle way, where we can drop type erasure for the first group of methods but not the second, reducing ABI impact and gaining performance without suffering these regressions?


(Ben Cohen) #8

This needs clarification, because that isn't quite what is happening. What is happening is all methods on sequences improve dramatically, including suffix and dropLast.

However, if you write a generic algorithm on Sequence, which has clearly documented linear performance for suffix, but you pass in a random-access collection, you no longer get a magic speedup.

This would be a fairly odd thing to rely on in an algorithm. Sequence clearly documents the performance of suffix to be linear. Bear in mind, since Sequence is not multi pass, you also should not be doing this in a loop. Saying "but it's there, people might use it" doesn't seem like a good enough argument. You could say the same thing about count, which is clearly documented as linear on all but random-access collections. If you need it to be constant in performance for your algorithm, you need to write your collection on RandomAccessCollection and nothing else. The type system is not going to help you figure this out – you just need to read the docs.

Bear in mind, these benchmarks are not real-world examples. They are artificial microbenchmarks designed to detect unintentional regressions as we develop the compiler. The tightness of the loop is often a measure of the triviality of the operation being measured – so when you regress or improve them, the numbers are sometimes dramatic (we currently have an example of a 1.7 million times speedup on the string rework branch :) but you shouldn't take them to translate directly to actual code.

I'm pretty sure that would end up with us swallowing the spider to catch the fly. I did experiment with a Prefix and Suffix type that then got tied together later on in Collection to be equal. This ended up having pretty unpleasant effects on type inference and compiler performance, and re-introduces a lot of complexity for minimal benefit, that this proposal hopes to eliminate.

Fact is, suffix on Sequence is a bit of an odd method to start with, given what sequences are. I could see the argument for deprecating it some time in the future if we decide sequences are still a long-term thing we want to have. This change is all about setting us up so that we can do that in the future, even after ABI.


(Ben Cohen) #9

One other thing I should add: the code size measurements are also really important to consider. A lot of users care far more about code size than run time performance. The code size savings shown by the benchmarks are substantial, and also much more real, with the libraries dropping by up to 25% (bear in mind, even after Swift is in the OS, apps that are back-deploying will need to ship these), and several of the "app"-style benchmarks such as Luhn, StringMatch and CSVParsing, show 3-6% improvement in both -O and -Osize.


(Chéyo Jiménez) #10

I would also like the proposal to mention something about opaque types.

Overall I am a huge fan of this change. Thank you Ben for working on this.


(Karoy Lorentey) #11

I wholeheartedly agree with this change, except for one nit that is pestering me: I find SubSequence wasn't a great name before, and now it gets a little worse.

  • There is the spelling issue. It should have been called Subsequence, with a lowercase s. (I find it's impossible to unsee this; it'll bother me forever.)
  • With this change, the associated type is now unconditionally constrained to Collection, so it's hard to justify calling it a "sub-sequence" without referring to its history.

I hesitate to bring this up -- renaming the type makes the source compatibility issue worse, so it makes sense not to do it. But if we were to start from scratch, I'd name the associated type Collection.Slice and do away with the SubSequence name altogether. (The existing Slice generic could be renamed DefaultSlice, following the pattern established by DefaultIndices. It could also be left as is.)


(TJ Usiyan) #12

I request consume(_ k: Int) -> (head: [Element], DropFirstSequence<Self>) as an additional extension method. I don't care about the name but this would basically be dropFirst but 'holding' the dropped elements. This is tricky to implement properly for single pass sequences because isEmpty should be avoided.


(Ben Cohen) #13

I completely agree – but I just don't think we have the option to change it. These proposed changes are source breaking, but in practice would be very rare. But changing SubSequence would be a lot more breaking. We could add a type alias for users, but not for conformers, for example. And SubSequence is very pervasive in documentation, sample code, talk videos etc.