<div dir="ltr">On Mon, Oct 23, 2017 at 12:47 AM, Brent Royal-Gordon <span dir="ltr"><<a href="mailto:brent@architechies.com" target="_blank">brent@architechies.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><span class="gmail-">> On Oct 21, 2017, at 6:27 PM, Xiaodi Wu via swift-dev <<a href="mailto:swift-dev@swift.org">swift-dev@swift.org</a>> wrote:<br>
><br>
> 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.<br>
<br>
</span>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:<br>
<br>
extension Double {<br>
private var bits: Int {<br>
return unsafeBitCast(self, to: Int64.self)<br>
}<br>
<br>
static func == (lhs: Double, rhs: Double) -> Bool {<br>
let lhsBits = lhs.bits<br>
let rhsBits = rhs.bits<br>
let nonSignBits = ~((-0 as Double).bits)<br>
<br>
return lhsBits == rhsBits || ((lhsBits | rhsBits) & nonSignBits) == 0<br>
}<br>
}<br></blockquote><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
`BinaryFloatingPoint.<` requires more branching, but it doesn't look too bad either:<br>
<br>
extension Double {<br>
static func < (lhs: Double, rhs: Double) -> Bool {<br>
let lhsBits = lhs.bits<br>
let rhsBits = rhs.bits<br>
<br>
let signBits = (-0 as Double).bits<br>
let nonSignBits = ~signBits<br>
<br>
if (lhsBits & signBits) == (rhsBits & signBits) {<br>
// lhs < rhs (where signs are the same) is equivalent to integer comparison.<br>
return lhsBits < rhsBits<br>
}<br>
else {<br>
// lhs < rhs (where signs are different) if lhs is negative and they aren't both zero.<br>
return (lhsBits & signBits) == 0 && ((lhsBits | rhsBits) & nonSignBits) != 0<br>
}<br>
}<br>
}<br>
<br>
(I could be wrong about these; I'm not a floating-point expert.)<br>
<br>
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.<br>
<span class="gmail-"><br>
> 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.<br>
<br>
</span>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:<br>
<br>
• Our `sort()`, `min()`, and `max()` methods<br>
• Our `Set` and `Dictionary` types<br></blockquote><div><br></div><div>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`.</div><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
Can these be trivially rewritten? I'm not sure about most of them, but I *can* come up with a trivial rewrite for `min()`:<br>
<br>
public func min() -> Element? {<br>
var it = makeIterator()<br>
guard var result = it.next() else { return nil }<br>
for e in IteratorSequence(it) {<br>
if !(result == result) || e < result { result = e }<br>
}<br>
return result<br>
}<br></blockquote><div><br></div><div>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).</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
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?<br></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
(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.)<br>
<span class="gmail-HOEnZb"><font color="#888888"><br>
--<br>
Brent Royal-Gordon<br>
Architechies<br>
<br>
</font></span></blockquote></div><br></div></div>