SE-0234: Removing Sequence.SubSequence

[Ben_Cohen]

@palimondo

I was coming from the perspective of .lazy sequences, where the eager part messes up the method chaining. That's probably a stronger case to also provide LazySequeceProtocol version, that delays the dropping until the first call to Iterator.next , right?

I'm not sure it's all that useful to defer dropping until the first call to next. The times when someone calls makeIterator, but then doesn't consume from it at all are probably pretty tiny (even in the case of zip, you'd only realize a win if the left side of the zip was empty). The trade-off is that by dropping all the elements at the start, you avoid having to check the count is zero every time you call next. It's probably worth a quick benchmarking to see if that makes any difference.

I think someone mentioned upstream that DropFirstSequence should conditionally conform to LazySequenceProtocol where Base: LazySequenceProtocol, which would avoid the current un-lazying.

It would be a good starter bug/proposal for someone to go through and find other eager things that should be added to lazy. split is definitely a case where a lazy equivalent would be good to add. Probably also, any future proposals for eagerly-evaluated additions should usually be paired with a lazy version if appropriate.

[palimondo (Pavol Vaskovic)]

@Ben_Cohen

I'm not sure it's all that useful to defer dropping until the first call to next . The times when someone calls makeIterator , but then doesn't consume from it at all are probably pretty tiny

I'm specifically thinking about lazy method chaining, that allows the compiler to fuse them all into single loop. I don't have examples that include dropFirst, but to illustrate what I have in mind:

@palimondo

func slpwpc(c: ℂ) -> Int {
    return sequence(first: ℂ(0), next: {z in z * z + c})
        .lazy
        .prefix(while: {$0.isPotentiallyInSet()})
        .prefix(maxIter)
        .count()
}

It is 33x slower then the imperative baseline.

Or a little bit of manual fusion of closures:

@palimondo

This is, in my opinion, the most “swifty” expression of the Mandelbrot renderer:

func mandelbrot_(_ c: ℂ) -> Int {
    return sequence(first: ℂ(0), next: {z in
        guard z.isPotentiallyInSet() else {return nil}
        return z * z + c
    }).lazy.prefix(maxIter).count()
}

It fuses one limiting bound of the infinite sequence into the inline closure with the guard statement and leaves the other one for the prefix method. The closure for next parameter is capturing the value of c . We’re using the first variant of sequence that internally contains another capturing closure . Using the master dev toolchain snapshot from May 30, 2018, this is 28x slower than imperative version. But as we’ll see later, this is mainly due to prefix implementation’s use of AnySequence .

When I replaced prefix with my implementation:

@palimondo

I was finally able to cobble together a composed “swifty” version that performs on par with the imperative baseline :

func mandelbrotL(_ c: ℂ) -> Int {
    return sequence(first: ℂ(0), next: {z in
        guard z.isPotentiallyInSet() else {return nil}
        return z * z + c
    }).lazy.prefixL(maxIter).count()
}

If you think this looks familiar, you’re right. Only difference from mandelbrot_ from above is the use of .prefixL — a proper LazySequence implementation of the method like those from SE-0045. Quite anticlimactic, if I may say.

I'd love to verify that #PR 20221 matches that performance. Can you please provide us with downloadable toolchain?

[John_McCall]

SE-0234 has been accepted; thank you all for your participation.

I'll be closing this thread, but please feel free to take the discussion about lazy sequence implementations to the evolution discussion forum.