[swift-dev] Rationalizing FloatingPoint conformance to Equatable

[Xiaodi Wu]

On Sat, Oct 21, 2017 at 10:16 PM, Jonathan Hull <jhull at gbis.com> wrote:

>
> On Oct 21, 2017, at 6:27 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> On Sat, Oct 21, 2017 at 7:52 PM, Jonathan Hull <jhull at gbis.com> wrote:
>
>>
>> On Oct 21, 2017, at 3:02 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>
>> On Fri, Oct 20, 2017 at 2:42 PM, Stephen Canon <scanon at apple.com> wrote:
>>
>>> On Oct 20, 2017, at 8:21 AM, David Zarzycki via swift-dev <
>>> swift-dev at swift.org> wrote:
>>>
>>>
>>> On Oct 20, 2017, at 07:51, Xiaodi Wu via swift-dev <swift-dev at swift.org>
>>> wrote:
>>>
>>> On Fri, Oct 20, 2017 at 1:22 AM, Jonathan Hull <jhull at gbis.com> wrote:
>>>
>>>> +1 for trapping unless using &==.  In the case of ‘Float?’ we could
>>>> also map to nil.
>>>>
>>>> This is probably a more appropriate discussion for evolution though...
>>>>
>>>>
>>>> On Oct 19, 2017, at 9:48 PM, Brent Royal-Gordon via swift-dev <
>>>> swift-dev at swift.org> wrote:
>>>>
>>>> On Oct 19, 2017, at 4:29 PM, Xiaodi Wu via swift-dev <
>>>> swift-dev at swift.org> wrote:
>>>>
>>>> D) Must floating-point IEEE-compliant equivalence be spelled `==`?
>>>>
>>>> In my view, this is something open for debate. I see no reason why it
>>>> cannot be migrated to `&==` if it were felt that `==` *must* be a full
>>>> equivalence relation. I believe this is controversial, however.
>>>>
>>>>
>>>> I actually got partway through writing up a pitch on this yesterday,
>>>> but my opinion is that NaNs are so exceptional, and so prone to misuse,
>>>> that we ought to treat them like integer arithmetic overflows: trap when
>>>> they're detected, unless you use an `&` variant operator which indicates
>>>> you know what you're doing.
>>>>
>>>> I strongly suspect that, in practice, most float-manipulating code is
>>>> not prepared to handle NaN and will not do anything sensible in its
>>>> presence. For example, Apple platforms use floating-point types for
>>>> geometry, color components, GPS locations, etc. Very little of this code
>>>> will do anything sensible in the presence of a NaN. Arguably, it'd be
>>>> better to exclude them through the type system, but I don't think that's a
>>>> realistic possibility—we would need to have done that in a more
>>>> source-break-friendly era. But that doesn't have to mean we're completely
>>>> stuck.
>>>>
>>>>
>>> Built-in floating point operators, as well as libc/libm math functions,
>>> are designed to propagate NaN correctly. This is not meant to be a thread
>>> about NaN, and we need to be cautious to define the scope of the problem to
>>> be solved from the outset. The tendency of having ever-expanding discussion
>>> where issues such as method names turn into discussions about the entire
>>> standard library go nowhere.
>>>
>>> The question here is about `==` specifically and how to accommodate
>>> partial equivalence relations. For sanity, we start with the premise that
>>> NaN will forever be as it is.
>>>
>>>
>>> I support Jonathan’s argument. If Swift wants to trap on NaN to improve
>>> self-consistency and simplicity, then the tradeoff might be worth it. The
>>> alternative, teaching the Equality protocol about NaNs, feels like “the
>>> tail wagging the dog".
>>>
>>> In short: what IEEE requires of floating-point hardware is separable
>>> from IEEE’s opinions about language/library design.
>>>
>>>
>>> Just to be precise: IEEE 754 places no requirements on hardware. The
>>> entirety of IEEE 754 is about what *languages* should provide. It just
>>> happens to be advantageous to implement many of the requirements directly
>>> in hardware.
>>>
>>> [The rest of this is a response to the thread as a whole, not to Dave]
>>>
>>> I have no philosophical objection to trapping on NaN. IEEE 754 says that
>>> the default behavior should be to not trap, but other non-default forms of
>>> exception handling* are explicitly allowed by IEEE 754.
>>>
>>> From a practical standpoint, it’s is counter to everything about the way
>>> much floating-point hardware is designed, and that should give us some
>>> pause. On x86 it’s possible to unmask the “invalid floating point
>>> exception”, which results in any operation that generates a NaN faulting.
>>> However, it will *not* cause a fault if an operand is already a quiet NaN,
>>> so Swift would need to either test every operand that’s read from memory at
>>> the time that it’s moved into register, or test every result.
>>>
>>> On some non-x86 architectures (including in particular most ARM
>>> implementations) there is no hardware support for unmasking exceptions, so
>>> there’s no way to automatically trap on invalid operations, you would have
>>> to explicitly check for NaN on every operation. This is much, much more
>>> expensive than checking for overflow on integer arithmetic (where for
>>> addition / subtraction, it’s just an easily-predicted conditional branch).
>>> Including these checks would introduce significant code bloat and slow down
>>> naive arithmetic by roughly an order of magnitude on current hardware,
>>> which is probably a non-starter.
>>>
>>> Trapping only for == is much, much more palatable, but as Xiaodi said,
>>> doesn’t actually get you the semantics that you want for ==.
>>>
>>> &== is ugly but workable. You will have inevitable bugs from people who
>>> naively adapt code from literally any other language that assumes IEEE 754
>>> semantics for ==, however.
>>>
>>> – Steve
>>>
>>> [*] note that “exception handling” in an IEEE 754 context does not mean
>>> what you think it does if you’re coming from a generic CS
>>> not-floating-point background.
>>>
>>
>> The performance aspect of this issue are daunting, and I'm glad you
>> brought it up. On a cursory reading, having every NaN value compare equal
>> to every other NaN value is likely to be several times, if not orders of
>> magnitude, slower than the hardware IEEE implementation. This would be an
>> extraordinary cost and makes me wonder if this is at all a good idea.
>>
>>
>> One counter argument is that &== will retain full speed where important
>> (e.g. in a tight loop).
>>
>> Off the top of my head, a naive implementation of == for Float (where Nan
>> == Nan) would be:
>>
>> func == (a: Float, b: Float)->Bool {
>> return (a &== b) || !(a &== a) || !(b &== b)
>> }
>>
>
> That's not correct :P (Consider what happens when `a = 42` and `b = .nan`.)
>
>
> Oh, you are right. I have accidentally made .nan equal to everything
> instead of nothing.  That will teach me to write code in mail without sleep.
>
> That should have been (also in mail without sleep… I have learned
> nothing!):
>
> func == (a: Float, b: Float)->Bool {
> return (a &== b) || !( a &== a  ||  b &== b )
> }
>
>
> The good news is that ‘a' and ‘b' only need to be loaded into registers
>> once.  Also, it could short circuit if 'a &== b' is true (if that is
>> faster).  We could probably do better with a little cleverness.
>>
>
> 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.
>
>
> He also said that for only == it was "much, much more palatable"
>

...which it is, in the grand scheme of things, as only a tiny proportion of
your code would be `==`. But `==` itself will still perform abysmally, and
a method such as `elementsEqual` that recursively evaluates `==` would be
very, very sad.

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.
>
>
> I am ok incurring cost (especially when it is recoverable) if it will help
> avoid pitfalls.  I guess the question is: how many pitfalls are there from
> breaking reflexivity?
>
> It is one of those things that you hear veteran programmers constantly
> warning about, which tells me that they have been bitten a few times.
>

To be clear, the most viable alternative to abandoning demand #4, to my
mind, is abandoning demand #1--that is, explicitly clarifying that
Equatable only guarantees a partial equivalence relation.

It would then be necessary to offer additional methods to determine if the
implementation's `==` is in fact a full equivalence relation. This is what
PR #12503 does with underscored methods. If this course of action is
settled upon, those methods would eventually become full public API with
improved names after Evolution. With conditional conformances, `Sequence
where Element : Equatable` would implement `public static var
_hasExceptionalValues : Bool { return Element._hasExceptionalValues }`.

Fundamentally, there is no magic to be had here: it's all tradeoffs.

If we make NaN == NaN, then *every* use of floating point `==` must incur a
performance cost or be migrated. Practically speaking, the average
developer would be conditioned to type `&==` when working with
floating-point code, therefore avoiding no more pitfalls as compared to the
status quo when working with floating point. However, any custom generic
code *might* be more robust--unless they rely on total ordering of
Comparable methods, which will still not be the case ((1 < NaN) == false
*and* (NaN < 1) == false), or assume seemingly "obvious" properties of
Numeric, which will still not be the case (remember, a + b - b != a if
you're working with floating-point values thanks to rounding). Put it this
way: very few generic algorithms that are incorrect now _would be correct
but for the fact that NaN != NaN_; accommodating floating-point types is
much trickier than just that. (I was the one who fixed accumulated rounding
error in floating point strides back in the day.)

On the other hand, if we formalize `==` as a *partial* equivalence
relation, then *every* use of `==` in correct generic code must either rely
only on partial equivalence or explicitly check for full equivalence.
Practically speaking, the average developer will carry on as they always
have and their generic code will have the same pitfalls as they do today;
they won't test for correctness using floating-point values, and if they
try to use floating-point values as input, the algorithm may fail to yield
the expected result--but just as likely because of the myriad other
pitfalls of floating-point types that have nothing to do with NaN != NaN.
However, any custom concrete floating point code will remain performant,
and any uses of stdlib methods will return predictable results because we
will fix them.

>From a pragmatic standpoint, a user is *astronomically* more commonly going
to use concrete floating point `==` than write generic algorithms on
collection types which happen only rely on equivalence and not any other
facilities for which floating-point types are uniquely wonky, then feed
that algorithm floating-point values.

It would serve us well to re-evaluate what generic algorithms absolutely
>> require a full equivalence relation. Let's take a look at `Array`, for
>> example.
>>
>> - `index(of:)` works perfectly sensibly without such a relation; if no
>> NaN is equal to any other NaN, `index(of: .nan)` is appropriately `nil`.
>> - `min()` and `max()` are something else entirely, as we're talking here
>> only of equivalence and not of total order, which is another issue
>> altogether.
>> - `sort()` is problematic, but not if a custom predicate is supplied.
>> - `split()` only runs into problems if specifically trying to split a
>> sequence on `.nan`, but again this would be unsurprising if no NaN is equal
>> to any other NaN.
>> - `==` is broken but can be fixed as shown in PR #12503.
>>
>>
>> My main worry would be generic algorithms on something one level of
>> generalization away.  For example, how should a Set handle double insertion
>> of a struct which has a Float in it.  It is very likely that the creator of
>> that struct just && together == of the elements, so the set will end up
>> with two identical entries (neither of which would register as being a
>> member when the set is asked).
>>
>
> Consider a comparison of two instances of Complex<Float>: it should
> absolutely return `false` when evaluating `Complex(1.0, .nan) ==
> Complex(1.0, .nan)`. Likewise, if (actually, let's put it another way: as
> long as) NaN != NaN, then an instance of Set<Float> should not deduplicate
> NaN, and NaN should never be a member of that Set, and neither should an
> instance of Set<Complex<Float>>. That's _correct_ in my view.
>
>
> Right, in the context of Float, but my point was that the issues ripple
> outward.
>
> Part of the issue is that we have generic algorithms which have an
> expectation of reflexivity from ==.  But we also need to consider generic
> algorithms which build on expectations of things like Set, where the
> expected behavior has been changed because of how == behaves regarding
> NaN.  As you said, you consider duplication of NaN in Sets the correct
> behavior, so that means that anything building on Set generically will need
> to consider this aberrant behavior in the same way they need to consider
> ==.  It ripples outward, and each level gets harder to plan for.
>

It only "ripples outward" in the sense that formalizing `==` as a partial
equivalence relation requires each use of `==` in the generic setting to
test for full equivalence if necessary. But that is what it means to make
or not to make a semantic guarantee. Moreover, as a consequence of the
present design where implementation doesn't match documentation, it's
*already necessary* to do so in today's Swift if you want your algorithms
to work with floating point. Finally, the reality of the situation is that
many algorithms will require such planning in order to accommodate floating
point even if NaN == NaN.

I can’t write generic code which puts something in a collection and then
> expects that thing to be a member of the collection (this could even lead
> to infinite loops).  The count of a collection and the number of members I
> can test for are potentially different.
>

Right, but again, even today, you can't rely on these properties in
reality. On a practical level, consider how often you write generic code
that deals only with equivalence of elements in collections (and not
ordering, or arithmetic, or any other protocol-based method).

The number of resulting special cases which one has to keep in mind grows
> exponentially as it ripples outwards.
>
> Also, you can’t just special case Float, because it is anything containing
> a Float.
>
> The wonkiness with `Array.==` is one of the few places where the behavior
> of the generic algorithm is inexplicable on the basis of what's publicly
> explained to the user. By contrast, `index(of:)`, `split`, etc. all behave
> predictably given the fact that NaN != NaN.
>
>
> One of the places we have found so far.
>

It's not a mystery where these problems arise. I've personally raised the
issue with `Array.==` a few times over the last two years. The entire
standard library can be made compatible with partial equivalence `==` with
trivial migration.


> This is a notorious area for bugs to happen though. It is not just the
> standard library. I’ll bet that people have a bunch of bugs in generic code
> they have written involving dictionaries with keys containing a Float
> somewhere.
>

For many, many reasons that do not at all involve NaN, I do believe the
common advice is *not* to use floating-point keys. You find the same advice
for C++, C#, Python, and on and on...

How does the PR handle Array<Complex> == Array<Complex>?  Wouldn’t it have
> the same issue?
>

Complex would have to make use of the underscored APIs; again, if this plan
of action is adopted, then the additional APIs would go through Evolution
and `==` as partial equivalence would become formalized.

I am currently leaning towards NaN == NaN behavior, with a warning
>> explaining &== when used with Float == Float (and a way to silence it).
>> That way, you at least have progressive disclosure.
>>
>
> Thanks,
> Jon
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171021/35869b4c/attachment.html>