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

[Dave Abrahams]

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 at swift.org> wrote:
>> 
>>> 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,
>> 
>> 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.

-- 
Dave