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

[Xiaodi Wu]

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

> > * 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
> 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 at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160519/18654980/attachment.html>