<div dir="ltr">On Mon, Oct 23, 2017 at 12:47 AM, Brent Royal-Gordon <span dir="ltr">&lt;<a href="mailto:brent@architechies.com" target="_blank">brent@architechies.com</a>&gt;</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-">&gt; On Oct 21, 2017, at 6:27 PM, Xiaodi Wu via swift-dev &lt;<a href="mailto:swift-dev@swift.org">swift-dev@swift.org</a>&gt; wrote:<br>
&gt;<br>
&gt; 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&#39;s little cleverness to be had.<br>
<br>
</span>I&#39;m not sure why you think there&#39;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) -&gt; 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) &amp; nonSignBits) == 0<br>
                }<br>
        }<br></blockquote><div><br></div><div>Besides all of Steve&#39;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.&lt;` requires more branching, but it doesn&#39;t look too bad either:<br>
<br>
        extension Double {<br>
                static func &lt; (lhs: Double, rhs: Double) -&gt; 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 &amp; signBits) == (rhsBits &amp; signBits) {<br>
                                // lhs &lt; rhs (where signs are the same) is equivalent to integer comparison.<br>
                                return lhsBits &lt; rhsBits<br>
                        }<br>
                        else {<br>
                                // lhs &lt; rhs (where signs are different) if lhs is negative and they aren&#39;t both zero.<br>
                                return (lhsBits &amp; signBits) == 0 &amp;&amp; ((lhsBits | rhsBits) &amp; nonSignBits) != 0<br>
                        }<br>
                }<br>
        }<br>
<br>
(I could be wrong about these; I&#39;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&#39;s a NaN in `numbers` with a different payload than the one `.nan` returns. Personally, I think that&#39;s an acceptable cost.<br>
<span class="gmail-"><br>
&gt; My overarching point is that, if most generic algorithms don&#39;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 &quot;if&quot; is doing a lot of work here—and I don&#39;t think it&#39;s actually true. Things in the standard library that currently don&#39;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 `&lt;` 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&#39;m not sure about most of them, but I *can* come up with a trivial rewrite for `min()`:<br>
<br>
  public func min() -&gt; 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 &lt; result { result = e }<br>
    }<br>
    return result<br>
  }<br></blockquote><div><br></div><div>You don&#39;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&#39;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&#39;m not sure I could rewrite `min(by:)` this way if we treat the comparator as equivalent to a `&lt;`. That seems like a sign we&#39;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>