[swift-dev] Rationalizing FloatingPoint conformance to Equatable

David Zarzycki dave at znu.io
Wed Oct 25 21:05:39 CDT 2017



> On Oct 25, 2017, at 19:25, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> 
> I was proposing something different where Float and Int are both Equatable and Substitutable, but neither Equatable nor Substitutable inherit from the other. The former is mathematical and the latter is not (which allows it to deal with NaN payloads, ±0, etc). Generic algorithms care mostly if not completely about mathematics, while generic containers care mostly if not completely about substitutability. They can live alongside each other and get along peacefully/sanely. And if people need to care about both, then at least they have an out.
> 
> The issue with this is similar to that in my reply earlier about bitwise comparison of floating-point values. Yes, you can propose some total ordering over floating-point values totally divorced from `==`, but I'm quite certain that people who invoke `sort()` on an array of floating-point values don't simply want *some* deterministic order, but rather an actual increasing order of numeric values.

Hi Xiaodi,

Of course, and the implementors of floating point data types would be expected to do just that. It isn’t hard. For example, in C:

// Make floats sort reliably and sufficiently reasonably
bool sortableLessThan(float x, float y) {
  union {
    int i;
    float f;
  } ux = { .f = x }, uy = { .f = y };
  int high_bit = ~INT_MAX;
  int x2 = ux.i >= 0 ? ux.i : (~ux.i | high_bit);
  int y2 = uy.i >= 0 ? uy.i : (~uy.i | high_bit);
  return x2 < y2;
}

Which the compiler vectorizes down to the following branchless code (which is debatably “reasonable” for sorting):

c.o`sortableLessThan:
c.o[0x0] <+0>:   vinsertps $0x10, %xmm1, %xmm0, %xmm0 ; xmm0 = xmm0[0],xmm1[0],xmm0[2,3] 
c.o[0x6] <+6>:   vmovlps %xmm0, -0x8(%rsp)
c.o[0xc] <+12>:  vpmovsxdq -0x8(%rsp), %xmm0
c.o[0x13] <+19>: vpcmpeqd %xmm1, %xmm1, %xmm1
c.o[0x17] <+23>: vpcmpgtq %xmm1, %xmm0, %xmm1
c.o[0x1c] <+28>: vpor   0x2c(%rip), %xmm0, %xmm2
c.o[0x24] <+36>: vpxor  0x34(%rip), %xmm2, %xmm2  ; (uint128_t) 0x00007fffffff000000007fffffff0000
c.o[0x2c] <+44>: vblendvpd %xmm1, %xmm0, %xmm2, %xmm0
c.o[0x32] <+50>: vmovd  %xmm0, %eax
c.o[0x36] <+54>: vpextrd $0x2, %xmm0, %ecx
c.o[0x3c] <+60>: cmpl   %ecx, %eax
c.o[0x3e] <+62>: setl   %al
c.o[0x41] <+65>: retq   


> Likewise, when someone asks if an array contains a floating-point value (say, `10.0 as Decimal`), they generally want to know if *any* representation of that value exists.

I’ve been thinking about the “contains” API argument a lot today, and I’m of the opinion now that we’re arguing about a problem that doesn’t exist.

The “contains” question doesn’t make sense because of rounding errors that are inherent in floating point arithmetic. People would need to write “.contains(value: x, plusOrMinus: y)” and there is no way that the generic collection types are going to vend such an API. If anything, the “contains” API needs to be limited to types that conform to (hand waving) some kind of “PreciseValue” protocol (which floating point would not). For the exact same rounding-error reasons, I don’t think floating point types should be hashable either.

> The point is that _what kind of substitutability_ matters, and the kind that people will expect for floating-point values is the very mathematical substitutability that is supposed to be guaranteed by Equatable, which simply does not accommodate NaN.


Given that rounding errors make “contains” and “hashing” impractical to use with floating point types, I don’t see any holes with my (hand waving) “Substitutability” proposal. I could be missing something though. Can you think of anything?

Dave
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171025/11a35fce/attachment.html>


More information about the swift-dev mailing list