[Review] SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++


(Chris Lattner) #1

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.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 contribute to 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 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


Blasts from the past: algorithms
(Matthew Johnson) #2

   * What is your evaluation of the proposal?

+1. I'm pleased to see an important foundational algorithm added to the standard library.

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

Yes. We should have a standard, shared implementation of as many generally useful algorithms as possible, especially those whose implementation is no trivial.

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

Yes

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

As noted in the proposal, it is inspired by STL, which is a very good source of inspiration for generic algorithms.

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

Quick read of the specific details of the proposal, informed by general familiarity with generic programming and the rotate algorithm.

···

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-announce mailing list
swift-evolution-announce@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution-announce


(Dmitri Gribenko) #3

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

Could you add complexity clauses to all new documentation comments?

We have discussed the names for these functions at length. We felt
like the argument in 'rotate(firstFrom:)' does not convey the
argument's role well. Our suggestion is to use
'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'. These
names emphasize that methods operate on the whole collection, shifting
all elements. The argument is the index of the element that is moved
to the start index, and we tried to convey that by using the word
'start' instead of 'first'. In the standard library, 'first' refers
to the element itself, not the index. Indices use 'startIndex' and
'endIndex'.

We have considered a lot of alternative names, including
'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
and others, but they were not as good. The problems are:

- 'swapSubranges' is mostly good, but 'subranges' does not imply that
the two subranges cover the whole collection. The user might
reasonably expect to pass two subranges that will be swapped.

- 'Half' implies that two parts make a whole, but it also implies that
two parts are of equal size, which is not the case for this API.

- 'splitAndSwap' implies that we are operating on the whole, but feels
a very roundabout way to describe the operation.

For a non-mutating rotation we suggest defining separate types,
RotatedCollection, RotatedBidirectionalCollection, and
RotatedRandomAccessCollection, instead of returning a
FlattenCollection. This has a few advantages.

- We can change the non-mutating 'rotated()' to just return the
collection instead of returning tuples of the collection and the
index. The index of the former first element can be stored inside the
RotatedCollection in a property. This change allows easier chaining
on '.rotated()', and goes in line with the return value of the
mutating 'rotate()' being discardable.

- Using an array in the return type of 'rotated()'
(FlattenCollection<[Self.SubSequence]>) would be less efficient than
it could be (extra allocation), and also feels like exposing too many
implementation details that we might want to change in future (for
example, if we get a CollectionOfTwo type).

- In future, when we have conditional protocol conformances in the
language, we would fold the three RotatedCollection types into one
type that conditionally conforms to collection protocols based on the
capabilities of the underlying collection. We won't be able to do
that if some overloads return a FlattenCollection.

For lazy 'rotated()', just like for non-mutating 'rotated()', we
recommend returning only one value, a LazyCollection that wraps an
appropriate RotatedCollection. The RotatedCollection will store the
index of the former first element in a property.

Dmitri

···

On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


Blasts from the past: algorithms
(Nate Cook) #4

Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

With a bidirectional collection, you have to compare the high and low index at each iteration, stopping when low >= high (before indices were Comparable, this required two equality comparisons per iteration). With a random-access collection, you can optimize the loop to use a fixed number of iterations, which should be more efficient.

Could you add complexity clauses to all new documentation comments?

We have discussed the names for these functions at length. We felt
like the argument in 'rotate(firstFrom:)' does not convey the
argument's role well. Our suggestion is to use
'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'. These
names emphasize that methods operate on the whole collection, shifting
all elements. The argument is the index of the element that is moved
to the start index, and we tried to convey that by using the word
'start' instead of 'first'. In the standard library, 'first' refers
to the element itself, not the index. Indices use 'startIndex' and
'endIndex'.

We have considered a lot of alternative names, including
'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
and others, but they were not as good. The problems are:

- 'swapSubranges' is mostly good, but 'subranges' does not imply that
the two subranges cover the whole collection. The user might
reasonably expect to pass two subranges that will be swapped.

- 'Half' implies that two parts make a whole, but it also implies that
two parts are of equal size, which is not the case for this API.

- 'splitAndSwap' implies that we are operating on the whole, but feels
a very roundabout way to describe the operation.

Agreed on all of this. The rotate name is hard to beat!

···

On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution > <swift-evolution@swift.org> wrote:

For a non-mutating rotation we suggest defining separate types,
RotatedCollection, RotatedBidirectionalCollection, and
RotatedRandomAccessCollection, instead of returning a
FlattenCollection. This has a few advantages.

- We can change the non-mutating 'rotated()' to just return the
collection instead of returning tuples of the collection and the
index. The index of the former first element can be stored inside the
RotatedCollection in a property. This change allows easier chaining
on '.rotated()', and goes in line with the return value of the
mutating 'rotate()' being discardable.

- Using an array in the return type of 'rotated()'
(FlattenCollection<[Self.SubSequence]>) would be less efficient than
it could be (extra allocation), and also feels like exposing too many
implementation details that we might want to change in future (for
example, if we get a CollectionOfTwo type).

- In future, when we have conditional protocol conformances in the
language, we would fold the three RotatedCollection types into one
type that conditionally conforms to collection protocols based on the
capabilities of the underlying collection. We won't be able to do
that if some overloads return a FlattenCollection.

For lazy 'rotated()', just like for non-mutating 'rotated()', we
recommend returning only one value, a LazyCollection that wraps an
appropriate RotatedCollection. The RotatedCollection will store the
index of the former first element in a property.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


Blasts from the past: algorithms
(Dmitri Gribenko) #5

Good point! In that case, 'reverse()' should also be a protocol
requirement, to allow dispatch to the most efficient version.

Dmitri

···

On Thu, May 5, 2016 at 5:11 PM, Nate Cook <natecook@gmail.com> wrote:

Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.

On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution >> <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

With a bidirectional collection, you have to compare the high and low index at each iteration, stopping when low >= high (before indices were Comparable, this required two equality comparisons per iteration). With a random-access collection, you can optimize the loop to use a fixed number of iterations, which should be more efficient.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dave Abrahams) #6

Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

With a bidirectional collection, you have to compare the high and low
index at each iteration, stopping when low >= high (before indices
were Comparable, this required two equality comparisons per
iteration). With a random-access collection, you can optimize the loop
to use a fixed number of iterations, which should be more efficient.

How can you reverse a variable-length collection with a fixed number of
iterations? Are you talking about loop unrolling in the library?

···

on Thu May 05 2016, Nate Cook <swift-evolution@swift.org> wrote:

On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution >> <swift-evolution@swift.org> wrote:

Could you add complexity clauses to all new documentation comments?

We have discussed the names for these functions at length. We felt
like the argument in 'rotate(firstFrom:)' does not convey the
argument's role well. Our suggestion is to use
'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'. These
names emphasize that methods operate on the whole collection, shifting
all elements. The argument is the index of the element that is moved
to the start index, and we tried to convey that by using the word
'start' instead of 'first'. In the standard library, 'first' refers
to the element itself, not the index. Indices use 'startIndex' and
'endIndex'.

We have considered a lot of alternative names, including
'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
and others, but they were not as good. The problems are:

- 'swapSubranges' is mostly good, but 'subranges' does not imply that
the two subranges cover the whole collection. The user might
reasonably expect to pass two subranges that will be swapped.

- 'Half' implies that two parts make a whole, but it also implies that
two parts are of equal size, which is not the case for this API.

- 'splitAndSwap' implies that we are operating on the whole, but feels
a very roundabout way to describe the operation.

Agreed on all of this. The rotate name is hard to beat!

For a non-mutating rotation we suggest defining separate types,
RotatedCollection, RotatedBidirectionalCollection, and
RotatedRandomAccessCollection, instead of returning a
FlattenCollection. This has a few advantages.

- We can change the non-mutating 'rotated()' to just return the
collection instead of returning tuples of the collection and the
index. The index of the former first element can be stored inside the
RotatedCollection in a property. This change allows easier chaining
on '.rotated()', and goes in line with the return value of the
mutating 'rotate()' being discardable.

- Using an array in the return type of 'rotated()'
(FlattenCollection<[Self.SubSequence]>) would be less efficient than
it could be (extra allocation), and also feels like exposing too many
implementation details that we might want to change in future (for
example, if we get a CollectionOfTwo type).

- In future, when we have conditional protocol conformances in the
language, we would fold the three RotatedCollection types into one
type that conditionally conforms to collection protocols based on the
capabilities of the underlying collection. We won't be able to do
that if some overloads return a FlattenCollection.

For lazy 'rotated()', just like for non-mutating 'rotated()', we
recommend returning only one value, a LazyCollection that wraps an
appropriate RotatedCollection. The RotatedCollection will store the
index of the former first element in a property.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

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

--
Dave


(Nate Cook) #7

Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

With a bidirectional collection, you have to compare the high and low index at each iteration, stopping when low >= high (before indices were Comparable, this required two equality comparisons per iteration). With a random-access collection, you can optimize the loop to use a fixed number of iterations, which should be more efficient.

Good point! In that case, 'reverse()' should also be a protocol
requirement, to allow dispatch to the most efficient version.

That brings up the question of which protocol to add the requirement to? Without a MutableBidirectionalProtocol (which we don't want, right?), we'd need to add it to MutableCollection. While a mutating reverse() is possible for a forward collection, it has significant space complexity, since it works either by creating an array of the indices or through recursion. We would also have reverse() available on some collections that don't have reversed(). Does that sound alright?

···

On May 6, 2016, at 12:35 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Thu, May 5, 2016 at 5:11 PM, Nate Cook <natecook@gmail.com <mailto:natecook@gmail.com>> wrote:

On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution >>> <swift-evolution@swift.org> wrote:

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>>*/


(Nate Cook) #8

Thanks for the feedback, Dmitri &co, this all looks excellent! I'll work on updating the proposal.

Hello Swift community,

The review of "SE-0078: Implement a rotate algorithm, equivalent to std::rotate() in C++" begins now and runs through May 9.

Hi,

I'm posting this feedback on behalf of Dave Abrahams, Max Moiseev and
myself. We met and discussed the proposal in great detail.

First of all, we want to thank Nate and Sergey for proposing this API,
which is an important and useful algorithm. We are generally in favor
of the proposal, but we would like to request a few changes.

Could you make 'func rotate' a requirement in the MutableCollection
protocol? This allows selecting the best implementation for a given
concrete type, even when calling from generic code.

Could you explain why do we need a special implementation of
'reverse()' for RandomAccessCollection? We couldn't think of a
performance reason for this.

With a bidirectional collection, you have to compare the high and low
index at each iteration, stopping when low >= high (before indices
were Comparable, this required two equality comparisons per
iteration). With a random-access collection, you can optimize the loop
to use a fixed number of iterations, which should be more efficient.

How can you reverse a variable-length collection with a fixed number of
iterations? Are you talking about loop unrolling in the library?

I mean looping count / 2 times instead of looping while lowIndex < highIndex, not a fixed number of iterations for every array.

···

On May 6, 2016, at 3:18 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Thu May 05 2016, Nate Cook <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On May 5, 2016, at 6:13 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Tue, May 3, 2016 at 8:57 PM, Chris Lattner via swift-evolution >>> <swift-evolution@swift.org> wrote:

Could you add complexity clauses to all new documentation comments?

We have discussed the names for these functions at length. We felt
like the argument in 'rotate(firstFrom:)' does not convey the
argument's role well. Our suggestion is to use
'rotate(shiftingToStart:)' and 'rotated(shiftingToStart:)'. These
names emphasize that methods operate on the whole collection, shifting
all elements. The argument is the index of the element that is moved
to the start index, and we tried to convey that by using the word
'start' instead of 'first'. In the standard library, 'first' refers
to the element itself, not the index. Indices use 'startIndex' and
'endIndex'.

We have considered a lot of alternative names, including
'swapSubranges(boundedBy:)', 'rewind', 'splitAndSwap', 'swapHalves'
and others, but they were not as good. The problems are:

- 'swapSubranges' is mostly good, but 'subranges' does not imply that
the two subranges cover the whole collection. The user might
reasonably expect to pass two subranges that will be swapped.

- 'Half' implies that two parts make a whole, but it also implies that
two parts are of equal size, which is not the case for this API.

- 'splitAndSwap' implies that we are operating on the whole, but feels
a very roundabout way to describe the operation.

Agreed on all of this. The rotate name is hard to beat!

For a non-mutating rotation we suggest defining separate types,
RotatedCollection, RotatedBidirectionalCollection, and
RotatedRandomAccessCollection, instead of returning a
FlattenCollection. This has a few advantages.

- We can change the non-mutating 'rotated()' to just return the
collection instead of returning tuples of the collection and the
index. The index of the former first element can be stored inside the
RotatedCollection in a property. This change allows easier chaining
on '.rotated()', and goes in line with the return value of the
mutating 'rotate()' being discardable.

- Using an array in the return type of 'rotated()'
(FlattenCollection<[Self.SubSequence]>) would be less efficient than
it could be (extra allocation), and also feels like exposing too many
implementation details that we might want to change in future (for
example, if we get a CollectionOfTwo type).

- In future, when we have conditional protocol conformances in the
language, we would fold the three RotatedCollection types into one
type that conditionally conforms to collection protocols based on the
capabilities of the underlying collection. We won't be able to do
that if some overloads return a FlattenCollection.

For lazy 'rotated()', just like for non-mutating 'rotated()', we
recommend returning only one value, a LazyCollection that wraps an
appropriate RotatedCollection. The RotatedCollection will store the
index of the former first element in a property.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

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

--
Dave

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


(Dmitri Gribenko) #9

Good question! I don't think we should provide reverse() on forward
collections.

I think we can play some tricks here. We can add an underscored
_customReverse() requirement to MutableCollection, a default
implementation that traps, and two specialized implementations for
forward and bidirectional collections. We would then add a protocol
extension (not a requirement) reverse() on MutableCollection where
Self : BidirectionalCollection that will call _customReverse().

Dmitri

···

On Fri, May 6, 2016 at 12:53 AM, Nate Cook <natecook@gmail.com> wrote:

That brings up the question of which protocol to add the requirement to?
Without a MutableBidirectionalProtocol (which we don't want, right?), we'd
need to add it to MutableCollection. While a mutating reverse() is possible
for a forward collection, it has significant space complexity, since it
works either by creating an array of the indices or through recursion. We
would also have reverse() available on some collections that don't have
reversed(). Does that sound alright?

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dave Abrahams) #10

Why do you think that will be faster?

···

on Fri May 06 2016, Nate Cook <natecook-AT-gmail.com> wrote:

    How can you reverse a variable-length collection with a fixed number of
    iterations? Are you talking about loop unrolling in the library?

I mean looping count / 2 times instead of looping while lowIndex <
highIndex,

--
Dave


(Nate Cook) #11

   How can you reverse a variable-length collection with a fixed number of
   iterations? Are you talking about loop unrolling in the library?

I mean looping count / 2 times instead of looping while lowIndex <
highIndex,

Why do you think that will be faster?

I don't know what kinds of optimization the compiler performs, but it certainly seems more open to optimization. Barring that, it removes the custom index comparison, which certainly couldn't be faster than checking for the end of a loop.

If it's not an improvement over the bidirectional algorithm, let's leave it out. Then we could skip the customization method and only have reverse() as an extension to BidirectionalCollection.

Nate

···

On May 6, 2016, at 4:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Fri May 06 2016, Nate Cook <natecook-AT-gmail.com> wrote:

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


(Dave Abrahams) #12

   How can you reverse a variable-length collection with a fixed number of
   iterations? Are you talking about loop unrolling in the library?

I mean looping count / 2 times instead of looping while lowIndex <
highIndex,

Why do you think that will be faster?

I don't know what kinds of optimization the compiler performs, but it
certainly seems more open to optimization. Barring that, it removes
the custom index comparison, which certainly couldn't be faster than
checking for the end of a loop.

When the collection has a trivial index with random access, the compiler
should be able to optimize the loop in all kinds of ways. IMO putting
this kind of optimization in the library is at the very least premature
without both testing to prove it's slower and talking with the optimizer
people to make sure they can't handle it at that level.

If it's not an improvement over the bidirectional algorithm, let's
leave it out. Then we could skip the customization method and only
have reverse() as an extension to BidirectionalCollection.

IMO the cost of reverse() is going to be dominated by data copying, and
the chance of index comparison showing up as significant is very low.
But it's all speculation. When there's no Big-O difference involved,
it's hard to justify introducing any complexity for an as-yet unobserved
performance increase.

···

on Fri May 06 2016, Nate Cook <nate-AT-natecook.com> wrote:

On May 6, 2016, at 4:20 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Fri May 06 2016, Nate Cook <natecook-AT-gmail.com> wrote:

--
Dave