SE-0231 — Optional iteration

Hi @endofunk – since it isn't directly related to the review, I took my reply over to the discussion forum.

2 Likes

I'd like to add one more reason in favor of the optional chaining solution, one that looks a bit into the future.

It is likely that one day if and for will allow inout bindings, and you'll be able to write this:

if inout array = obj?.array {
  for inout x in array {
    x.mutate()
  }
}

Unfortunately, inout isn't possible with the result of ?? []. And unless a lot of things change, neither will it work with a function returning a wrapper collection.

But optional chaining already works well with inout. So if optional iteration is implemented in term of optional chaining, this should be fine:

for inout x in obj?.array {
  x.mutate()
}
7 Likes

If I may ask, where does this insight come from?

This is proposed in the ownership manifesto.

4 Likes

This is a good observation. The problem of mutation through wrapper collections, however, is one we know we already have, and will have to address in the move-only future. @Ben_Cohen and I have discussed some possible approaches that could eventually allow for this.

1 Like

It doesn't have to check if the original collection is empty on every iteration. And according to my quick test the following simple .orEmpty() doesn't add any overhead in an optimized build.

Here is a quick implementation and microbenchmark
import QuartzCore

public struct FlattenedOptionalSequence<Base: Sequence>: IteratorProtocol, Sequence {
    let baseNext: () -> Base.Element?
    init(_ optionalSequence: Optional<Base>) {
        switch optionalSequence {
        case .none: baseNext = { return nil }
        case .some(let s):
            var baseIterator = s.makeIterator()
            baseNext = { return baseIterator.next() }
        }
    }
    public func makeIterator() -> FlattenedOptionalSequence<Base> { return self }
    public mutating func next() -> Base.Element? { return baseNext() }
}

extension Optional where Wrapped: Sequence {
    func orEmpty() -> FlattenedOptionalSequence<Wrapped> {
        return FlattenedOptionalSequence(self)
    }
}

func test() {
    let n = 10_000_000
    let seq: [Int] = (0 ..< n).map { _ in Int.random(in: .min ... .max) }

    var nonEmptyTestCount = 0
    while nonEmptyTestCount < 7 {

        let optSeq: [Int]? = Bool.random() ? seq : .none
        if optSeq == .none { continue }

        do {
            print("  Using if let s = optSeq { for e in s { ... } }:")
            var cs = 0
            let t0 = CACurrentMediaTime()
            if let s = optSeq {
                for e in s {
                    cs &+= e
                }
            }
            let t1 = CACurrentMediaTime()
            print("    ", t1 - t0, "seconds (checksum: \(cs))")
        }
        do {
            print("  Using for e in optSeq.orEmpty() { ... }")
            var cs = 0
            let t0 = CACurrentMediaTime()
            for e in optSeq.orEmpty() {
                cs &+= e
            }
            let t1 = CACurrentMediaTime()
            print("    ", t1 - t0, "seconds (checksum: \(cs))")
        }
        nonEmptyTestCount += 1
        print()
    }
    
}

test()

I haven't checked if:

            for e in optSeq.orEmpty() {
                cs &+= e
            }

is optimized into identical asm as:

            if let s = optSeq {
                for e in s {
                    cs &+= e
                }
            }

But I wouldn't be surprised if it was.


Typical output on my MBP late 2013, 2 GHz i7
  Using if let s = optSeq { for e in s { ... } }:
     0.006638151011429727 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.005152345052920282 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.004637237987481058 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.00462937809061259 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.004614591947756708 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.004562856047414243 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.004583214991725981 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.004558937973342836 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.0047228699550032616 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.004625577945262194 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.00457263900898397 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.004642735002562404 seconds (checksum: 2508382841143532506)

  Using if let s = optSeq { for e in s { ... } }:
     0.004757425980642438 seconds (checksum: 2508382841143532506)
  Using for e in optSeq.orEmpty() { ... }
     0.004532704944722354 seconds (checksum: 2508382841143532506)

Program ended with exit code: 0

It seems to me that an implementation could do the nil check up front in such a way that the wrapper collection is naturally set up in an "empty" state—either the iterator for a sequence could be constructed in the nil-returning state, or a collection formed with equal startIndex/endIndex.

Exactly, see my post above : )

1 Like

But that still requires a wrapper. Your startIndex can’t just be the underlying collection’s startIndex because of the nil case, and every layer of wrapping you add increases the chance the optimizer gives up and goes home, leaving you with a performance cliff. The explicit if does not have this problem.

