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

[Andrew Trick via swift-evolution]

> On Apr 25, 2016, at 4:19 PM, Dave Abrahams via swift-evolution 
>  wrote:
> 
> 
> on Mon Apr 25 2016, Haravikk  wrote:
> 
>>On 25 Apr 2016, at 22:53, Dave Abrahams via swift-evolution
>> wrote:
>> 
>>on Sat Apr 23 2016, Haravikk  wrote:
>> 
>>On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution
>> wrote:
>> 
>>On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>> 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 < 100 { i = i &+ 1 }
>>let elapsed = NSDate().timeIntervalSince1970 - startTime
>>}
>> 
>>do {
>>let startTime = NSDate().timeIntervalSince1970
>>var i = 0
>>while i < 100 { 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.

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

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

[Dave Abrahams via swift-evolution]

on Mon Apr 25 2016, Haravikk  wrote:

> On 25 Apr 2016, at 22:53, Dave Abrahams via swift-evolution
>  wrote:
>
> on Sat Apr 23 2016, Haravikk  wrote:
>
> On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution
>  wrote:
>
> On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>  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 < 100 { i = i &+ 1 }
> let elapsed = NSDate().timeIntervalSince1970 - startTime
> }
>
> do {
> let startTime = NSDate().timeIntervalSince1970
> var i = 0
> while i < 100 { 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
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Haravikk via swift-evolution]

> On 25 Apr 2016, at 22:53, Dave Abrahams via swift-evolution 
>  wrote:
> 
> 
> on Sat Apr 23 2016, Haravikk  > wrote:
> 
>>On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution
>> wrote:
>> 
>>On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>> 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 < 100 { i = i &+ 1 }
>> let elapsed = NSDate().timeIntervalSince1970 - startTime
>> }
>> 
>> do {
>> let startTime = NSDate().timeIntervalSince1970
>> var i = 0
>> while i < 100 { 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?___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Dave Abrahams via swift-evolution]

on Sat Apr 23 2016, Haravikk  wrote:

> On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution
>  wrote:
>
> On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>  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 < 100 { i = i &+ 1 }
> let elapsed = NSDate().timeIntervalSince1970 - startTime
> }
>
> do {
> let startTime = NSDate().timeIntervalSince1970
> var i = 0
> while i < 100 { 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

> 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

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

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

[Haravikk via swift-evolution]

> On 7 Apr 2016, at 18:54, Dmitri Gribenko via swift-evolution 
>  wrote:
> 
> On Thu, Apr 7, 2016 at 12:20 AM, Vladimir.S via swift-evolution
>  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 < 100 { i = i &+ 1 }
let elapsed = NSDate().timeIntervalSince1970 - startTime
}

do {
let startTime = NSDate().timeIntervalSince1970
var i = 0
while i < 100 { 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.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Dmitri Gribenko via swift-evolution]

On Fri, Apr 8, 2016 at 3:49 AM, Vladimir.S  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 ;-)

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

-- 
main(i,j){for(i=2;;i++){for(j=2;j*/
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Vladimir.S via swift-evolution]

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 ;-)

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

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

[Dmitri Gribenko via swift-evolution]

On Thu, Apr 7, 2016 at 11:27 AM, Vladimir.S  wrote:
> 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

-- 
main(i,j){for(i=2;;i++){for(j=2;j*/
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Vladimir.S via swift-evolution]

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.
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160229/011552.html

Dmitri

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

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

[Dmitri Gribenko via swift-evolution]

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

-- 
main(i,j){for(i=2;;i++){for(j=2;j*/
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Vladimir.S via swift-evolution]

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
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.

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

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

[Haravikk via swift-evolution]

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

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

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

[Vladimir.S via swift-evolution]

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