[swift-evolution] Feature proposal: Range operator with step

Stephen Canon scanon at apple.com
Sat Apr 2 20:30:58 CDT 2016

General numerics comments:
We’ll want internal state and computation to be Double for Float or Double, and Float80 for Float80.  This confers a couple significant advantages:

- There are useful loops with more than 2**31 steps, which means having _step be Int is insufficient on 32-bit systems.  By contrast, 2**53 steps is indistinguishable from “infinite loop” for consumer systems (tens of days for a loop that does no actual work).  At some point, we will want to use a wider state, but Double is sufficient for the foreseeable future, and this can be an internal detail so it’s easy to change if/when we need to so.

- Using Double is preferable to using Int64 because it allows us to avoid extra Int -> FP conversions, and avoids multi-word arithmetic on 32-bit systems.

- Using Double internally for Float loops avoids catastrophic cancellation for loops that cross zero, e.g.:

	for x in stride(from: Float(-200000), through: Float(1), by: Float(0.1)) {

If computed in Float, the last 20 values produced by this are:

-0.09375, 0, 0.109375, 0.203125, 0.296875, 0.40625, 0.5, 0.609375, 0.703125, 0.796875, 0.90625, 1, 1.109375, 1.203125, 1.296875, 1.40625, 1.5, 1.609375, 1.703125, 1.796875, 1.90625

Of course, it’s still possible to construct such examples for Double, but they require step size of such wildly disparate scale from the endpoints that you have to loop “forever” (hours/days) before the catastrophic cancellation becomes a significant concern.

- Double is no less computationally efficient than Float on modern x86 or ARM.

We should also make sure that we codegen _start + _step*_stride to a fused-multiply add when we have hardware support (x86 Haswell and later, all arm64, most current armv7).  This eliminates the catastrophic cancellation issue *entirely*, and is faster than a separate mul and add to boot.

One specific question:
I don’t see any reason to enforce that stride isn’t subnormal (and good reasons to allow it).  Why did you add that restriction?

Other than those notes, this approach seems perfectly workable to me.

– Steve

> On Apr 2, 2016, at 3:26 PM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
> All righty, here's a proof-of-concept for non-error-accumulating
> stride based on the swift-3-indexing-model branch. I tried to
> incorporate the feedback received in the interim. Namely:
> 1. Only floating point types get this slightly more computationally
> intensive "new" stride; all other types get the "classic" stride. If
> accepted, this new code could be appended to Stride.swift and exist
> alongside current code, which doesn't need to be modified.
> 2. Based on discussions about UnsafePointer, etc., it dawned on me
> that what really determines whether a StrideTo<T> accumulates error
> isn't T but rather T.Stride, so based on Dave's insights above we get
> "new stride" if T.Stride == FloatingPoint.
> 3. I need to multiply floating point values, and if I understand
> correctly multiplication will be guaranteed by a revised SignedNumber
> protocol; for now, I've used a _FloatingPointStrideable protocol as a
> workaround. Note that Float80 doesn't conform to FloatingPoint, so it
> isn't retroactively modeled to conform to _FloatingPointStrideable.
> Nothing's lost for the moment because we can't use Float80 values for
> "new stride" anyway, since it doesn't currently implement the isNormal
> property (see below for why I use that property).
> 4. I considered Dave's suggestion whether we could avoid introducing
> new types, instead modifying the existing StrideToIterator and
> StrideThroughIterator and relying on compiler optimization to turn
> "new" stride into "classic" stride for StrideTo<Int>, etc.; however,
> because the differences between "classic" stride and "new" stride
> extend beyond the iterator's next() method (see below), I thought it
> best to keep the floating point logic in distinct types.
> 5. One difference discussed was how to handle edge cases involving
> lots of iterations; I incorporated Howard's suggestions here, so
> whether a stride requires more than Int.max steps is tested
> upfront--as a consequence, infinite loops are impossible. I would love
> it if, as Thorsten suggests, we could use BigInts, but of course
> there's no such type in the stdlib and adding one would have to be
> another discussion altogether.
> 6. The stride increment can't be zero; for a floating point type, it
> also obviously can't be infinity or NaN. I'm inclined to think that
> subnormal increments should be out of the question as well, so my
> proposed streamlined criterion is simply `stride.isNormal`. Comments
> on this are welcome...
> Not included:
> 1. I know Ranges are in flux, so I've held off on extending Range with
> a striding(by:) method in this proof-of-concept.
> 2. No attempt at the suggested stride(from:to:steps:) quite yet.
> 2. No tests written yet for this proof-of-concept; I noticed that
> there's a stub for testing strides with bounds of type Double, but
> there's a comment about things not being ready because Double conforms
> to RandomIndexType--not sure what to make of that.
> 3. Haven't gotten around to testing performance.
> On Wed, Mar 30, 2016 at 12:03 PM, Erica Sadun <erica at ericasadun.com> wrote:
>> On Mar 29, 2016, at 11:26 PM, Xiaodi Wu via swift-evolution
>> <swift-evolution at swift.org> wrote:
>> On Tue, Mar 29, 2016 at 7:48 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>> on Tue Mar 29 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>> Relatedly, while you're tackling this big revision:
>> I've tried to play around with what it would take to write a generic
>> non-error-accumulating striding method, and afaict, it would be
>> enormously cleaner if Strideable types are guaranteed to have + and *
>> (well, Strideable.Stride needs *, to be more accurate),
>> That should happen automatically, since it conforms to SignedNumber,
>> when we get the Integer protocols updated (project currently on hold while
>> we land this other revision).
>> since the iterator needs to be able to compute end = start + iteration
>> * stride.
>> Don't you need division too if you're going to do this?
>> I didn't seem to ever need division. See attached playground (which
>> borrows shamelessly from existing code and Erica's proposal, and which
>> is written in Swift 2.2 because that's what I had handy).
>> Have you considered trying to extend the `swift-3-indexing-model` branch
>> at the Swift repo to take the floating point approach into account? Dave A
>> is working on a massive overhaul of ranges (including `Countable` items
>> and one would presume floating point closed and open intervals as well),
>> and I'd love to see better implementations of, for example,
>> `(x..<y).striding(by:z)`
>> happen for Double types.
>> I'd be happy to throw a proposal together based on a proof of concept,
>> if you had the flexibility to work on the coding.
>> -- Erica
> <FloatingPointStrideable.swift>_______________________________________________
> 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/20160402/bf7eb458/attachment.html>

More information about the swift-evolution mailing list