[swift-dev] Rationalizing FloatingPoint conformance to Equatable

[Xiaodi Wu]

On Mon, Oct 23, 2017 at 12:47 AM, Brent Royal-Gordon <brent at architechies.com
> wrote:

> > On Oct 21, 2017, at 6:27 PM, Xiaodi Wu via swift-dev <
> swift-dev at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171023/5804ad55/attachment.html>