[swift-dev] Rationalizing FloatingPoint conformance to Equatable

[Brent Royal-Gordon]

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

`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

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
  }

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?

(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