Improvement proposal: change overflow behavior in successor()/predecessor() methods for Int types

Evolution Discussion
1

Hi All!
(Please let me know if that was already discussed. Searched, found nothing related to such proposal.)

(TLDR: Suggest to change successor() method for Int values to follow default Swift rules for integer overflow. Probably some kind of successorWithOverflow could be introduced to use when needed)

Swift protects(trying to protect) us from Integer overflow problem, i.e. when we want to do this:
let i : Int8 = Int8.max
let k : Int8 = i + 1
, we will have run-time error on second line. Swift protects us from using (most likely) unexpected negative value (-128) for <k> variable in this case.

I believe this is really great and prevents our code from undefined behavior and some security problems.
When we adds something to our Int variable in most cases we presume(and create next code with that presumption) that in result we have a bigger value in our variable. Not smaller and not negative(in case of signed Int).

If we really needs Integer overflow in our code(for example for some math), we use special operator explicitly:
let k = i &+ 1
and in this case we'll have -128 in <k> with no errors.

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.

I'm totally confused in this case. No explicit 'marker' to allow integer overflow. I don't expect to have (-128) in k, I'm calling successor() to get next mathematical value for <i> and (-128) is not next value for (127).

Even worse. In Swift 3.0 we have no ++ operator. You can find that often .successor/.predecessor are recommended as replacement for ++ operator.
I.e. i++ => i.successor(), I believe that many will choose this form over i += 1 or i + 1. And in this case we lose our integer overflow protection from Swift.

Suggestion is: change .successor/.predecessor for Int values to follow overflow rules and probable introduce some .successorWithOverflow/.predecessorWithOverflow if one need them in code.

Please let me know what do you think about this suggestion. Thank you.

P.S. Sorry for my English.

(Btw, I personally totally disagree with the chosen solution regarding removing ++/--, I believe that we should leave ++ and -- as form of i += 1 code. I.e. only as assignment for variable, drop all other variants of using ++ and --.
And i += 1 is not just 1 char longer than i++ : in first case you have to press 4 different keys/combinations and just one(the same twice) in second case.
Just personal opinion :-) )

Vladimir.S

2

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. These methods were not designed to
be used in contexts other than indices. When ints are used as
indices, doing an overflow check in successor() does not prevent any
mistakes, since Array's bounds are always tighter than
Int.min...Int.max.

These methods are going away in the new indexing model.
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160229/011552.html

Dmitri

···

On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution <swift-evolution@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.

--
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>*/

3

(TLDR: Suggest to change successor() method for Int values to follow default Swift rules for integer overflow. Probably some kind of successorWithOverflow could be introduced to use when needed)

I’m a +1 for this; in fact, this is just how I assumed they worked, as the postcondition requirement for .successor() is that n.successor() > n if I remember right, which clearly can’t be the case if the limit of the integer is reached, so a runtime error seems reasonable.

(Btw, I personally totally disagree with the chosen solution regarding removing ++/--, I believe that we should leave ++ and -- as form of i += 1 code. I.e. only as assignment for variable, drop all other variants of using ++ and --.
And i += 1 is not just 1 char longer than i++ : in first case you have to press 4 different keys/combinations and just one(the same twice) in second case.
Just personal opinion :-) )

These were removed for a bunch of reasons:
Requiring the use of += 1 or -=1 is more consistent (assignment always includes an equals sign)
It can easily lead to confusing cases when used in function parameters or complex statements, making it unclear at a glance what a value will actually be. Some people argued that the operator should just have no return type to counter this.
If the operator had no return type to address #2 then it basically becomes redundant when i += 1 is identical, but also more flexible.
They were most commonly used within C-style for loops, which Swift no longer has.
So I’m a -1 to anyone wanting those back ;)

···

On 7 Apr 2016, at 08:20, Vladimir.S via swift-evolution <swift-evolution@swift.org> wrote:

4

This is exactly why I think successor()/predecessor() must raise runtime error on integer overflow - because we(I believe) expect this behavior from these funcs.
For example, someone, who don't know about current behavior of these methods, can use them to increment/decrement index for some collection/array and so produce hard-to-find errors or vulnerable code.

Any other opinion on this proposal please?

···

On 07.04.2016 14:31, Haravikk wrote:

On 7 Apr 2016, at 08:20, Vladimir.S via swift-evolution >> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

(TLDR: Suggest to change successor() method for Int values to follow
default Swift rules for integer overflow. Probably some kind of
successorWithOverflow could be introduced to use when needed)

I’m a +1 for this; in fact, this is just how I assumed they worked, as the
postcondition requirement for .successor() is that n.successor() > n if I
remember right, which clearly can’t be the case if the limit of the integer
is reached, so a runtime error seems reasonable.

5

OK, thank you for the clarification Dmitri.
If these methods are going away - no possible problems :-)
Will we have some kind of .next() method for integers in new indexing model and in Swift 3.0 in general?

(But actually I don't agree that there is all OK with these functions in current version of Swift. "Not designed" - understand, but they can be used(so they will! be used) "out of the box", even Int8 has these methods,
Int32.max is just 2GB for [Int8] etc..
Yes, in case of using successor() only with Int64 only for indices of Array - all looks like OK.)

···

