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

[Stephen Canon]

Gah, hit send too soon, the values should be:

-1, -0.890625, -0.796875, -0.703125, -0.59375, -0.5, -0.390625, -0.296875, -0.203125, -0.09375, 0, 0.109375, 0.203125, 0.296875, 0.40625, 0.5, 0.609375, 0.703125, 0.796875, 0.90625

i.e. nearly 10% error for the values closest to zero.
– Steve

> On Apr 2, 2016, at 6:30 PM, Stephen Canon via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution