[Review] SE-0050: Decoupling Floating Point Strides from Generic Implementations


(Chris Lattner) #1

Hello Swift community,

The review of "SE-0050: Decoupling Floating Point Strides from Generic Implementations" begins now and runs through May 23. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0050-floating-point-stride.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


(Brent Royal-Gordon) #2

  * What is your evaluation of the proposal?

No mistake: this is a pretty ugly solution to the problem. However, it *is* a problem that badly needs solving, and all the other solutions (like "always use the float logic and let the optimizer fix it up into integer logic") are far worse. So I believe this proposal should be accepted.

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

Yes. Striding simply doesn't work properly on floating-point types right now. That needs to be fixed.

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

Most languages I've used just let you write shitty floating-point code. It's nice to see Swift helping you write good floating-point code.

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

Quick reading and some private experiments.

···

--
Brent Royal-Gordon
Architechies


(Nicola Salmoria) #3

* What is your evaluation of the proposal?

+1. It might not be pretty, but it is an improvement.

The Proposed Solution doesn't compile with development snapshot 05-09
(SE-0067 hasn't landed yet, IIRC). I hacked it to get it to compile, and
tested it with two problematic cases:

Test #1:
let expected = Array(stride(from: 10, through: 20, by: 1).map { Float($0) *
0.1 })
// [1.0, 1.10000002, 1.20000005, 1.30000007, 1.39999998, 1.5, 1.60000002,
1.70000005, 1.80000007, 1.89999998, 2.0]

let actual = Array(stride(from: Float(1.0), through: 2.0, by: 0.1))
// old result: one iteration less than expected
// [1.0, 1.10000002, 1.20000005, 1.30000007, 1.4000001, 1.50000012,
1.60000014, 1.70000017, 1.80000019, 1.90000021]
// new result: correct
// [1.0, 1.10000002, 1.20000005, 1.29999995, 1.39999998, 1.5, 1.60000002,
1.70000005, 1.79999995, 1.9000001, 2.0]

Test #2:
let expected = Array(stride(from: 10, to: 100, by: 9).map { Float($0) * 0.1 })
// [1.0, 1.89999998, 2.79999995, 3.70000005, 4.5999999, 5.5, 6.4000001,
7.30000019, 8.19999981, 9.10000038]

let actual = Array(stride(from: Float(1.0), to: 10.0, by: 0.9))
// old result: one iteration more than expected
// [1.0, 1.89999998, 2.79999995, 3.69999981, 4.5999999, 5.5, 6.4000001,
7.30000019, 8.19999981, 9.09999943, 9.99999905]
// new result: correct
// [1.0, 1.89999998, 2.79999995, 3.69999981, 4.5999999, 5.5, 6.39999962,
7.29999971, 8.19999981, 9.09999943]

So the proposed solution works as advertised.

I would suggest to include two cases like the above in the test suite.

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

Swift?

Yes. This is a higher level abstraction, so it's important that it
guarantees the best possible accuracy. The current generic implementation
gives unacceptably surprising results.

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

Yes. It nicely follows the principle of least astonishment.

* If you have used other languages or libraries with a similar feature,

how do you feel that this proposal compares to those?

I always flat-out avoided floating point loops in other languages, fearing
that they would be unreliable. It's good that with this change it'll be
possible to use them with more confidence.

* How much effort did you put into your review? A glance, a quick reading,

or an in-depth study?

careful reading, tested the proposed solution, and read and contributed to
the relevant threads.

···

--
Nicola


(Xiaodi Wu) #4

> * What is your evaluation of the proposal?

+1. It might not be pretty, but it is an improvement.

The Proposed Solution doesn't compile with development snapshot 05-09
(SE-0067 hasn't landed yet, IIRC).

An (almost complete) implementation of SE-0067 floating point protocols
have landed in master; there have been a few nips and tucks as compared to
SE-0067 itself and I've created a version of the code in this proposal to
compile accordingly. You can see it here:
https://github.com/xwu/swift/tree/SE-0050

There's is a wrinkle in the proposal worth discussing here during the
review period, and you'll notice a difference related to it if you compare
the code above to what's in this proposal. What should be the type of the
internal step counter `_step`? [BigInt types not currently in the stdlib
are out of scope.]

As proposed, _step has the same floating point type as the stride size.
Originally, Erica proposed an Int step counter, and I too thought that it
was plenty good enough. Functionally, 2^64 iterations is effectively an
infinite loop on modern machines. Moreover, strides have always been
intended to conform to Collection (though they do not in fact do so), and
by analogy to arrays and other collection types a maximum of Int elements
is quite consistent.

However, Stephen Canon has pointed out that using an Int step counter means
that the maximum number of steps on 32-bit systems is dramatically lower.
On the other hand, while I can readily accept that there are meaningful
loops with 2^32 iterations, I'm unsure whether there are as many use cases
for floating point strides with more than 2^32 steps.

More concerning, though, there's a hit in performing
integer-to-floating-point conversion at every iteration. Recently, I tried
to compare the performance of floating point stride using an Int step
counter or a floating point one. What I had handy at the time was Swift
2.2; I backported both solutions and measured performance using XCTest
framework (making sure to use the result of the computation at each
iteration to prevent the compiler from optimizing away my loop). I found
that, at least in the several times that I performed the test, one solution
was not consistently faster than the other. I'm not sure whether this can
be generalized to 32-bit platforms, and I did not dig to see if one or both
solutions was compiled to make use of fused multiply-add.

What one gains from using an Int step counter over a floating point one is
a consistent maximum number of steps regardless of the floating point type
of the endpoints. Less pertinently, when it comes to implementation detail,
some of the computations are a little more elegant (for instance,
precondition total number of steps less than Int.max rather than testing
whether the ULP of the total number of steps is less than or equal to one).

I hacked it to get it to compile, and

···

On Thu, May 19, 2016 at 4:31 AM, Nicola Salmoria via swift-evolution < swift-evolution@swift.org> wrote:

tested it with two problematic cases:

Test #1:
let expected = Array(stride(from: 10, through: 20, by: 1).map { Float($0) *
0.1 })
// [1.0, 1.10000002, 1.20000005, 1.30000007, 1.39999998, 1.5, 1.60000002,
1.70000005, 1.80000007, 1.89999998, 2.0]

let actual = Array(stride(from: Float(1.0), through: 2.0, by: 0.1))
// old result: one iteration less than expected
// [1.0, 1.10000002, 1.20000005, 1.30000007, 1.4000001, 1.50000012,
1.60000014, 1.70000017, 1.80000019, 1.90000021]
// new result: correct
// [1.0, 1.10000002, 1.20000005, 1.29999995, 1.39999998, 1.5, 1.60000002,
1.70000005, 1.79999995, 1.9000001, 2.0]

Test #2:
let expected = Array(stride(from: 10, to: 100, by: 9).map { Float($0) *
0.1 })
// [1.0, 1.89999998, 2.79999995, 3.70000005, 4.5999999, 5.5, 6.4000001,
7.30000019, 8.19999981, 9.10000038]

let actual = Array(stride(from: Float(1.0), to: 10.0, by: 0.9))
// old result: one iteration more than expected
// [1.0, 1.89999998, 2.79999995, 3.69999981, 4.5999999, 5.5, 6.4000001,
7.30000019, 8.19999981, 9.09999943, 9.99999905]
// new result: correct
// [1.0, 1.89999998, 2.79999995, 3.69999981, 4.5999999, 5.5, 6.39999962,
7.29999971, 8.19999981, 9.09999943]

So the proposed solution works as advertised.

I would suggest to include two cases like the above in the test suite.

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

Yes. This is a higher level abstraction, so it's important that it
guarantees the best possible accuracy. The current generic implementation
gives unacceptably surprising results.

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

Yes. It nicely follows the principle of least astonishment.

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

I always flat-out avoided floating point loops in other languages, fearing
that they would be unreliable. It's good that with this change it'll be
possible to use them with more confidence.

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

careful reading, tested the proposed solution, and read and contributed to
the relevant threads.

--
Nicola

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