> 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
}
}
`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
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
