NaN canonicalization

Some popular source languages don't have the ability to preserve NaN bit patterns. For example, JS has only a single NaN value, and makes no guarantees about preserving specific bit patterns. NaN bit patterns could become an API feature that some implementation source languages support that others don't. Consequently, interface types should consider canonicalizing NaNs in f32 and f64 values at interface boundaries.

Good observation! I agree.

I can think of two design principles that would motivate this:

Determinism/predictability: Languages that only deal in single, canonical NaNs should not have to deal with receiving non-canonical NaNs across interface boundaries. (Although what problems could this cause? Could those languages just reat canonical and non-canonical NaNs uniformly?
Declaration of intent: Semantically, floats are not supposed to express arbitrary bits, so interface declarations are simpler and clearer if NaN boxing cannot possibly be part of the interface and if documented interfaces cannot possibly try to promise that the NaN payloads will be preserved.

Are those the principles motivating this suggestion, or am I off base? Regardless, are the underlying design principles documented anywhere?

I'm thinking about this in the context of this part of the interface-types motivation:

As part of this maximum-reuse profile, the language and toolchain that a module author uses should be kept an encapsulated module implementation detail allowing module clients to independently choose their own language and toolchain.

To promote maximal reuse, we should discourage APIs that rely on NaN bits to convey meaningful information, because such APIs wouldn't be accessible from JS or other languages with a single NaN.

The reasoning seems to be that interface types should restrict communication between components to information that all languages can retain in their obvious representation without loss. That seems to be adding yet another scope creep to interface types, and one that's fairly fuzzy.

Also, there's nothing that says that an interface-types f64 has to lower to a double in JS—a JS program could specify a non-canonical lowerer that lowers it to a BigInt via its bits. Sure that causes boxing, but so does lowering i32 to Int32 in OCaml; I imagine we aren't planning to limit i32 to 31-bit integers, but such a limitation seems to be advocated by the same reasoning. For OCaml, I would expect the tooling for generating a converter from an interface type to OCaml data will, by default, lower i32 to int, but will also have an option for lowering to Int32 as well.

There also might be a cost to this. I imagine some day we will have bulk operations for lifting and lowering list f64. Fusing a bulk lift with a bulk lower could result in simply a memcpy. But the restriction here would require canonicalization as well.

To be sure, I'm still exploring the space here.

One option would be to say that it's nondeterministic whether NaNs are canonicalized at boundaries. That would let implementations skip the overhead, but still signal the intent of f32 and f64 and allow JS and others to participate with their main number types.

Another option would be to observe that NaN canonicalization is SIMD-optimizable, so we may be able to make it fairly fast. It still wouldn't be free though, especially for small-to-medium arrays.

Does OCaml have a way of representing a value which is unboxed if it's in the 31-bit integer range, and boxed otherwise? Could it use its tagged integer representation for this? If so, it wouldn't have to box in the common case, and it wouldn't have to fail on values that other languages accept.

@sunfishcode

That seems to be adding yet another scope creep to interface types, and one that's fairly fuzzy.

Regardless of what the answer to this technical question is, as of the vote on the scope yesterday, this sort of question seems squarely within the scope of interface types (and the component model), specifically under promoting cross-language interopability. This isn't the first time this sort of question has popped up and it won't be the last. In all these sorts of questions, there is an inherent tension between expressing every last thing a particular language might want and defining language-agnostic interfaces that are widely implementable.

By way of comparison, I'd be surprised if COM or protobufs makes any guarantees about preserving NaN payloads across interfaces. That would mean that they've implicitly chosen the "non-deterministically canonicalize NaNs" route @sunfishcode suggested is another option above. Given wasm's emphasis on determinism, it makes sense for us to ask if we should choose differently.

I think there's a third motivation in addition to the two @tlively gave: if f64 carries non-canonical NaN payloads, it may force a toolchain (which knows nothing of the specific workloads it is being used to compile) to conservatively decide that it must preserve non-canonical payloads (b/c some other toolchain does, thus parity) incurring extra cost (not just at the boundary, but potentially within the body of computation as well) -- concretely I'm thinking about this harming NaN-boxing engines. If the cost of NaN-canonicalization was significant, then this would be a tough tradeoff, but as @sunfishcode says, it's quite cheap these days, and I expect insignificant in the context of a cross-component call.

This isn't the first time this sort of question has popped up and it won't be the last. In all these sorts of questions, there is an inherent tension between expressing every last thing a particular language might want and defining language-agnostic interfaces that are widely implementable.

Yes, these sorts of questions will come up regularly. One way to resolve them is to have everyone fight over an answer, pick a winner, and then apply that solution to everyone. That strategy results in lots of fights and comes out with winners and losers.

Another way to resolve them is to find a way to accommodate everyone's needs. Adapters (even simple ones) and fusion provide a great way to make this possible. For example, a producer of an API for which NaNs are supposed to be insignificant can use an f64.lift_canonicalize_nan operation. This ensures consumers do not depend on insignificant nan information, and it also informs tooling that nan's are not significant and can be optimized appropriately. Similarly, a consumer of such an API can use an f64.lower_canonicalize_nat operation. The fuser, when it matches lift_canonicalize_nan with lower_canonicalize_nan can easily avoid canonicalizing twice.

Meanwhile, an API intended for efficient numeric programs (and which has little interest in JS programs) can still use interface types as a means of efficient shared-nothing data transfer. Their needs are not bottlenecked by others' irrelevant needs.

As a bonus, if the numeric program using the API happens to rely on NaN canonicalization for its own purposes, it can use lower_canonicalize_nan to make the data conform to the program's internal invariants as it is transferred. If it has a specific canonicalization it relies on, it can specify the bit pattern as an argument to lower_canonicalize_nan.

I would rather interface types offer options to people rather than impose choices on people (of course, so long as it also provides sufficient isolation so that others' choice of the available options does not interfere with one's own choice).

This is perfectly reasonable: to have more than one coercion operation. That is one of the fundamental merits of the adapter fusion approach.
There is, of course, a counter argument: the existence of lower_canonicalize_nan is embodying the possibility of additional semantics that is not adequately modeled in the type signature. To maximize interoperability, especially across ownership boundaries, we should have as much a 'universal' interpretation as is possible.

I'm not sure I follow the counter argument. The consumer is generally free to do whatever it wants with the data. If you didn't provide lower_canonicalize_nan, it could still canonicalize the NaN itself. By providing a specialized adapter for it, you enable optimizations that the consumer cannot employ on its own: eliminating the canonicalization if the lifter already did so, or using hardware accelerating to perform the canonicalization during the transfer. So, semantically speaking we're not adding anything that wasn't already possible—it's just a performance optimization.

Should it be possible to declare an interface with an f64 argument where the NaN bits are a significant part of the interface contract?

Choices so far include:

Yes, so some source languages can't map f64 to their main number types.
Yes, some source languages just can't be used to implement some interfaces.
No, NaNs are always canonicalized at interfaces.
No, it's nondeterministic whether NaNs are canonicalized at interfaces.

The choice I suggested was:

Yes, but some programs in some languages will need to not use the default mapping for f64 and instead map to some more complete representation (e.g. BigInt) in order to access/provide the full range of functionality permitted/required by the interface.

In fact, the (non-default) lowerer for JS could lower to the number type for non-NaNs and lower to BigInt for NaNs.

It seems like a reasonable balance that also allows for incremental progress would be

no canonicalization in interface types itself
for the canonical ABI and JS, interface type floats turn into Numbers and NaNs get canonicalized just like they do with the regular Wasm -> JS value semantics
when we eventually have adapter functions, JS programs can do whatever they want, such as turn NaNs into BigInts

Depends on what the goal is. If maximum interoperability is then canonicalization seems essential

When I was helping with the early days of Kotlin, they wanted to interop with Java but to also be nulll-safe, which posed an obvious problem. The solution strategy I developed for them at a high-level was to have an ergonomic default—the type-checker would treat Java values as non-null but automatically insert checks where such assumptions were made—but also a more manual fallback—the type-checker would also recognize Java values were potentially non-null and still permit programmers to test them for nullness before automatically inserting checks. That interop strategy was quite successful and is analogous to what I am suggesting here.

Okay, so we're back to not treating this as a problem about multi-language interop, but rather specifically about floating-point.

There are real practical downsides (listed above) with allowing non-canonical NaNs to cross boundaries and I think all the use cases for supporting non-canonical NaNs are hypothetical.

I gave real existing libraries that real existing languages currently link to in a cross-language shared-nothing manner, and the specifications of those APIs explicitly state requirements (in line with IEEE 754-2019 recommendations) that cannot be supported with NaN canonicalization. As many language runtimes link against a foreign-implemented library for these floating-point libraries (and expect them to preserve NaN payloads per IEEE 754 recommendations), such a component would provide a service that could be shared by many programs implemented across many languages. Could you articulate why you believe this is not a viable use case for interface types?

While you've listed some hypothetical downsides, they did not seem to me to be articulated in sufficient depth to assert that they were real and practical. It would help me understand your perspective better if you were to elaborate on (one of) them further. For example, you mention tooling, but I don't see how NaN canonicalization would affect tools like LLVM/Binaryen—you have to know how the rest of the program handles (or ignores) NaNs, which only the programmer knows and hence there already exist various compiler flags to indicate how much flexibility to grant the compiler with respect to floating-point values. Maybe you have something else in mind, but without an elaboration on what that something is I have a hard time seeing how NaN canonicalization would have a real practical benefit for tooling.

Late to this party, and I am not an expert in this area so feel free to ignore, but my gut reaction is that defaulting to canonicalization would not be desirable. My thinking:

An f64 is just a bucket of 64 bits of which each combination is assigned meaning by the IEEE standard.. saying that we only support a subset of combinations seems counter to the low level nature of Wasm.
The existing f64 already is specced to support all combinations, so we'd need the interface type to not be name f64 if we wanted to be very strict about what kind of data-type this is.
A language like JS can read serialized floats from all sorts of sources and already has to deal with canonicalization itself. If you're writing data processing in JS that must roundtrip, then you have to avoid this somehow. To me, this wouldn't be any different if JS code deals with data coming from IT.
Generally IT has the philosophy that if two languages agree on data format there should be no additional overhead, so C sending data to Rust should not be subject to unnecessary conversions.

So my solution would be for f64 to continue to mean that all bits have meaning in all combinations, but that adapters for individual languages can decide to either canonicalize or use raw bits storage. It be up to programmers to know if a language is suitable for implementing a particular interface, much like they already must know that they can't roundtrip serialized data using certain data types.

That, or introduce a c64 type :P

I gave real existing libraries that real existing languages currently link to in a cross-language shared-nothing manner, and the specifications of those APIs explicitly state requirements (in line with IEEE 754-2019 recommendations) that cannot be supported with NaN canonicalization.

If we were to compile that OpenLibm acos code to WebAssembly, today, we'd get a function which can return nondeterministic NaN bits. This is because core wasm's own arithmetic operators don't guarantee to propagate NaN payloads. Consequently, that OpenLibm acos example already doesn't satisfy use cases that require NaN propagation.

It would be easy to modify the code to do what .NET does to ensure IEEE compliance. Right now, the functions in those libraries have typically just one line that relies on the fact that either x+x or (x-x)/(x-x) preserves NaN payloads on IEEE-754-2019-compliant hardware, so you could easily make the change in the C source code without having to do anything specifically in WebAssembly (and without meaningfully changing performance since these lines are off the hot path). This would be in line with changes these libraries have made to accommodate buggy compilers and buggy hardware.

More generally, on a platform where add, sub, mul and sqrt don't propagate NaN payloads, how important is it for acos to propagate NaN payloads?

Two thoughts:

While those instructions are not guaranteed to propagate NaN payloads, they are generally implemented with common instructions/libraries, and so based on these libraries' experiences I wouldn't be surprised if in practice wasm propagates NaN payloads fairly reliably (though I do know there have been some weird cases identified in SIMD). You could probably compile the above libraries to wasm without change and see them still preserve NaNs despite the lack of guarantees.
That aside, it's easy to have a compiler generate NaN-guards around these instructions. I suspect any program really wanting to ensure cross-platform determinism will do so.

I get why add and such are not guaranteed to propagate NaN payloads in wasm (though it might be reasonable to require that they do when all inputs have the same payload): due to the variation of hardware, we'd have to go out of our way to make this deterministic and take a performance hit for it. But NaN canonicalization in interface types would be going out of our way to remove existing functionality while adding additional complexity (because now lowering has to specify a canonical NaN—I've found existing systems with different choices of canonical NaNs), and I don't (yet) see the benefit of that.

I've looked around for a source for .NET needing NaN payload propagation functionality and not been able to find one yet.
IEEE 754 says "should" and not "shall". EMCA-335, the spec for .NET, says "this standard does not specify how to access the exact bit pattern of NaNs that are created". If specs or real-world use cases need NaN payloads to be propagated, I'm genuinely curious to learn more.

@sunfishcode

@sunfishcode There are some links I can fish up on this that you might like, but it looks like I won't have time to re-find them until Friday. Sorry for the delay.

First, for some context on IEEE 754, this document provides some useful background for the most recent changes:

All new operations are “recommended” even when we really meant “required,” to retain upward
compatibility from 754-2008.

Among these new operations are getPayload, setPayload, and setPayloadSignaling, and among the changes 2019 made to 2008 is more explicit specification of binary representation of NaNs (such as how quiet vs. signaling should be represented). This suggests to me that there's pressure to make NaN payloads more standardized and accessible, but there are obstacles with backwards compatibility for existing hardware, and this seems to be what they found to be the compromise.

As for .NET, unfortunately the language spec significantly underspecifies many things. So you have to dig through the code comments and repo history for the specification "in practice". That link above is one example I found indicating they want IEEE conformance. This comment suggests they believe it makes the platform more appealing to numerical libraries:

Being able to say that we are IEEE compliant for required operations is something that can be quite important for various numerics libraries, for porting code from native, and for determinism across platforms.

Interestingly, there happens to be this recent issue about a problem caused by (unintentional) NaN canonicalization filed by a customer here expressing this concern:

This can be an issue if the application works with binary serialization formats that store double or float values in the form of the bits that make them up, because converting those bits to double or float with these BitConverter methods may make round-tripping that double or float not always possible.

That seems like a concern that would apply to components for (de)seriallizing numerical data.

Digging around, it seems that some statistics software indeed make use of NaN payloads. One concrete example I found was that R uses payloads to distinguish between NA_real_ (meaning missing real-valued data) and NaN (meaning numerical error). This distinction has semantic significance. For example, if you run a survey, you're supposed to use NA to indicate when a participant did not supply an answer, and R functions handle NA values accordingly. Many of these functions rely on the fact that payloads are preserved (so that if you make a new column based on some function of other columns, it will have an NA row (rather than NaN) entry whenever that row's value was dependent on data that was not available), though this documentation notes the non-determinism when there are NaNs in the mix:

Numerical computations using NA will normally result in NA: a possible exception is where NaN is also involved, in which case either might result (which may depend on the R platform).

Hope that helped satiate your curiosity!

The evidence I would like to see is users (of floating point libraries) actually caring about NaN payloads. From what I've heard of the history of this feature, the use case that motivated the whole concept of NaN payloads (stuffing error codes into NaNs that implicitly propagate along with the float values) never actually materialized. Or, said differently: if IT canonicalized NaN payloads, it sounds like no end user would actually notice, much less complain.

And, to reiterate what I said above: if someone did actually notice, due again to the high divergence in NaN-payload propagation, the right solution would be to add a separate type that explicitly called out "I care about the NaN payload", so that the interface contract is explicit and extra steps could be taken on languages that didn't propagate NaN payloads by default. This isn't hypothetical: this is what SpiderMonkey actually had to do in the past to implement the .wast test suite when it was compiled to JS and what SpiderMonkey-on-wasm would want to do if such NaN-payload use cases ever materialized.

The evidence I would like to see is users (of floating point libraries) actually caring about NaN payloads.

R programs are linked against a component (not written in R) providing IEEE-compliant implementations of common floating-point numbers. These programs rely on the fact that such a component preserves payloads and thereby maintains the distinction between NA in R and NaN in R, which is semantically significant.

Googling how R uses NaN payloads, I only see mention of the special "NA" value, with links to R documentation explaining that the propagation of NA is unreliable and varies by platform and compiler, which reinforces the overall point made by this issue that non-canonical NaNs are a source of importability and should not be relied upon. Moreover, due to this loose R spec language, coercing NA to a canonical NaN is allowed, so it's not clear whether, to my final question, any end user would actually notice NA vs. NaN.

More generally, my assumption here is that the cross-language interop in the particular case of R is only between the usual C-family set of ABI-compatible languages which would naturally depend on shared-everything linking due to the prevalent use of shared linear memory in these math-intensive types libraries (e.g., when passing a matrix or large vector). Thus, I don't think this concrete example would be an instance of cross-component NaN payload propagation, but rather another instance of shared-everything linking. Another example would be Rust using C-implemented libc or libm.

