SE-0231 — Optional iteration

That also makes for a hugely verbose language which, again, is not Swift. You're talking about fundamentally changing the design principles behind the language, or having a one off use case for this feature.

Whew.... perfect case where it's best ignore unsubstantiated conclusions.

I was mainly pointing out that that particular solution was largely ignored because it doesn’t fit the language.

This is not accurate, at least for the problem I outlined. The error-prone solution of ?? [] was an entirely library-level solution, and the problem was not specific to operators. It can happen with methods as well.

@endofunk Why does the conversation feel like the above would be a valid solution for optional iteration? This is just another way of spelling ?? []. Regardless of it's benefits, you still have to find an actual orElse.

Without trying to upset this apple cart. Let's simply review the code sample you provided:

for i in maybeHugeRange?.reversed() ?? [] { // doom occurs here
  print(i) // your app will jetsam without ever reaching here
  break
}

...and consider an alternative method like Rust's unwrap_or. I'll use the simple code sample I provide earlier:

extension Optional {
  func ifSome(orElse: Wrapped) -> Wrapped {
    switch self {
    case .some(let wrapped): return wrapped
    case .none: return orElse
    }
  }
}

Trying to do this kind of this isn't possible re "Left side of nil coalescing operator '??' has non-optional type '[Int]', so the right side is never used"

for i in maybeHugeRange.ifSome(orElse: 0..<0).reversed() ?? [] {
  print(i) // your app will jetsam without ever reaching here
  break
}

So maybe I'm missing the obvious here... how exactly does the method end up with the same issue.

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.

Terms of Service

Privacy Policy

Cookie Policy