[Review] SE-0052: Change IteratorType post-nil guarantee


(Chris Lattner) #1

Hello Swift community,

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager


(Brent Royal-Gordon) #2

  * What is your evaluation of the proposal?

I think it's a good idea.

This is a particularly sharp edge in the standard library: people have a completely reasonable expectation about `next()`'s behavior which is usually, but not always, borne out. And the vast majority of iterators can provide this feature for free. Only a few would pay any price, and that price would be minimal—it could easily be the cheapest statements in the method.

Nor do I think the FuseIterator solution will actually help. If you know about FuseIterator, you don't really need it, because you know about `next()`'s nil behavior and can code around it. This is an attempt to protect the people who *don't* know about the problem.

There are languages so averse to trading anything for efficiency that they refuse to provide simple improvements to help with these kinds of issues. I don't think Swift should be one of them.

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes.

  * Does this proposal fit well with the feel and direction of Swift?

I think so. One of the major themes of Swift 3 is cleaning up the standard library.

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I haven't, but some of the previous discussions on this issue have brought up Rust, which uses the FuseIterator solution. It seems like a pretty lousy one to me.

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Quick reading this time, but I participated the previous discussion.

···

--
Brent Royal-Gordon
Architechies


#3

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

• What is your evaluation of the proposal?

I'm -1.

I agree with Patrick Pijnappel that it is too easy to write code that assumes that iterators end with nil for good, and breaks when this assumption happens to be false.

I agree as well that the precondition that when calling next(), no preceding call to next() should have returned nil is not observed enough.

I agree that algorithms need guarantees and API contracts.

Yet I have three arguments against the proposal:

1. Obscurity argument: Both the existing precondition, and the proposed convention are non-enforceable, non-testable, not well-known enough, and generally too weak to be efficient in any way. People don't write custom iterators often enough, and I don't expect those rules to eventually percolate through Swift culture.

2. Social argument: when a user complains that my library crashes when fed with a third-party iterator that does not behave, I, as a library author, have better make my code robust and accept non-conforming iterators than whining about the third-party. It's just faster and more efficient.

3. Iterator autonomy argument : Iterator is easily seen as a type that exists to support Sequence. In this case, we'd like Iterator to end for good (finite sequence), or never end (infinite sequence). However, one could argue that Iterator is an autonomous type that happens to support Sequence, but may have other uses, like message queues. In such a context, requiring post-nil guarantees has no meaning.

I'd thus remove the existing precondition, and support the following alternatives:

- the FuseIterator Patrick's proposal (and we could discuss its name).
- a new StoppingIterator protocol which does explicitly provide the post-nil guarantee. Algorithms could then use this guarantee.

• Is the problem being addressed significant enough to warrant a change to Swift?

Yes, because algorithms need guarantees and API contracts. I'm totally with the proposal author here. But I don't think the proposed changes are the right solution.

• If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

This proposal has opened my eyes on a subtle problem with iterators that had not yet bitten me in any language I have used before. Or if it had, I guess just made my code more robust without much second thought.

• How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

The best I could to expose my points :slight_smile:

Gwendal Roué


(Max Moiseev) #4

Hi all,

We discussed the proposal with the members of the standard library team and we tend to +1 it (or +3 if you like).

It does not introduce any new costs to the implementations currently available in the standard library, and even in the case of `TakeWhileIterator` the extra branches are likely to be eliminated by the optimizer.
We also believe that moving the burden of adhering to the API contract from the user of the API to its developer is a valuable change.

max

···

On Apr 28, 2016, at 11:12 AM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Michael Peternell) #5

comments below.

Hello Swift community,

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?

I think it's good

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes, it will demand safe and well-defined behavior from Iterators.

  * Does this proposal fit well with the feel and direction of Swift?

Swift is already a very safe language, and producing undefined behavior if someone calls the iterator too often is not nice. Since most iterators already behave nicely (or maybe all?) this shouldn't be a big issue.

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

not sure

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

I read the proposal.

-Michael

···

Am 28.04.2016 um 20:12 schrieb Chris Lattner via swift-evolution <swift-evolution@swift.org>:


(Lily Ballard) #6

Hello Swift community,

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?

I was originally strongly -1 on this (as can be seen from my previous messages on this ML about this topic), both for the reasons that Gwendal Roué wrote as well as my belief that the vast majority of users never even write code that hits this case at all and my own experience in that it's actually more common for me as an author of a custom Iterator to have to worry about meeting this guarantee than it is for anyone using my Iterator to rely on the behavior.

However, if there really is a 25% speedup on UTF-8 decoding for ASCII input, that's a pretty significant point in favor of the change. I saw the gist that was used to come up with this 25% number. But I do have to ask, does the 25% increase still hold when talking about String.UTF8View, or is that significant speedup only shown when using the UTF8 type to transcode? And similarly, what's the effect on performance for non-ASCII input?