Does my example .orEmpty() implementation above have that problem? (someone more knowledgeable than me would have to analyze it and take a look at the disassembly etc.)

Then this is a problem of and case against every wrapping sequence type in the standard library (LazySequence, LazyCollection, UnfoldSequence, ReversedCollection, etc ...), and I guess many of them are at least as commonly used as this FlattenedOptionalSequence would be.

I for one thinks it's great that Swift's design allows it to have so much functionality in the stdlib instead of in the language/compiler, even UInt8 is in the stdlib!

(And I probably don't have to say that I'd prefer a simple solution like adding a method like .orEmpty() to the stdlib over having to add the concept of "degenerate optional chaining syntax" to all the stuff you have to digest in order to understand Swift's compiler magic, which is already a bit too mystical for my taste.)

Unrelated to your point, but I'd like to say that it seems more consistent to me that, if this proposal is adopted with the degenerate optional chaining syntax, your example would instead be:

for x in obj?.array? { .. }

Otherwise it's inconsistent with the case where you declare a variable for obj?.array separately.

1 Like

For the sake of completeness, I think there is another option that has not been mentioned yet:
Add a requirement to Sequence that constructs an empty instance so that you could write

for x in seq ?? .empty() {

I think there is a good reason that wasn't proposed, but let's look at its features:
It wouldn't need any wrapping, so it should be faster than all the library alternatives. But still, if the goal is maximal performance, if let would be better.
A compiler change could be optimal in every aspect (except, of course, acceptance among discussionists ;-), so you would never need to waste a thought on how to iterate a Sequence?.

Can't wait to discuss the new concepts and syntax needed for doing reversed iteration in the compiler rather than in the stdlib! : )

1 Like

Yes, all the notionally "zero-cost" wrapper types run the risk that if they don't get effectively optimized and inlined at compile time, they cease to be zero cost.* The simpler you keep them the better (for example, AnyCollection, which is very elaborate, still sometimes gets optimized away, but is very prone to suddenly falling off a cliff).

I don't mean to fearmonger. The optimizer gets better over time, and the cliffs become rarer, but it's always a risk that your code won't get optimized as well as you hope, and I've found the more you pile on, the more chance you'll hit problems.

* though bear in mind, with something like ReversedCollection, chances are you'll still be better off with a non-zero constant factor than the linear time + allocation that returning an array takes.

Yes, I did intentionally leave out the type erasing AnyCollection from the list, since I'm aware of what it's like efficiency-wise, and it's quite far from FlattenedOptionalSequence which is about as simple as they can get, apart from the baseNext closure, which I was expecting to maybe be a problem, but it does seem to get optimized away. Have you had a chance to look at it, and perhaps found some example in which it won't be optimized into to the equivalent of an if let contained for-in loop?

I’m pretty strongly -1 on this.

As others have pointed out, the for! element in optional spelling doesn’t make sense. On the other hand, for element in optional! already works, and for element in optional? looks to me to be creating an optional optional: it is not consistent with other usages of optional values:

For example, if your API takes an optional, you don’t feed it like this: aFunction(optionalValue?), but rather by just providing the optionalValue itself.

So to me, if anything, we should just allow for element in optional {} that is a no-op in the case of nil (as it essentially is for empty collections now).

But it is consistent with optional chaining which is the other place in the language where a no-op with optionals can occur.

Hmm. It’s not though, because you never write ? after the last part of the chain. Instead, it looks like takesAnOptional(nonOptional.optional) and takesAnOptional(optional?.optional). Off the top of my head putting a ? at the end of either results in an error.

If we’re talking about a nested optional like for element in optional?.property {} the suggestion to allow that without extra syntactic sugar still applies.

Edit: there is a case where the ? goes at the end, but only when it’s followed by a call to the preceding optional function (which results in another value, even if that value is Void, and is hence not actually the end of the chain)

It is consistent with how one matches Optional in patterns.

Some questions about the "degenerate optional chaining syntax"-solution that needs to have clear answers:

Would it involve messing with the grammar?

Is changing parsing rules likely to have unpleasant ramifications that we aren't expecting?

What would the type of hmm be, or what would the compile time error be, here:

let hmm = optSeq? // <--
for e in hmm { … }

given that this would compile:

for e in optSeq? { … }

?

2 Likes