Most generally, due to the R-documented portability problems, if R wanted to provide deterministic NA semantics and support fully cross-language shared-nothing-linking, then the only robust option would be to keep NA as an implementation detail of the R component and reflect NA in public interfaces as explicit types that will show up well in all languages, like variants with error cases that have explicit payloads.

I know we are talking about IEEE 754 here, where NaN bit patterns were designed to provide error handling over the different scenarios where NaN arises... but such error handling is not really used.

A modern and serious revision of numerical representations used for computations (this is what f32 and f64 are) is worked under the umbrella of unums. Posits (unum III) is a drop-in replacement for IEEE 754.

In this format, there is no such thing as multiple types of NaNs, under the premise that it is a waste of bit patterns that can be used to improve accuracy.

Ah, very good point: if there is some new variation on IEEE754 floats on the horizon that is a drop-in replacement for IEEE754 floats except for the removal of non-canonical NaNs, that seems like an additional argument in favor of not including them in component interface float semantics.

Incidentally, I'm actively working on a rebase of this proposal onto the recently-merged Module Linking rebase (itself rebased onto the Component Model, as proposed earlier in the year), and I'm planning to include the fix to this issue. In particular, the current idea is for intertype to include new float32/float64 types which are distinct from core-wasm f32/f64 in that they only include a single semantic NaN value. Thus intertype and core:valtype will be disjoint sets of types instead of slightly-intersecting.

It seems potentially noteworthy that even though NaN representation distinguishability is itself left implementation-defined by ECMA-262, behavior is specified to be deterministic in the operation that makes it potentially observable:

An implementation must always choose the same encoding for each implementation distinguishable NaN value.

~~It seems like all major engines do permit observation with the same (maybe?) semantics in practice. I'm not 100% sure of that, but e.g. the following behaves the same in both V8 and Spidermonkey:~~

Edit: lol I meant to set b[0], not a[0] there, oops. In V8 the representation propagates, in Spidermonkey it canonicalizes, but in both it does so reliably.

This seems to make a case for at least determinacy, esp. given the role TypedArray plays in bridging JS & WASM. I'm totally out of my depth so this hardly counts as a meaningful opinion - I just figured it might be worth describing the specifics of how JS handles it in the spec & in practice because JS has been mentioned as a factor a few times and determinacy is one of the questions, but the specified-determinacy of Float32Array and Float64Array did not appear to have been previously noted.

Navigation Menu

Repository navigation

NaN canonicalization #134

9 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

NaN canonicalization #134

Description

Activity

lukewagner commented on May 24, 2021

tlively commented on May 25, 2021

sunfishcode commented on May 25, 2021

RossTate commented on May 26, 2021

sunfishcode commented on May 26, 2021

lukewagner commented on May 26, 2021

RossTate commented on May 27, 2021

fgmccabe commented on May 27, 2021

RossTate commented on May 27, 2021

sunfishcode commented on May 27, 2021

RossTate commented on May 27, 2021

RossTate commented on May 27, 2021

fitzgen commented on May 28, 2021

fgmccabe commented on May 28, 2021

RossTate commented on May 28, 2021

9 remaining items

RossTate commented on Jun 4, 2021

aardappel commented on Jun 4, 2021

sunfishcode commented on Jun 4, 2021

RossTate commented on Jun 4, 2021

sunfishcode commented on Jun 5, 2021

RossTate commented on Jun 5, 2021

sunfishcode commented on Jun 9, 2021

RossTate commented on Jun 10, 2021

RossTate commented on Jun 11, 2021

lukewagner commented on Jun 14, 2021

RossTate commented on Jun 14, 2021

lukewagner commented on Jun 14, 2021

saona-raimundo commented on Dec 19, 2021

lukewagner commented on Dec 20, 2021

bathos commented on Dec 20, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions