On Mon, Oct 23, 2017 at 12:47 AM, Brent Royal-Gordon <br...@architechies.com
> wrote:
> > On Oct 21, 2017, at 6:27 PM, Xiaodi Wu via swift-dev <
> swift-dev@swift.org> wrote:
> >
> > Steve can describe the exact number of additional machine instructions
> on each architecture, but from my cursory reading the performance cost is
> not good and there's little cleverness to be had.
>
> I'm not sure why you think there's no cleverness to be had. For instance,
> suppose we loosen our requirement a bit: We require the `==` operator to be
> reflexive, but we allow `BinaryFloatingPoint.==` to treat NaNs with
> different payloads as different values. That very nearly allows us to use
> integer equality for floating-point comparison; we only need a +0/-0
> special case:
>
> extension Double {
> private var bits: Int {
> return unsafeBitCast(self, to: Int64.self)
> }
>
> static func == (lhs: Double, rhs: Double) -> Bool {
> let lhsBits = lhs.bits
> let rhsBits = rhs.bits
> let nonSignBits = ~((-0 as Double).bits)
>
> return lhsBits == rhsBits || ((lhsBits | rhsBits)
> & nonSignBits) == 0
> }
> }
>
Besides all of Steve's points (which are absolutely key to consider), this
function is clearly more expensive than a single machine instruction.
Consider also how much more expensive it would be in the case where this
custom equality prevents SIMD parallelization.
`BinaryFloatingPoint.<` requires more branching, but it doesn't look too
> bad either:
>
> extension Double {
> static func < (lhs: Double, rhs: Double) -> Bool {
> let lhsBits = lhs.bits
> let rhsBits = rhs.bits
>
> let signBits = (-0 as Double).bits
> let nonSignBits = ~signBits
>
> if (lhsBits & signBits) == (rhsBits & signBits) {
> // lhs < rhs (where signs are the same) is
> equivalent to integer comparison.
> return lhsBits < rhsBits
> }
> else {
> // lhs < rhs (where signs are different)
> if lhs is negative and they aren't both zero.
> return (lhsBits & signBits) == 0 &&
> ((lhsBits | rhsBits) & nonSignBits) != 0
> }
> }
> }
>
> (I could be wrong about these; I'm not a floating-point expert.)
>
> These implementations would make sorting and searching work *mostly*
> sensibly; the only problem would be that, for instance,
> `numbers.contains(.nan)` might return false if there's a NaN in `numbers`
> with a different payload than the one `.nan` returns. Personally, I think
> that's an acceptable cost.
>
> > My overarching point is that, if most generic algorithms don't break
> without a full equivalence relation and others can be trivially rewritten
> to accommodate floating point behavior, then incurring a non-trivial cost
> by default is not a good idea.
>
> Yes, but the "if" is doing a lot of work here—and I don't think it's
> actually true. Things in the standard library that currently don't
> accommodate floating-point behavior include:
>
> • Our `sort()`, `min()`, and `max()` methods
> • Our `Set` and `Dictionary` types
>
Again, `Set` and `Dictionary` accommodate floating-point types just
fine--in that their behavior is consistent with NaN != NaN. That is, if you
accept that NaN != NaN, then there is nothing to fix about the
implementation of `Set` or `Dictionary`.
As to `sort`, `min`, and `max`, again, those would not be addressed by
reflexive equality of NaN; that would require a total ordering over
floating point values, which is another issue entirely (and, also, exists
as `FloatingPoint.isTotallyOrdered(belowOrEqualTo:)`, a function with
behavior dictated by the IEEE standard). We are discussing here only
whether NaN == NaN should be required by Equatable; NaN would still be
unordered relative to all other values for the purposes of `<` and other
comparison operators.
Can these be trivially rewritten? I'm not sure about most of them, but I
> *can* come up with a trivial rewrite for `min()`:
>
> public func min() -> Element? {
> var it = makeIterator()
> guard var result = it.next() else { return nil }
> for e in IteratorSequence(it) {
> if !(result == result) || e < result { result = e }
> }
> return result
> }
>
You don't need to rewrite from scratch; what you want to use is
`FloatingPoint.minimum(_:_:)` (again, a function with behavior dictated by
the IEEE standard).
But that brings us to the second question: Do we really expect random
> people to rewrite their code like this? I mean, we're literally doing a
> reflexivity check in this code. Is that a sensible thing to force on our
> users?
>
Floating point is hard; we cannot hide the complexity of floating point
merely by redefining `==`. We do, however, stand a good chance of making
things worse by deviating from the common practice in other languages.
> (For that matter, I'm not sure I could rewrite `min(by:)` this way if we
> treat the comparator as equivalent to a `<`. That seems like a sign we're
> Doing It Wrong.)
>
> --
> Brent Royal-Gordon
> Architechies
>
>
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
