[Proposal] Change some collection iterators to use custom types instead of IndexIterator<T>


(Michael Gottesman) #1

Hello everyone!

Iterators are very important for performance since we use them for for loops. By default collections if they do not provide a custom iterator use IndexingIterator as an iterator. IndexingIterator, while only supporting forward movement, is based on indices which possess the ability to go backwards and forwards. For some indices, backwards iteration adds unnecessary cost/complexity.
In order to preserve future flexibility, we want to change certain of the types to use custom types that are essentially just IndexingIterator<T>. Then later on when we want to implement these optimizations, we can do it on the custom type underneath the hood without changing the API/ABI.

The reason I use the phrase "some iterators" is that I already know that we definitely want to do this for StringCharacterView but there are potentially other containers in the standard library that this could apply to. I still need to audit these containers for potential applications. That being said given the place where we are in the schedule, I think it is important to start the discussion about the general concept and after I audit the various containers, I will post an update.

Thoughts, flames, etc?
Michael

https://bugs.swift.org/browse/SR-1961


(Xiaodi Wu) #2

(thumbs up)

···

On Fri, Jul 22, 2016 at 4:35 PM, Michael Gottesman via swift-evolution < swift-evolution@swift.org> wrote:

Hello everyone!

Iterators are very important for performance since we use them for for
loops. By default collections if they do not provide a custom iterator use
IndexingIterator as an iterator. IndexingIterator, while only supporting
forward movement, is based on indices which possess the ability to go
backwards and forwards. For some indices, backwards iteration adds
unnecessary cost/complexity.
In order to preserve future flexibility, we want to change certain of the
types to use custom types that are essentially just IndexingIterator<T>.
Then later on when we want to implement these optimizations, we can do it
on the custom type underneath the hood without changing the API/ABI.

The reason I use the phrase "some iterators" is that I already know that
we definitely want to do this for StringCharacterView but there are
potentially other containers in the standard library that this could apply
to. I still need to audit these containers for potential applications. That
being said given the place where we are in the schedule, I think it is
important to start the discussion about the general concept and after I
audit the various containers, I will post an update.

Thoughts, flames, etc?
Michael

https://bugs.swift.org/browse/SR-1961
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Michael Gottesman) #3

Submitted the following PR:

https://github.com/apple/swift-evolution/pull/469

Michael

···

On Jul 22, 2016, at 2:35 PM, Michael Gottesman via swift-evolution <swift-evolution@swift.org> wrote:

Hello everyone!

Iterators are very important for performance since we use them for for loops. By default collections if they do not provide a custom iterator use IndexingIterator as an iterator. IndexingIterator, while only supporting forward movement, is based on indices which possess the ability to go backwards and forwards. For some indices, backwards iteration adds unnecessary cost/complexity.
In order to preserve future flexibility, we want to change certain of the types to use custom types that are essentially just IndexingIterator<T>. Then later on when we want to implement these optimizations, we can do it on the custom type underneath the hood without changing the API/ABI.

The reason I use the phrase "some iterators" is that I already know that we definitely want to do this for StringCharacterView but there are potentially other containers in the standard library that this could apply to. I still need to audit these containers for potential applications. That being said given the place where we are in the schedule, I think it is important to start the discussion about the general concept and after I audit the various containers, I will post an update.

Thoughts, flames, etc?
Michael

https://bugs.swift.org/browse/SR-1961
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution