Making the sign of NaNs unspecified to enable enum layout optimization


(Joe Groff) #1

I had a discussion with Steve this morning about the potential for enum layout optimization with floating-point payloads. One great thing about floating-point is that it has NaNs, and lots of them. For the most part, the only significant semantic difference among these NaNs is whether they're signaling or not, so it's tempting to reclaim some of these representations for other purposes. Javascript engines are of course famous for "NaN-encoding" values, representing JS numbers as native Doubles and packing pointers to non-number object instances into the same representation by using NaN bit patterns. In Swift, we could do similar things for enums with floating-point payloads, making 'Float?' and 'Double?' take the same amount of space as non-optionals, and automatically applying Javascript-style layout optimizations when defining enums with mixed float and object payloads. IEEE 754 is ambivalent about the role of NaN payloads, and there are libraries that use payloads for interesting diagnostic purposes, but the standard declares up front that it "does not interpret the sign of a NaN" (section 6.3). Reserving "negative" NaNs with the sign bit set as extra inhabitants could let us do enum layout optimization without interfering with the ability for libraries to freely use NaN payloads.

However, the way we usually handle enum optimization with extra inhabitants is problematic for floats. We normally say that it is undefined behavior for a value to have an extra inhabitant representation—a class reference cannot be null, a Bool can only be 0 or 1, and so on. With floats, we need to interoperate with numerics code not written in Swift, and we want to be able to read floating-point data out of memory that may use arbitrary bit patterns. We don't want every double-returning C function or load from memory to require a check for reserved values afterward. Making it undefined behavior for floats to have "extra inhabitant" representations is thus probably not practical.

Instead of saying that extra inhabitants are undefined behavior, we could instead continue to allow Floats and Doubles to have arbitrary bit patterns, and only check for reserved values at the point we construct an enum that wants to use reserved values for layout. If we reserve negative NaNs, then for example, constructing a Float? or Double? from a nonoptional value would check whether the payload value is NaN and if so, clear the sign bit at that point. That way, we don't have any ABI problems with Floats and Doubles from foreign sources, but still get the benefits of layout optimization for Swift types. On the other hand, this would mean that supposedly-idempotent operations like '.some(x)!' lose the sign information for NaNs. Since we wouldn't want to prevent the optimizer from folding those kinds of operations away, we could define Swift's semantics to say that querying the sign of a NaN value produces an unspecified value. This matches the intent of IEEE 754, and shouldn't impact most numerics code in practice. If we were interested in pursuing enum layout optimization with float payloads, I think this would be the best approach.

-Joe


(Jordan Rose) #2

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

Jordan

···

On Oct 19, 2016, at 20:42, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

I had a discussion with Steve this morning about the potential for enum layout optimization with floating-point payloads. One great thing about floating-point is that it has NaNs, and lots of them. For the most part, the only significant semantic difference among these NaNs is whether they're signaling or not, so it's tempting to reclaim some of these representations for other purposes. Javascript engines are of course famous for "NaN-encoding" values, representing JS numbers as native Doubles and packing pointers to non-number object instances into the same representation by using NaN bit patterns. In Swift, we could do similar things for enums with floating-point payloads, making 'Float?' and 'Double?' take the same amount of space as non-optionals, and automatically applying Javascript-style layout optimizations when defining enums with mixed float and object payloads. IEEE 754 is ambivalent about the role of NaN payloads, and there are libraries that use payloads for interesting diagnostic purposes, but the standard declares up front that it "does not interpret the sign of a NaN" (section 6.3). Reserving "negative" NaNs with the sign bit set as extra inhabitants could let us do enum layout optimization without interfering with the ability for libraries to freely use NaN payloads.

However, the way we usually handle enum optimization with extra inhabitants is problematic for floats. We normally say that it is undefined behavior for a value to have an extra inhabitant representation—a class reference cannot be null, a Bool can only be 0 or 1, and so on. With floats, we need to interoperate with numerics code not written in Swift, and we want to be able to read floating-point data out of memory that may use arbitrary bit patterns. We don't want every double-returning C function or load from memory to require a check for reserved values afterward. Making it undefined behavior for floats to have "extra inhabitant" representations is thus probably not practical.

Instead of saying that extra inhabitants are undefined behavior, we could instead continue to allow Floats and Doubles to have arbitrary bit patterns, and only check for reserved values at the point we construct an enum that wants to use reserved values for layout. If we reserve negative NaNs, then for example, constructing a Float? or Double? from a nonoptional value would check whether the payload value is NaN and if so, clear the sign bit at that point. That way, we don't have any ABI problems with Floats and Doubles from foreign sources, but still get the benefits of layout optimization for Swift types. On the other hand, this would mean that supposedly-idempotent operations like '.some(x)!' lose the sign information for NaNs. Since we wouldn't want to prevent the optimizer from folding those kinds of operations away, we could define Swift's semantics to say that querying the sign of a NaN value produces an unspecified value. This matches the intent of IEEE 754, and shouldn't impact most numerics code in practice. If we were interested in pursuing enum layout optimization with float payloads, I think this would be the best approach.

-Joe
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev


(John McCall) #3

As an implementation matter, is this going to significantly complicate the "make a T? from an unknown T" path? Currently, I think that logic just asks whether a type has extra inhabitants; it doesn't have any notion of having to rewrite actual values to avoid colliding with the "extra" inhabitants.

John.

···

On Oct 19, 2016, at 8:42 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
I had a discussion with Steve this morning about the potential for enum layout optimization with floating-point payloads. One great thing about floating-point is that it has NaNs, and lots of them. For the most part, the only significant semantic difference among these NaNs is whether they're signaling or not, so it's tempting to reclaim some of these representations for other purposes. Javascript engines are of course famous for "NaN-encoding" values, representing JS numbers as native Doubles and packing pointers to non-number object instances into the same representation by using NaN bit patterns. In Swift, we could do similar things for enums with floating-point payloads, making 'Float?' and 'Double?' take the same amount of space as non-optionals, and automatically applying Javascript-style layout optimizations when defining enums with mixed float and object payloads. IEEE 754 is ambivalent about the role of NaN payloads, and there are libraries that use payloads for interesting diagnostic purposes, but the standard declares up front that it "does not interpret the sign of a NaN" (section 6.3). Reserving "negative" NaNs with the sign bit set as extra inhabitants could let us do enum layout optimization without interfering with the ability for libraries to freely use NaN payloads.

However, the way we usually handle enum optimization with extra inhabitants is problematic for floats. We normally say that it is undefined behavior for a value to have an extra inhabitant representation—a class reference cannot be null, a Bool can only be 0 or 1, and so on. With floats, we need to interoperate with numerics code not written in Swift, and we want to be able to read floating-point data out of memory that may use arbitrary bit patterns. We don't want every double-returning C function or load from memory to require a check for reserved values afterward. Making it undefined behavior for floats to have "extra inhabitant" representations is thus probably not practical.

Instead of saying that extra inhabitants are undefined behavior, we could instead continue to allow Floats and Doubles to have arbitrary bit patterns, and only check for reserved values at the point we construct an enum that wants to use reserved values for layout. If we reserve negative NaNs, then for example, constructing a Float? or Double? from a nonoptional value would check whether the payload value is NaN and if so, clear the sign bit at that point. That way, we don't have any ABI problems with Floats and Doubles from foreign sources, but still get the benefits of layout optimization for Swift types. On the other hand, this would mean that supposedly-idempotent operations like '.some(x)!' lose the sign information for NaNs. Since we wouldn't want to prevent the optimizer from folding those kinds of operations away, we could define Swift's semantics to say that querying the sign of a NaN value produces an unspecified value. This matches the intent of IEEE 754, and shouldn't impact most numerics code in practice. If we were interested in pursuing enum layout optimization with float payloads, I think this would be the best approach.


(Joe Groff) #4

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.

-Joe

···

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com> wrote:


(Joe Groff) #5

It's true that it would no longer be a guaranteed identity operation, but we already have the notion of "inject tag" in the abstract access pattern for enums, which occurs after the payload has been stored, which normally sets the extra tag bits. It seems to me we could also use it to collapse NaN representations when the "some" tag is injected over a float (though we would need a "evacuateExtraInhabitantRepresentations" value witness to do this generically).

-Joe

···

On Oct 20, 2016, at 10:45 AM, John McCall <rjmccall@apple.com> wrote:

On Oct 19, 2016, at 8:42 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:
I had a discussion with Steve this morning about the potential for enum layout optimization with floating-point payloads. One great thing about floating-point is that it has NaNs, and lots of them. For the most part, the only significant semantic difference among these NaNs is whether they're signaling or not, so it's tempting to reclaim some of these representations for other purposes. Javascript engines are of course famous for "NaN-encoding" values, representing JS numbers as native Doubles and packing pointers to non-number object instances into the same representation by using NaN bit patterns. In Swift, we could do similar things for enums with floating-point payloads, making 'Float?' and 'Double?' take the same amount of space as non-optionals, and automatically applying Javascript-style layout optimizations when defining enums with mixed float and object payloads. IEEE 754 is ambivalent about the role of NaN payloads, and there are libraries that use payloads for interesting diagnostic purposes, but the standard declares up front that it "does not interpret the sign of a NaN" (section 6.3). Reserving "negative" NaNs with the sign bit set as extra inhabitants could let us do enum layout optimization without interfering with the ability for libraries to freely use NaN payloads.

However, the way we usually handle enum optimization with extra inhabitants is problematic for floats. We normally say that it is undefined behavior for a value to have an extra inhabitant representation—a class reference cannot be null, a Bool can only be 0 or 1, and so on. With floats, we need to interoperate with numerics code not written in Swift, and we want to be able to read floating-point data out of memory that may use arbitrary bit patterns. We don't want every double-returning C function or load from memory to require a check for reserved values afterward. Making it undefined behavior for floats to have "extra inhabitant" representations is thus probably not practical.

Instead of saying that extra inhabitants are undefined behavior, we could instead continue to allow Floats and Doubles to have arbitrary bit patterns, and only check for reserved values at the point we construct an enum that wants to use reserved values for layout. If we reserve negative NaNs, then for example, constructing a Float? or Double? from a nonoptional value would check whether the payload value is NaN and if so, clear the sign bit at that point. That way, we don't have any ABI problems with Floats and Doubles from foreign sources, but still get the benefits of layout optimization for Swift types. On the other hand, this would mean that supposedly-idempotent operations like '.some(x)!' lose the sign information for NaNs. Since we wouldn't want to prevent the optimizer from folding those kinds of operations away, we could define Swift's semantics to say that querying the sign of a NaN value produces an unspecified value. This matches the intent of IEEE 754, and shouldn't impact most numerics code in practice. If we were interested in pursuing enum layout optimization with float payloads, I think this would be the best approach.

As an implementation matter, is this going to significantly complicate the "make a T? from an unknown T" path? Currently, I think that logic just asks whether a type has extra inhabitants; it doesn't have any notion of having to rewrite actual values to avoid colliding with the "extra" inhabitants.


(Kenny Leung) #6

nimoy-interview.png.jpg


(Jordan Rose) #7

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

Right, that’s sort of my point. If you’re using NaN payloads for non-float-related information, you shouldn’t be using the bit that’s part of the floating-point standard. But I could also see plenty of people saying “we’re not going to waste a whole bit” and not bothering to distinguish it from the rest.

At the same time, I can certainly see people saying “hey, an extra bit” about the sign bit. If you’re using NaN payloads, you probably are going to check for that before performing any operations on the NaN, rather than relying on nil-swallowing NaN-propagation doing what your program requires.

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.

I don’t think I agree with either of those sentences. I’d really like the story to be either “we treat different NaN bit strings as distinct” or “there are no meaningful distinctions between NaNs in Swift (except maybe sNaN vs. qNaN); if you want anything more you need to use Int as your storage type”. Each of those has natural consequences for me concerning both extra inhabitants and total ordering.

Jordan

···

On Oct 20, 2016, at 10:04, Joe Groff <jgroff@apple.com> wrote:

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com> wrote:


(Stephen Canon) #8

In particular, the language doesn’t guarantee to preserve the representation exactly specifically **for conversions to Float? and back**. IEEE 754 has no notion of optionals, so the IEEE 754 rules don’t directly constrain the design space here.

The primary constraint is that conversion to Optional and back should preserve values. I don’t think that it needs to preserve *encodings*, however (e.g. IEEE 754 conversions canonicalize decimal significands, and I’m OK with conversions to/from Optional doing the same; we can mod NaNs out by some reserved payload bit and call them different encodings of the same NaN value and the same rationale applies).

Preserving values implies preserving substitutability. That should preserve nan-ness for sure, and should either preserve signaling-ness or actually “signal” (in the IEEE 754 sense) at the point of conversion to Optional. One can argue that preserving the signbit of the NaN would be nice (for substitutability in copysign), but one can also argue that this is really a property of the encoding, not the value.

Like Joe, I don’t think that comparison really enters into this (the issue was never totally resolved to my understanding, but my recollection is that we mostly left it as "<=> should order according to the IEEE 754 level 2 abstraction”—meaning all NaNs are equal to each other for the purposes of <=>).

I would be pretty opposed to claiming sNaNs for this purpose. The two better options I see are:

  - Use the signbit of NaN.
  - Reserve NaNs whose significand begins with `b11` (these bit patterns are already reserved by the `Float(nan: signaling:)` constructor).

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

– Steve

···

On Oct 20, 2016, at 10:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com> wrote:

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.


(John McCall) #9

This seems reasonable. We could use the same thing to take advantage of spare bits that the type doesn't promise to initialize, e.g. in a struct with internal padding.

John.

···

On Oct 20, 2016, at 10:50 AM, Joe Groff <jgroff@apple.com> wrote:

On Oct 20, 2016, at 10:45 AM, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Oct 19, 2016, at 8:42 PM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
I had a discussion with Steve this morning about the potential for enum layout optimization with floating-point payloads. One great thing about floating-point is that it has NaNs, and lots of them. For the most part, the only significant semantic difference among these NaNs is whether they're signaling or not, so it's tempting to reclaim some of these representations for other purposes. Javascript engines are of course famous for "NaN-encoding" values, representing JS numbers as native Doubles and packing pointers to non-number object instances into the same representation by using NaN bit patterns. In Swift, we could do similar things for enums with floating-point payloads, making 'Float?' and 'Double?' take the same amount of space as non-optionals, and automatically applying Javascript-style layout optimizations when defining enums with mixed float and object payloads. IEEE 754 is ambivalent about the role of NaN payloads, and there are libraries that use payloads for interesting diagnostic purposes, but the standard declares up front that it "does not interpret the sign of a NaN" (section 6.3). Reserving "negative" NaNs with the sign bit set as extra inhabitants could let us do enum layout optimization without interfering with the ability for libraries to freely use NaN payloads.

However, the way we usually handle enum optimization with extra inhabitants is problematic for floats. We normally say that it is undefined behavior for a value to have an extra inhabitant representation—a class reference cannot be null, a Bool can only be 0 or 1, and so on. With floats, we need to interoperate with numerics code not written in Swift, and we want to be able to read floating-point data out of memory that may use arbitrary bit patterns. We don't want every double-returning C function or load from memory to require a check for reserved values afterward. Making it undefined behavior for floats to have "extra inhabitant" representations is thus probably not practical.

Instead of saying that extra inhabitants are undefined behavior, we could instead continue to allow Floats and Doubles to have arbitrary bit patterns, and only check for reserved values at the point we construct an enum that wants to use reserved values for layout. If we reserve negative NaNs, then for example, constructing a Float? or Double? from a nonoptional value would check whether the payload value is NaN and if so, clear the sign bit at that point. That way, we don't have any ABI problems with Floats and Doubles from foreign sources, but still get the benefits of layout optimization for Swift types. On the other hand, this would mean that supposedly-idempotent operations like '.some(x)!' lose the sign information for NaNs. Since we wouldn't want to prevent the optimizer from folding those kinds of operations away, we could define Swift's semantics to say that querying the sign of a NaN value produces an unspecified value. This matches the intent of IEEE 754, and shouldn't impact most numerics code in practice. If we were interested in pursuing enum layout optimization with float payloads, I think this would be the best approach.

As an implementation matter, is this going to significantly complicate the "make a T? from an unknown T" path? Currently, I think that logic just asks whether a type has extra inhabitants; it doesn't have any notion of having to rewrite actual values to avoid colliding with the "extra" inhabitants.

It's true that it would no longer be a guaranteed identity operation, but we already have the notion of "inject tag" in the abstract access pattern for enums, which occurs after the payload has been stored, which normally sets the extra tag bits. It seems to me we could also use it to collapse NaN representations when the "some" tag is injected over a float (though we would need a "evacuateExtraInhabitantRepresentations" value witness to do this generically).


(Joe Groff) #10

JavaScript goes as far as saying that there's semantically only one NaN value. We could reasonably do the same (though I think there's value in preserving 'sNaN' and 'qNaN'), since hardware and libm already make basically no portable guarantees about what NaN representation you get. That might make it less morally wrong to sometimes treat all NaNs uniformly and sometimes preserve them.

-Joe

···

On Oct 20, 2016, at 10:35 AM, Jordan Rose <jordan_rose@apple.com> wrote:

On Oct 20, 2016, at 10:04, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote:

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

Right, that’s sort of my point. If you’re using NaN payloads for non-float-related information, you shouldn’t be using the bit that’s part of the floating-point standard. But I could also see plenty of people saying “we’re not going to waste a whole bit” and not bothering to distinguish it from the rest.

At the same time, I can certainly see people saying “hey, an extra bit” about the sign bit. If you’re using NaN payloads, you probably are going to check for that before performing any operations on the NaN, rather than relying on nil-swallowing NaN-propagation doing what your program requires.

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.

I don’t think I agree with either of those sentences. I’d really like the story to be either “we treat different NaN bit strings as distinct” or “there are no meaningful distinctions between NaNs in Swift (except maybe sNaN vs. qNaN); if you want anything more you need to use Int as your storage type”. Each of those has natural consequences for me concerning both extra inhabitants and total ordering.


(Joe Groff) #11

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

-Joe

···

On Oct 20, 2016, at 10:38 AM, Stephen Canon <scanon@apple.com> wrote:

On Oct 20, 2016, at 10:04 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com> wrote:

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.

In particular, the language doesn’t guarantee to preserve the representation exactly specifically **for conversions to Float? and back**. IEEE 754 has no notion of optionals, so the IEEE 754 rules don’t directly constrain the design space here.

The primary constraint is that conversion to Optional and back should preserve values. I don’t think that it needs to preserve *encodings*, however (e.g. IEEE 754 conversions canonicalize decimal significands, and I’m OK with conversions to/from Optional doing the same; we can mod NaNs out by some reserved payload bit and call them different encodings of the same NaN value and the same rationale applies).

Preserving values implies preserving substitutability. That should preserve nan-ness for sure, and should either preserve signaling-ness or actually “signal” (in the IEEE 754 sense) at the point of conversion to Optional. One can argue that preserving the signbit of the NaN would be nice (for substitutability in copysign), but one can also argue that this is really a property of the encoding, not the value.

Like Joe, I don’t think that comparison really enters into this (the issue was never totally resolved to my understanding, but my recollection is that we mostly left it as "<=> should order according to the IEEE 754 level 2 abstraction”—meaning all NaNs are equal to each other for the purposes of <=>).

I would be pretty opposed to claiming sNaNs for this purpose. The two better options I see are:

  - Use the signbit of NaN.
  - Reserve NaNs whose significand begins with `b11` (these bit patterns are already reserved by the `Float(nan: signaling:)` constructor).

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.


(Jordan Rose) #12

Joe, Steve, and Dave Abrahams convinced me that this is a fairly good encoding for NaN-payloads in general, and probably one that’s still compatible with real systems in practice. If anyone really needs that last bit of qNaN payload, they can inspect the bit pattern directly, and if they need to distinguish different NaNs in a Set or Dictionary the element type shouldn’t be Float/Double.

Thanks for talking this all through with me.
Jordan

···

On Oct 20, 2016, at 12:59, Joe Groff <jgroff@apple.com> wrote:

On Oct 20, 2016, at 10:38 AM, Stephen Canon <scanon@apple.com <mailto:scanon@apple.com>> wrote:

On Oct 20, 2016, at 10:04 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Oct 20, 2016, at 9:42 AM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote:

Some disconnected thoughts:

- “Does not interpret” does not mean “does not preserve”. The very next sentence in the standard is "Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand."

- If we were to claim a class of NaNs, I would pick signalling NaNs rather than positive or negative ones. AFAIK most NaN-embedding tricks avoid signalling NaNs because they can, well, signal, even though (again AFAIK) most modern systems don’t bother.

Claiming sNaNs would be unfortunate since "signaling" is about the only semantically distinct bit NaNs normally have, and I think we should minimize interference with users who are taking advantage of signaling or NaN payloads for their own means. (OTOH, on some platforms like x87 it's already practically impossible to preserve the signaling bit, since even loads will immediately raise the exception and quiet the NaN, and there would be some nice safety benefits to getting a trap early if a Float? is bitcast to a Float without being formally checked first.)

- I don’t feel like we have a coherent story here. We know that APIs taking “Double” or “Float” can represent any bit pattern. The last plan I heard for floating-point comparison treats NaNs as unordered relative to one another, even in a total order comparison. (I maintain that this is unsound.) And this proposal would treat some or all NaNs as invalid. I feel like we need to pick one approach here.

I'm not saying that they'd be invalid, only that the language doesn't guarantee to preserve these representations exactly. That seems orthogonal to the comparison issue—whatever rule we come up with for float ordering, all NaNs ought to be treated uniformly by that rule.

In particular, the language doesn’t guarantee to preserve the representation exactly specifically **for conversions to Float? and back**. IEEE 754 has no notion of optionals, so the IEEE 754 rules don’t directly constrain the design space here.

The primary constraint is that conversion to Optional and back should preserve values. I don’t think that it needs to preserve *encodings*, however (e.g. IEEE 754 conversions canonicalize decimal significands, and I’m OK with conversions to/from Optional doing the same; we can mod NaNs out by some reserved payload bit and call them different encodings of the same NaN value and the same rationale applies).

Preserving values implies preserving substitutability. That should preserve nan-ness for sure, and should either preserve signaling-ness or actually “signal” (in the IEEE 754 sense) at the point of conversion to Optional. One can argue that preserving the signbit of the NaN would be nice (for substitutability in copysign), but one can also argue that this is really a property of the encoding, not the value.

Like Joe, I don’t think that comparison really enters into this (the issue was never totally resolved to my understanding, but my recollection is that we mostly left it as "<=> should order according to the IEEE 754 level 2 abstraction”—meaning all NaNs are equal to each other for the purposes of <=>).

I would be pretty opposed to claiming sNaNs for this purpose. The two better options I see are:

  - Use the signbit of NaN.
  - Reserve NaNs whose significand begins with `b11` (these bit patterns are already reserved by the `Float(nan: signaling:)` constructor).

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.


(Chris Lattner) #13

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

-Chris

···

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.


(Joe Groff) #14

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

-Joe

···

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.


(John McCall) #15

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, ...

John.

···

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.


(Stephen Canon) #16

The test for detecting the reserved encoding is essentially identical either way (pseudo-assembly):

  detectNegativeNaN:
    ADD encoding, encoding, 0x0010000000000000
    JC nil

  detectLeading11NaN:
    ADD encoding, encoding, 0x0004000000000000
    JO nil

– Steve

···

On Oct 24, 2016, at 2:55 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, …


(John McCall) #17

Sure, that's basically just a different way of spelling the comparison. For the most part, though, Swift will not need to perform this operation; it'll be checking for a specific value. I don't see any reason to say that e.g. .none can be encoded by an arbitrary reserved NaN rather than a specific one.

Anyway, we're agreed that both representations require doing integer comparisons on the value, not FP comparisons, and so operations on Float? will generally require moving the value between register banks if we do this. It's not as pure a win as we might hope. Still probably worthwhile, though.

John.

···

On Oct 24, 2016, at 12:30 PM, Stephen Canon <scanon@apple.com> wrote:

On Oct 24, 2016, at 2:55 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, …

The test for detecting the reserved encoding is essentially identical either way (pseudo-assembly):

  detectNegativeNaN:
    ADD encoding, encoding, 0x0010000000000000
    JC nil

  detectLeading11NaN:
    ADD encoding, encoding, 0x0004000000000000
    JO nil


(Jordan Rose) #18

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, …

The test for detecting the reserved encoding is essentially identical either way (pseudo-assembly):

  detectNegativeNaN:
    ADD encoding, encoding, 0x0010000000000000
    JC nil

  detectLeading11NaN:
    ADD encoding, encoding, 0x0004000000000000
    JO nil

Sure, that's basically just a different way of spelling the comparison. For the most part, though, Swift will not need to perform this operation; it'll be checking for a specific value. I don't see any reason to say that e.g. .none can be encoded by an arbitrary reserved NaN rather than a specific one.

That doesn't quite happen when the other case also has a payload.

enum SmallIntOrBigFloat {
  case small(Int8)
  case big(Double)
}

Jordan

···

On Oct 24, 2016, at 12:58, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Oct 24, 2016, at 12:30 PM, Stephen Canon <scanon@apple.com> wrote:

On Oct 24, 2016, at 2:55 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

Anyway, we're agreed that both representations require doing integer comparisons on the value, not FP comparisons, and so operations on Float? will generally require moving the value between register banks if we do this. It's not as pure a win as we might hope. Still probably worthwhile, though.


(John McCall) #19

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, …

The test for detecting the reserved encoding is essentially identical either way (pseudo-assembly):

  detectNegativeNaN:
    ADD encoding, encoding, 0x0010000000000000
    JC nil

  detectLeading11NaN:
    ADD encoding, encoding, 0x0004000000000000
    JO nil

Sure, that's basically just a different way of spelling the comparison. For the most part, though, Swift will not need to perform this operation; it'll be checking for a specific value. I don't see any reason to say that e.g. .none can be encoded by an arbitrary reserved NaN rather than a specific one.

That doesn't quite happen when the other case also has a payload.

enum SmallIntOrBigFloat {
  case small(Int8)
  case big(Double)
}

I don't know if we actually do that particular optimization, but sure, there are situations where this comes up. The more important one to my mind is that the value witnesses for Float will have to return an abstract index; that's the path that will be used by generic code that's working with a T?.

John.

···

On Oct 24, 2016, at 1:07 PM, Jordan Rose <jordan_rose@apple.com> wrote:

On Oct 24, 2016, at 12:58, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Oct 24, 2016, at 12:30 PM, Stephen Canon <scanon@apple.com <mailto:scanon@apple.com>> wrote:

On Oct 24, 2016, at 2:55 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com <mailto:clattner@apple.com>> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Jordan

Anyway, we're agreed that both representations require doing integer comparisons on the value, not FP comparisons, and so operations on Float? will generally require moving the value between register banks if we do this. It's not as pure a win as we might hope. Still probably worthwhile, though.


(Joe Groff) #20

copysign( ) is a reason to not pick the first option. I’m not very worried about it, but it is a reason. I see no problem with the second option.

As we discussed in person this morning, de-canonicalizing b11 might be a better compromise to minimize the potential impact of layout optimizations. That would leave the implementation with 2^51 NaN representations (50 significand bits, plus the sign bit) in Double to play with, which ought to be enough for anyone™. I liked the idea of using the sign bit originally since testing for NaNs and sign bits is something that can be easily done using common FPU instructions without crossing domains, but as you noted, it sounds like comparison and branching operations tend to do that anyway, so masking and branching using integer operations shouldn't be too much of a burden. Jordan's question of to what degree we consider different NaN encodings to be distinct semantic values is still an interesting one, but if we take only the b11 NaN payloads away, that should minimize the degree to which the implementation needs to be considered as a constraint in having that discussion.

To your original email, I agree this is an important problem to tackle, and that we should handle the inhabitant masking when the FP value is converted to optional.

That said, I don’t understand the above. With the “b11” representation, what how is a "Double?" tested for “.None"? One advantage of using the signbit is that “is negative” comparisons are very cheap on risc systems, because you don’t have to materialize a large/weird immediate.

That's why I liked using the sign bit originally too. Steve noted that, since any operation on an Optional is probably going to involve testing and branching before revealing the underlying float value, and float comparisons and branches tend to unavoidably burn a couple cycles engaging the integer ALU, there's unlikely to be much benefit on ARM or Intel avoiding integer masking operations. (More strictly RISCy architectures like Power would be more negatively impacted, perhaps.) On ARM64 at least, the bitmask for a b11 NaN is still representable as an immediate, since it involves a single contiguous run of 1 bits.

There isn't any efficient way of just testing the sign bit of a value using FP instructions that I can see. You could maybe take advantage of the vector registers overlapping the FP registers and use integer vector operations, but it would take a lot of code and have false-dependency problems. So in both representations, the most efficient test sequence seems to be (1) get value in integer register (2) compare against some specific integer value. And in that case, in both representations it seems to me that the obvious extra-inhabitant sequence is 0xFFFFFFFF, 0xFFFFFFFE, …

The test for detecting the reserved encoding is essentially identical either way (pseudo-assembly):

  detectNegativeNaN:
    ADD encoding, encoding, 0x0010000000000000
    JC nil

  detectLeading11NaN:
    ADD encoding, encoding, 0x0004000000000000
    JO nil

Sure, that's basically just a different way of spelling the comparison. For the most part, though, Swift will not need to perform this operation; it'll be checking for a specific value. I don't see any reason to say that e.g. .none can be encoded by an arbitrary reserved NaN rather than a specific one.

When we know there's exactly one no-payload case, as with .none in Optional, we do have the option of testing for an arbitrary extra inhabitant if it happens to be cheaper/smaller code, since having any extra inhabitant representation other than the first would be UB anyway. In these cases, either the mask or first inhabitant should fit in an ARM64 bitmask immediate, and are a 64-bit movabs on Intel either way, so it's probably not worthwhile.

Anyway, we're agreed that both representations require doing integer comparisons on the value, not FP comparisons, and so operations on Float? will generally require moving the value between register banks if we do this. It's not as pure a win as we might hope. Still probably worthwhile, though.

Right. Since there's no perf benefit to using the sign bit, using b11 payloads has the least potential of interfering with users trying to use specific NaN encodings for their own purposes.

-Joe

···

On Oct 24, 2016, at 12:58 PM, John McCall <rjmccall@apple.com> wrote:

On Oct 24, 2016, at 12:30 PM, Stephen Canon <scanon@apple.com> wrote:

On Oct 24, 2016, at 2:55 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Oct 24, 2016, at 8:49 AM, Joe Groff via swift-dev <swift-dev@swift.org> wrote:

On Oct 22, 2016, at 10:39 AM, Chris Lattner <clattner@apple.com> wrote:

On Oct 20, 2016, at 2:59 PM, Joe Groff via swift-dev <swift-dev@swift.org> wrote: