[Second review] SE-0516: `Iterable`

As the writer and presenter responsible: The video is pretty much describing what I currently expect Swift to look like when 6.4 ships, but that doesn’t mean it won’t change between now and then. Features we’ve talked about in past WWDC videos have been delayed, redesigned, or removed before they shipped. That’s just the cost of producing these things at the beginning of the beta period rather than the end.

In particular, the fact that I talked about Iterable doesn’t mean that it can’t be renamed, redesigned, deferred, or completely rethought if that’s where the review and LSG discussions end up. Hopefully the discussions of element batching will still be useful even if the names are different, but if not, that’s life.

(Taking my presenter hat off for a moment, I don’t love the names in this proposal—IterableIterator is such a tongue twister that I tried not to say it aloud!—but I don’t have better suggestions.)

21 Likes

Hello all! The associated type and related names are obviously a point of concern here, so I'd like to suggest a few alternatives to IterableIterator for further discussion:

SpanIterator

Switching to SpanIterator would change the protocols in this way:

protocol Iterable<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    associatedtype SpanIterator: SpanIteratorProtocol<Element, Failure>

    @_lifetime(borrow self)
    func makeSpanIterator() -> SpanIterator
    // ...
}

protocol SpanIteratorProtocol<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    // ...
}

The current version of the proposal includes a type called SpanIterator that just wraps a single Span – that could be renamed to SingleSpanIterator or could be nested under Span. In that case, each of the types currently using SpanIterator as its iterator type would change to Span.SpanIterator.

Spans

The much briefer name Spans feels related to the associated type names in the Sequence and Collection sphere: Index, Indices, and SubSequence. For better or worse, this approach would make Iterable feel slightly less connected to the Sequence protocol and its iterator type:

protocol Iterable<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    associatedtype Spans: SpansProvider<Element, Failure>

    @_lifetime(borrow self)
    func spans() -> Spans
    // ...
}

protocol SpansProvider<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    // ...
}

BorrowingIterator

Lastly, we could use the new Iterator name with the BorrowingIterator names from the original proposal.

protocol Iterable<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    associatedtype BorrowingIterator: BorrowingIteratorProtocol<Element, Failure>

    @_lifetime(borrow self)
    func makeBorrowingIterator() -> BorrowingIterator
    // ...
}

protocol BorrowingIteratorProtocol<Element, Failure>: ~Copyable, ~Escapable {
    associatedtype Element: ~Copyable
    associatedtype Failure: Error = Never
    // ...
}
7 Likes

This approach was explored as a part of our design process, with results discussed in Basing ~Copyable iteration on IteratorProtocol in the Alternatives section. In short, the proposed direction prioritizes support for bulk iteration and ergonomic usage in Swift, based on the differences between Rust's and Swift's defaults and syntax.

The Alternatives section also specifically addresses this question in Only support sequences with direct storage. We are actively working on modeling types with persistent storage in the swift-collections package, as described in Container and other protocols.

1 Like

Thanks for the nudge in the right direction.

This section says:

Primarily, the bulk iteration aspect of the proposed Iterable protocol is a critical part of improving performance when working with a wide variety of collections.

I'd like to hear why making an iterator (with all methods inlineable) which holds a Span and traverses it one Ref at a time doesn't meet the performance goals.

In addition, the different element types used in this alternative design lead to awkward usage at the call site. For example, when used with a Span<NoncopyableInt>, the first(where:) method declared above would have a signature like the following, with a (borrowing Ref<NoncopyableInt>) -> Bool predicate parameter. Forcing interaction with the element a user actually wants work with to go through a wrapper type in such a common case doesn't meet our usability expectations.

This is yet another reason why myself and several others said we needed to address the automatic denaturing of Ref to borrowing at the time those proposals were pushed through. Alternatively, (to quote so many responses to my proposal critiques at that time) "just because the language can't do it now, isn't reason not to do the rest of it". Iterator can return Ref<Element> now, and we can deal with improving the ergonomics of that in a later proposal.

1 Like

(IterableIteratorAdapter would also need to be renamed, if it's still part of this proposal.)

I think the renaming partly depends on whether consuming/draining/mutating iteration from the "Future directions" section will be proposed later.

With this first alternative, it isn't clear how to name the consuming/draining APIs.

Borrowing iteration Mutating iteration Consuming iteration
Iterable ??? ???
SpanIterator MutableSpanIterator ???
makeSpanIterator() makeMutableSpanIterator() ???
SpanIteratorProtocol MutableSpanIteratorProtocol ???

With this second alternative, putting a spans() -> Spans method on the various span types might be confusing or out of place.

With this third alternative, the naming scheme is simpler. (Although I can't imagine exactly how consuming/draining iteration will work.)

Borrowing iteration Mutating iteration Consuming iteration
Iterable ??? ???
BorrowingIterator MutatingIterator ConsumingIterator
makeBorrowingIterator() makeMutatingIterator() makeConsumingIterator()
BorrowingIteratorProtocol MutatingIteratorProtocol ConsumingIteratorProtocol

Using a nested type seems like a good idea, even if there isn't a naming clash.


In the "Standard Library adoption" section:

The SpanIterator type stores both a Span and the current offsets into the span, to allow flexibility for future kinds of iteration.

If "future kinds of iteration" means bidirectional or random-access iteration, does the skip(by:) requirement need to be renamed? Or would skip(by:) allow a negative offset?

1 Like

I believe Ben answered this question for you in the first review. The tl;dr is that even leaving the borrowing/copying thing aside, calling a next() method for every element is a problem for performance by itself, and it takes heroic effort by the optimizer to compile that down to something fast. Trafficking in Spans more directly exposes what’s needed to achieve best-case iteration performance.

4 Likes

One thing that jumped at me was the alternatives section is about the tradeoff between compiler complexity and long-term API complexity.

I understand the desire to avoid special casing Sequence in the compiler and to keep ownership expressed through the type system. That seems like a very reasonable goal.

That said, Sequence is such a fundamental abstraction that I found myself wondering whether the opposite tradeoff might actually be preferable here.

The proposal introduces a parallel iteration hierarchy (Iterable, IterableIteratorProtocol, makeIterableIterator(), etc.) rather than evolving the existing Sequence model. While that keeps the compiler cleaner, it also adds concepts, naming, and APIs that users and library authors will have to learn and live with indefinitely.

From a user’s perspective, the tradeoff feels a little different because compiler complexity is something most of us rarely interact with directly, while new protocols and APIs become part of the model most user must learn and cemented as language surface forever. I’m curious how that factored into the design discussion.

Was there much discussion around where that balance should be? Specifically, was there a point where preserving a more Sequence-centric model was considered worth some amount of compiler special-casing?

Relatedly, I’m curious whether ownership-aware iteration is expected to be a fairly isolated case, or whether we should expect similar ownership-aware counterparts to emerge for other foundational protocols over time.

I’m not asking because I think the proposal is wrong. I genuinely find the tradeoff interesting and would love to better understand how it was evaluated and get more visibility into inner working. Thank you.

5 Likes

You're right, he did. I took his word for it then, but the more I thought about it, the more I didn't understand why the ABI boundary was relevant — I was thinking of it as the user's for…in loop, which is quite optimizable if the Iterator is inlinable. It'd be rare for the user's code to need to be generic over container types returned from ABI-stable libraries and those libraries be unable to stabilize a concrete iterator type to enable inlining.

But rereading that now, I see it's more about the ABI boundary being above a generic function which needs to iterate a user-provided container. In that case, the iterator can never be inlined, so having it return larger chunks is important.

That seems pretty edge-case-y though! I'm struggling to think of situations where system frameworks are in the habit of traversing user-provided collections. SwiftUI's ForEach might be an example, though it requires a RandomAccessCollection, so Iterable doesn't seem to meet its needs directly. And a situation where passing it a .enumerated() leads performance to tank (by returning 1-spans) seems undesirable too. And ForEach could be internally specialized for the common case of "got given an Array" or "got given any type whose Iterator is a SpanIterator", anyway.

I definitely understand the desire to have the iterator return large spans better, but mostly I'm still seeing it as a hypothetical concern. Whereas my points above about the complexity of combinators (and the immediacy with which implementing them discards the entire benefit of Span-centric iteration) still stand. If anything it makes me more convinced that this shouldn't be seen as "the future of most iteration" but rather "a special case optimization for direct for…in iteration of a container".

Just popping in to note for the record my prior API naming comments, which remain applicable I think.

4 Likes

A good example from before the Span types would be String(decoding:as:), which prior to my fixes this year was about 50x slower than it should be for decoding UTF16 because it wasn't working around this issue by extracting an UnsafeBufferPointer from the collection being decoded. I believe it's still slow for types that don't have the ability to do that. That pattern ("make one generic call to get an unsafe pointer and then use that instead") is fairly omnipresent in the stdlib.

5 Likes

And I appreciate that this proposal as it stands would go some way to resolving this — it could handle any Iterable<CodeUnit> and spit a String out. But I feel like the correct answer to this is to take Span<CodeUnit>, since taking an Iterable<CodeUnit> still has performance cliffs (notably, any kind of combinator is likely to reduce the iterator to producing 1-spans).

Or, build the decoder so you can imperatively feed it Span<CodeUnit> incrementally. Surely by far the most common case where you have more than one span isn't TreeSet (lol) or even Deque, but would be receiving the spans asynchronously from I/O, so having it accept a synchronous Iterable probably doesn't actually help very often.

3 Likes

That’s definitely the simplest thing to do, but there’s no reason that a combinator has to be written that way.

Obviously the options differ per-combinator, but I don't believe that this is practically true.

  • If map, flatMap or enumerated() transform more than the next item
    • it's no longer lazy (I'm aware Sequence.map isn't lazy by default, but that has its own set of problems)
    • it must manage an internal buffer of more than one item (which implies a complex set of possible policies for that buffer based on the output element size and upstream span size)
    • behavior becomes very unpredictable if its closure has side-effects
    • it may perform redundant work based on what other combinators are in the chain, eg. anything that cuts iteration short (first, prefix, contains, etc).
  • If filter filters more than the next item
    • it may perform redundant work based on what other combinators are in the chain
    • behavior becomes very unpredictable if its closure has side-effects
    • it is limited in how big a span it can pass through from upstream based on how many consecutive elements pass the filter; in the worst case it's all 1-spans anyway
  • If compactMap transforms and filters more than one item, it has both sets of problems combined
  • drop(while:) and prefix(while:) are fine
  • most other combinators are relatives of reduce, so they're not relevant

For the affected combinators, to me, the design of least surprise and very likely greatest efficiency would be to ask for 1-spans from upstream, and work element-by-element.

This is why I would like to see these combinators implemented as part of this proposal — their designs & the compromises necessary to support iteration-by-span feed meaningful discussion of the Iterable protocol itself.

1 Like

Least surprise, yes, for some of them. Greatest efficiency, no, not in general. These sorts of combinators are often chained in computations where each step does a fairly trivial operation that can be vectorized or otherwise cheaply evaluated in a loop. Operating on contiguous blocks of multiple elements in memory in such a scenario can be hugely advantageous even if you end up throwing much of that work away. If "asking for more data from upstream" means crossing a specialization boundary, that may easily be a couple orders of magnitude more expensive than everything else that happens in a processing chain, in which case you can do quite a lot of redundant work and still come out ahead vis-a-vis going one element at a time.

Karoy and Nate have prototyped some of this stuff in the swift collections package (Nate is in the midst of updating it to match the new names used in this proposal revision); I would encourage anyone interested in the shape of such operations to look there for early examples.

6 Likes

Good to know, but their current implementations of map and filter at least pass maximumCount: 1 upstream, as I expected.

(edit) I may have been too naïve in my reading of that code. It does sometimes pass maximumCount: 1, but I don't understand the difference between next() and generate on the Producer type, nor how Producer works with Iterable.

2 Likes

Roughly, Producer (as currently drafted) is a protocol representing a sequence that transfers ownership of the items it produces, rather than providing borrowing access to them ("consuming" iteration vs "borrowing" iteration). next() asks for one element at a time, but callers can also use generate(into:) as a way to consume multiple elements at once.

So the MapProducer you linked to will ask the underlying Iterable object for one item at a time when it is asked for one result at a time, but can also ask for multiple items when it is asked to provide multiple results. I don't want to derail this thread with a design discussion of what will surely be another evolution proposal, so let's start a separate thread if you want to discuss this in more detail.

I guess the question that's relevant to this proposal is, are these combinators of Iterable not themselves Iterable? Because if we're immediately adding a 3rd style of iteration to the mess, I don't think this one should be squatting the good Iterable name. And I think we should be discussing whether this one and that one could be unified.

It isn’t possible to abstract over totally different ownership behaviors, so unification isn’t a consideration.

2 Likes

This has been discussed at some length in a variety of threads, but perhaps not clearly articulated in any one place. They mostly cannot, because the distinction between consuming and borrowing is fundamental--we end up wanting a way to spell both forms of iteration--but we think borrowing iteration (as captured in this Iterable protocol) is the form that most people should reach for most of the time, so it makes sense to give it the primary name.

2 Likes

I think this is mistaken: the primary name is already taken by Sequence and makeIterator(). Those two won't be dislodged so easily. Iterable is more complex and has more constraints; and other than the name Iterable all the other names in this proposal are more complex and intimidating than those from the Sequence family and don't look like a primary name that much:

Copying Borrowing
container Sequence Iterable
iterator IteratorProtocol IterableIteratorProtocol
getter makeIterator() makeIterableIterator()
advancing next() nextSpan() & skip()

I think a borrowing iteration is a more specialized concept than the old copying one. Its purpose is to optimize things with the tradeoff that it is more difficult to implement and might not make sense in all cases. Swift promotes this idea that things are copyable by default, and that non-copyable types and lifetimes are more advanced concepts a subset of users need to know about. Containers will have their "Unique" specialized variants to deal with non-copyables and lifetimes, and I think the same logic should apply here too: dealing with borrows is sort of specialized and thus Sequence will stay as the approachable iteration protocol. Borrowing iteration should be left for when you need optimization or when dealing with non-copyable types.

So I suggest going back to BorrowingSequence as a way to express this specialization. It also makes all the other names much clearer by getting rid of the "IterableIterator" nonsense. And it keeps names aligned across various sequence/iterator types, from the old one to all the new ones in the future:

Copying Borrowing Consuming
container Sequence BorrowingSequence ConsumingSequence
iterator IteratorProtocol BorrowingIteratorProtocol ConsumingIteratorProtocol
getter makeIterator() makeBorrowingIterator() makeConsumingIterator()
advancing next() nextSpan() & skip() TBD
19 Likes