[swift-evolution] Improvement proposal: change overflow behavior in successor()/predecessor() methods for Int types

[Dave Abrahams]

on Mon Apr 25 2016, Haravikk <swift-evolution-AT-haravikk.me> wrote:

>     On 25 Apr 2016, at 22:53, Dave Abrahams via swift-evolution
>     <swift-evolution at swift.org> wrote:
>
>     on Sat Apr 23 2016, Haravikk <swift-evolution at swift.org> wrote:
>
>         On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution
>         <swift-evolution at swift.org> wrote:
>
>         On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>         <swift-evolution at swift.org> wrote:
>
>         But. .successor() .predecessor() methods for Int values do not follow
>         these
>         rules for overflow situations. I.e. :
>         let i : Int8 = Int8.max
>         let k : Int8 = i.successor()
>         - is OK for current Swift compiler. We have i==127 and k==-128, no
>         run-time
>         error.
>
>         This was done for performance reasons. Array's indices are Ints, and
>         adding an overflow check here was causing significant performance
>         issues when iterating over arrays.
>
>         Sorry to bump this after it’s been idle for a little while, but I was
>         thinking
>         about this again recently and I can’t come up with a test that verifies
>         a
>         meaningful performance difference. I just threw the following into a
>         playground:
>
>         import Foundation
>
>         do {
>         let startTime = NSDate().timeIntervalSince1970
>         var i = 0
>         while i < 1000000 { i = i &+ 1 }
>         let elapsed = NSDate().timeIntervalSince1970 - startTime
>         }
>
>         do {
>         let startTime = NSDate().timeIntervalSince1970
>         var i = 0
>         while i < 1000000 { i = i + 1 }
>         let elapsed = NSDate().timeIntervalSince1970 - startTime
>         }
>
>         My results come out with no discernible performance difference; 
>
>     I wouldn't be surprised if these examples compiled down to exactly the
>     same code because the compiler can hoist the overflow checks out of the
>     loop. 
>
> I don’t know how that would work exactly, or do you mean it can calculate before
> the loop that the value will never overflow?

Exactly.

>     Try doing the same thing with a sort or a binary search if you
>     want to experience the difference
>
> I tested two versions of a binary search algorithm, one calculating the
> mid-point using arithmetic with overflow checking and one without, and again
> both give performance that’s effectively identical. Can you give a concrete
> example of code that demonstrates the difference?

Not I.  Perhaps some of our performance gurus will chime in with the answer.  Or,
perhaps they'll tell us this optimization has become obsolete.

> Still, even if for sorting it makes a big difference to sorting then surely
> that’s an argument for arrays to have their own sorting implementation with
> unsafe arithmetic used internally, rather than changing predecessor/successor?

-- 
Dave