Similarly, do we have any numbers for the effect on performance for a custom Iterator that now has to track state which it otherwise wouldn't? TakeWhileIterator would be a good candidate for testing, except it hasn't been implemented yet (though it shouldn't be hard to whip up a sample implementation for that).

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes. The current defined behavior is pretty much the worst of all options since it encourages library authors to deliberately crash, and yet no stdlib type actually does crash, so it makes it easy to write code that works for stdlib iterators but will fail when given a third-party iterator.

  * Does this proposal fit well with the feel and direction of Swift?

Yes.

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Rust's equivalent Iterator type is defined such that after a previous call to next() has returned None, Iterators are allowed to return either None or Some(Item) from subsequent calls to next() (but shouldn't crash). And Rust has a FuseIterator (and a corresponding .fuse() method). This matches the first alternative in the proposal. And with this approach, it's true that it's extremely rare for people to call .fuse() (but this just demonstrates that very few people write code where post-nil behavior matters), but it does simplify many Iterator implementations, and AFAIK nobody's complained about this behavior.

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

An in-depth study.

-Kevin Ballard

···

On Thu, Apr 28, 2016, at 11:12 AM, Chris Lattner via swift-evolution wrote:


#7

Actually, a StoppingIterator protocol is not a good idea, because this concept should go up the type hierarchy up to Collection in order to let sequence and collection methods use static type information in order to choose the correct iterator algorithm.

I'd prefer a FuseIterator that eventually returns nil forever as soon as it underlying iterator returns nil. Yes, fuseIterator would not apply the "when calling next(), no preceding call to next() should have returned nil" precondition. This precondition would be removed from the Iterator documentation. The FuseIterator would be the easy-going iterator, the one that has no surprise, and makes it easy to write algorithms.

When one needs a "simple" iterator, one just has to derive a FuseIterator from it. Its implementation could look like:

struct FuseIterator<Element> : Iterator {
    let baseNext: () -> Element?
    var ended: Bool = false
    init<I: Iterator where G.Element == Element>(_ baseIterator: I) {
        var baseIterator = baseIterator
        baseNext = { baseIterator.next() }
    }
    mutating func next() -> Element? {
        if ended {
            return nil
        } else if let element = baseNext() {
            return element
        } else {
            ended = true
            return nil
        }
    }
}

We would maybe also need a FuseSequence, in order to iterate a wild base iterator with a `for` loop until its first nil.

Last, forgive my non-native English, but when I look at "fuse" in a Thesaurus, I don't quite see the meaning of "consume until first exhaustion". It looks like any one of "BoundedIterator", "ClosedIterator", "CompactIterator", "TerminatingIterator" would better communicate its nature. "ClosedIterator" looks like the new "ClosedRange" types introduced by SE-0065 and is my current favorite.

Gwendal Roué

···

Le 29 avr. 2016 à 08:18, Gwendal Roué <gwendal.roue@gmail.com> a écrit :

The review of "SE-0052: Change IteratorType post-nil guarantee" begins now and runs through May 3. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md

I'd thus […] support the following alternatives:

- the FuseIterator Patrick's proposal (and we could discuss its name).
- a new StoppingIterator protocol which does explicitly provide the post-nil guarantee. Algorithms could then use this guarantee.


(Patrick Pijnappel) #8

Thanks for the feedback! Some comments:

1. *Obscurity argument*: Both the existing precondition, and the proposed

convention are non-enforceable, non-testable, not well-known enough, and
generally too weak to be efficient in any way. People don't write custom
iterators often enough, and I don't expect those rules to eventually
percolate through Swift culture.

To some degree true, but I'd argue the current guarantee is significantly
more obscure than the proposed alternative:
- All standard library iterators return nil indefinitely.
- Iterators return nil if they're exhausted, i.e. no next element exists.
If I call next() again, it is still exhausted, still no next element
exists, so you'd probably expect it to return nil again.

3. *Iterator autonomy argument* : Iterator is easily seen as a type that

exists to support Sequence. In this case, we'd like Iterator to end for
good (finite sequence), or never end (infinite sequence). However, one
could argue that Iterator is an autonomous type that happens to support
Sequence, but may have other uses, like message queues. In such a context,
requiring post-nil guarantees has no meaning.

IteratorProtocol does explicitly describe itself as iterating over a
sequence though:
/// A type that supplies the values of a sequence one at a time.
I'm not sure IteratorProtocol is intended to be used for such cases (where
the sequence changes length underneath). If it is, we could consider
changing the guarantee to return nil as long as the underlying sequence is
empty (i.e. allowing restarts). It's worth noting too that the current
guarantee also doesn't support sequences changing length.

···

On Fri, Apr 29, 2016 at 2:40 PM, Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

> * What is your evaluation of the proposal?

I think it's a good idea.

This is a particularly sharp edge in the standard library: people have a
completely reasonable expectation about `next()`'s behavior which is
usually, but not always, borne out. And the vast majority of iterators can
provide this feature for free. Only a few would pay any price, and that
price would be minimal—it could easily be the cheapest statements in the
method.

