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

Sun Apr 3 02:59:09 CDT 2016

On Sat, Apr 2, 2016 at 8:30 PM, Stephen Canon <scanon at apple.com> wrote:
> General numerics comments:
> We’ll want internal state and computation to be Double for Float or Double,
> and Float80 for Float80.

One argument why Float for Float might be sufficient:

1. Given that `Float(-200000) + Float(1) * Float(199999.9) ==
Float(-0.09375)`, -0.09375 *should* be a value in the sequence when
striding from Float(-200000) to Float(1) by Float(0.1). Otherwise, it
could be astonishing for users that StrideTo<Float> is somehow more
accurate than bare arithmetic using Float, since the documentation
explains explicitly how the values are being calculated (for stride as
it is now, the documentation says "self, self + stride, self + stride
+ stride ... last", which I changed for floating point types to "self,
self + stride, self + stride * 2 ... last"). A user that wants
double-precision accuracy in that computation should explicitly cast
stride arguments to Double.

2. While there are definitely useful loops with more than 2**31 steps,
and I agree that we should ensure at least 2**53 steps for
`stride<Double>(...)` even on 32-bit systems, loops using
`stride<Float>(...)` with more than 2**24 steps should be rare. Users
who wish to go beyond 2**24 steps can always cast stride arguments to
Double, which has the benefit of being more explicit and less magical.

I've played with using Double for Double and Float for Float (which
confers, I think, the rest of the advantages over Int named below),
but Double for Float is definitely a new twist. One disadvantage is
that using Double internally for Float would require Float bounds to
be represented internally as Double bounds. I was trying to be clever
with the generics so that any stride<T : Strideable where T.Stride :
FloatingPoint>(...) would be non-error-accumulating, but I can't think
of a way to do this while also avoiding catastrophic cancellation for
Float because the generic algorithm does not care that T and T.Stride
have the same precision or, for that matter, whether T is a floating
point type at all. Thoughts?

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

The restriction was poorly thought out based on a vague notion that
"typically sized" ranges and very small strides would be somehow "not
good." I can also now think of some good reasons to change that as
well, such that what's enforced is only `stride.isFinite &&
!stride.isZero`.

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

Hurray!

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