On 07.04.2016 20:54, Dmitri Gribenko wrote:

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. These methods were not designed to
be used in contexts other than indices. When ints are used as
indices, doing an overflow check in successor() does not prevent any
mistakes, since Array's bounds are always tighter than
Int.min...Int.max.

These methods are going away in the new indexing model.
[swift-evolution] [RFC] New collections model: collections advance indices

Dmitri

6

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 suspect that this a side-effect of the iteration and storing overhead, but it seems to me that this is the kind of minimum boilerplate you are going to have anyway if you’re using .successor(). I know the issue is specifically with array iteration, but I don’t believe I actually need an array involved to demonstrate this, in fact the extra overhead would make the difference even less noticeable.

Is there a test that can demonstrate a more extreme difference? Even so, if the issue is with array iteration then it seems that the best place to fix that is in the array’s generator, rather than using the more generic IndexingGenerator that has no awareness of the underlying index type.

···

On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution > <swift-evolution@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.

7

OK, thank you for the clarification Dmitri.
If these methods are going away - no possible problems :-)
Will we have some kind of .next() method for integers in new indexing model
and in Swift 3.0 in general?

There would be no need to. Collection will have a .successor(of:)
method that returns the next index after the given one.

(But actually I don't agree that there is all OK with these functions in
current version of Swift. "Not designed" - understand, but they can be
used(so they will! be used) "out of the box", even Int8 has these methods,
Int32.max is just 2GB for [Int8] etc..
Yes, in case of using successor() only with Int64 only for indices of Array
- all looks like OK.)

I can see that, but when you know that you are dealing with an
integer, isn't "+ 1" a more common and readable notation?

Dmitri

···

On Thu, Apr 7, 2016 at 11:27 AM, Vladimir.S <svabox@gmail.com> wrote:

--
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>*/

8

There would be no need to. Collection will have a .successor(of:)
method that returns the next index after the given one.

I see. Thank you for letting know about this.

I can see that, but when you know that you are dealing with an
integer, isn't "+ 1" a more common and readable notation?

Hmm.. I believe that i++ is muuuch common used than i += 1 ;-)

Personally I totally agree with almost all reasons why we should drop these ++/--, but until this moment I was not agree that operator(not expression) i++ (i.e. operator to increase i to 1 that do not return any value) produces any problem in code. And it is so common in programming word, in c/c++ which we will(!) use with our Swift code often, so it can't produce any misunderstanding like "what does this "i++" line do??"
(again, just operator, like: if something { someInt++ } )

But now, I was pointed that someInt += 1 is better because of this "=" char in operator i.e. we clearly say that we will assign the value to variable, mutate it.
And I think this makes the language better, so right now I fully support the decision to remove ++/--

So.. Thank you for your time and your replies :-)

Vladimir.

···

On 07.04.2016 21:43, Dmitri Gribenko wrote:

9

    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. Try doing the same thing with a sort or a binary search if you
want to experience the difference

···

on Sat Apr 23 2016, Haravikk <swift-evolution@swift.org> wrote:

    On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution > <swift-evolution@swift.org> wrote:
    On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution > <swift-evolution@swift.org> wrote:

I suspect that this a side-effect of the iteration and storing
overhead, but it seems to me that this is the kind of minimum
boilerplate you are going to have anyway if you’re using
.successor(). I know the issue is specifically with array iteration,
but I don’t believe I actually need an array involved to demonstrate
this, in fact the extra overhead would make the difference even less
noticeable.

Is there a test that can demonstrate a more extreme difference? Even so, if the
issue is with array iteration then it seems that the best place to fix that is
in the array’s generator, rather than using the more generic IndexingGenerator
that has no awareness of the underlying index type.

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

--
Dave

10

The reason why I said "+ 1" is because this discussion is about
Int.successor(), which returns a new Int rather than mutating it in
place. So i++ and i += 1 are not direct replacements for
Int.successor().

Dmitri

···

On Fri, Apr 8, 2016 at 3:49 AM, Vladimir.S <svabox@gmail.com> wrote:

On 07.04.2016 21:43, Dmitri Gribenko wrote:

There would be no need to. Collection will have a .successor(of:)
method that returns the next index after the given one.

I see. Thank you for letting know about this.

I can see that, but when you know that you are dealing with an
integer, isn't "+ 1" a more common and readable notation?

Hmm.. I believe that i++ is muuuch common used than i += 1 ;-)

--
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>*/

11

   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?

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?

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?

···

On 25 Apr 2016, at 22:53, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Sat Apr 23 2016, Haravikk <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

   On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution >> <swift-evolution@swift.org> wrote:
   On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution >> <swift-evolution@swift.org> wrote:

12

        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.

···

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@swift.org> wrote:
    on Sat Apr 23 2016, Haravikk <swift-evolution@swift.org> wrote:
        On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution > <swift-evolution@swift.org> wrote:
        On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution > <swift-evolution@swift.org> wrote:

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

13

To answer this specific question, the optimizer will remove the overflow check whenever it proves impossible to fire. The example above has constant loop bounds, so obviously the optimizer can remove the check. In many cases it can’t, but as Dmitri pointed out, the bounds check is strictly narrower so there’s no reason to do both.

-Andy

···

On Apr 25, 2016, at 4:19 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

   on Sat Apr 23 2016, Haravikk <swift-evolution@swift.org> wrote:

       On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution >> <swift-evolution@swift.org> wrote:

       On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution >> <swift-evolution@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.