Nor do I think the FuseIterator solution will actually help. If you know
about FuseIterator, you don't really need it, because you know about
`next()`'s nil behavior and can code around it. This is an attempt to
protect the people who *don't* know about the problem.

There are languages so averse to trading anything for efficiency that they
refuse to provide simple improvements to help with these kinds of issues. I
don't think Swift should be one of them.

> * Is the problem being addressed significant enough to warrant a
change to Swift?

Yes.

> * Does this proposal fit well with the feel and direction of Swift?

I think so. One of the major themes of Swift 3 is cleaning up the standard
library.

> * If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?

I haven't, but some of the previous discussions on this issue have brought
up Rust, which uses the FuseIterator solution. It seems like a pretty lousy
one to me.

> * How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?

Quick reading this time, but I participated the previous discussion.

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Patrick Pijnappel) #9

However, if there really is a 25% speedup on UTF-8 decoding for ASCII
input, that's a pretty significant point in favor of the change. I saw the
gist that was used to come up with this 25% number. But I do have to ask,
does the 25% increase still hold when talking about String.UTF8View, or is
that significant speedup only shown when using the UTF8 type to transcode?
And similarly, what's the effect on performance for non-ASCII input?

The mentioned results are for decoding, i.e. UTF8 in, while UTF8View is
about transcoding/encoding, i.e. UTF8 out. But any thin wrapper around UTF8
decode (e.g. String(cString:)) should see basically the same speed-ups. I
haven't tested UTF16 decode, but the code path for all non-surrogates is
very similar to UTF8's ASCII decode and should the same similar gains –
which should translate directly into gains for e.g. iterating over a
UnicodeScalarView.

As for non-ascii input, the extra branch is a smaller slice of the total,
making the speed-up ~10%.

Similarly, do we have any numbers for the effect on performance for a

custom Iterator that now has to track state which it otherwise wouldn't?
TakeWhileIterator would be a good candidate for testing, except it hasn't
been implemented yet (though it shouldn't be hard to whip up a sample
implementation for that).

In the common cases I tested so far (where post-nil isn't used) the branch
is optimized away, but probably you could thwart the optimizer somehow. The
performance hit then would be likely be (very) roughly speaking the 1 over
the total number of branches in the loop.

···

On Tue, May 3, 2016 at 8:24 AM, Kevin Ballard via swift-evolution < swift-evolution@swift.org> wrote:

On Thu, Apr 28, 2016, at 11:12 AM, Chris Lattner via swift-evolution wrote:
> Hello Swift community,
>
> The review of "SE-0052: Change IteratorType post-nil guarantee" begins
now and runs through May 3. The proposal is available here:
>
>
https://github.com/apple/swift-evolution/blob/master/proposals/0052-iterator-post-nil-guarantee.md
>
> Reviews are an important part of the Swift evolution process. All
reviews should be sent to the swift-evolution mailing list at
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> or, if you would like to keep your feedback private, directly to the
review manager.
>
> What goes into a review?
>
> The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:
>
> * What is your evaluation of the proposal?

I was originally strongly -1 on this (as can be seen from my previous
messages on this ML about this topic), both for the reasons that Gwendal
Roué wrote as well as my belief that the vast majority of users never even
write code that hits this case at all and my own experience in that it's
actually more common for me as an author of a custom Iterator to have to
worry about meeting this guarantee than it is for anyone using my Iterator
to rely on the behavior.

However, if there really is a 25% speedup on UTF-8 decoding for ASCII
input, that's a pretty significant point in favor of the change. I saw the
gist that was used to come up with this 25% number. But I do have to ask,
does the 25% increase still hold when talking about String.UTF8View, or is
that significant speedup only shown when using the UTF8 type to transcode?
And similarly, what's the effect on performance for non-ASCII input?

Similarly, do we have any numbers for the effect on performance for a
custom Iterator that now has to track state which it otherwise wouldn't?
TakeWhileIterator would be a good candidate for testing, except it hasn't
been implemented yet (though it shouldn't be hard to whip up a sample
implementation for that).

> * Is the problem being addressed significant enough to warrant a
change to Swift?

Yes. The current defined behavior is pretty much the worst of all options
since it encourages library authors to deliberately crash, and yet no
stdlib type actually does crash, so it makes it easy to write code that
works for stdlib iterators but will fail when given a third-party iterator.

> * Does this proposal fit well with the feel and direction of Swift?

Yes.

> * If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?

Rust's equivalent Iterator type is defined such that after a previous call
to next() has returned None, Iterators are allowed to return either None or
Some(Item) from subsequent calls to next() (but shouldn't crash). And Rust
has a FuseIterator (and a corresponding .fuse() method). This matches the
first alternative in the proposal. And with this approach, it's true that
it's extremely rare for people to call .fuse() (but this just demonstrates
that very few people write code where post-nil behavior matters), but it
does simplify many Iterator implementations, and AFAIK nobody's complained
about this behavior.

> * How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?

An in-depth study.

-Kevin Ballard
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution