4 ms·

> Also, any floating-point operation performed on a NaN will give back the same NaN. This is not entirely true. The IEEE-754 recommendation is that floating-p

> Also, any floating-point operation performed on a NaN will give back the same NaN. This is not entirely true. The IEEE-754 recommendation is that floating-point operations do NaN propagation: the result of an operation with one or more NaN inputs should have the same payload as one of those NaN inputs. However, it's only a recommendation, and the only requirement is that the result be a qNaN. There do exist some notable architectures that do not do NaN propagation: RISC-V, for one (it returns the preferred NaN [1]). As a matter of principle, if you're writing this not in assembly, you also have to worry about whether or not the compiler will guarantee NaN payload preservation (so long as the hardware does). Spoiler alert: the answer is no. And we don't talk about sNaN. Just say no to sNaN. [1] Usually, people call this "canonical NaN", but I find this can cause confusion with canonical/noncanonical floating-point numbers. For the basic floating-point types everyone is familiar with, all values are canonical--you have to use the x87 80-bit FP type, the double-double type, or decimal floating point types to find noncanonical representations.

mckeed 4y ago
Wouldn't this strategy still allow performance gains when running on a processor that does NaN propagation?
- zamadatix 4y ago
  I think you'd also want to check the NaN route is actually faster in practice on the CPUs you are targeting but beyond that as long as you're willing to maintain the dedicated codepath for it (or are fine with saying it only runs on specific targets) then you should be good.
- jcranmer 4y ago
  You'd have to be sure that the compiler will also preserve NaN propagation through optimization, which is itself not a safe assumption (internal models for compiler IR often model floating-point as producing a nondeterministic choice of NaN representation, which means that it's not illegal for an optimization to fail to propagate NaNs). As for performance gains, well, the thing is you're not likely to see much of a gain. The post argues that "standard is to store the floats in the high 32 bits of the pointer, with the low 32 bits as a tag", except I've never seen a system like this (tbh, I haven't really done too many VM systems, so my experience isn't great). That tagging model seems like they're assuming a pointer-tagging system [0], rather than true NaN-boxing. With NaN-boxing, you'd want to use the high bits of the payload, so that the low 32-bits can be used directly for whatever value is boxed. See https://searchfox.org/mozilla-central/source/js/public/Value.h#554-557 https://searchfox.org/mozilla-central/source/js/public/Value... for an example of NaN-boxing in Firefox's JS engine [1]. What you save from somebody already using high payload bits from the tag is... an or instruction at the end to set the bits. Realistically, though, there's very little need for a VM to support 32-bit float types. They're not actually faster than 64-bit floats (except for division) in hardware, and the main benefit of smaller float types is more compact memory representation--except if you're boxing all the values anyways, the 32-bit float types also aren't any smaller. [0] Classical pointer tagging uses low bits for the tag, because you rely on pointer alignment. However, with 64-bit systems generally having only 48-bit pointers (57-bit with x86's 5-level page table, but this requires processes to opt in to using 5-level page tables anyways), it makes a lot of sense on 64-bit systems to also use high bits for the tag these days instead. [1] JS doesn't have 32-bit floats, but it does have 32-bit integers, so you can at least get an idea for how the payload would be set if the boxed value could represent 32-bit floats.
  - bjourne 4y ago
    It really depends on how you are boxing. Assuming a four byte object header a boxed float32 consumes 8 bytes. A boxed float64 consumes 12 bytes but! Is quite likely to require 4 bytes of padding to align it to an 8 byte boundary. It adds up quickly if you have many floats.
andreareina 4y ago
I was working on a function to deduplicate (preserving order) collections in python. Very straightforward: take the next value, see if it's in the set of already-seen values, put it in the output list if not. Since it uses sets under the hood, the values have to be hashable. Testing was almost equally straightforward: I favor property testing[1] and just asked for examples from from_type(Sequence[Hashable]). Except. It turns out that Decimal is a hashable type, but there is a specific value that isn't: Decimal('sNaN'). Which of course the tests found pretty much right away (yay prop tests). sNaN: not even once. [1] specifically, using hypothesis
moonchild 4y ago
>> Also, any floating-point operation performed on a NaN will give back the same NaN. > This is not entirely true. As I say two sentences prior: > a couple of qualities near-ubiquitous on modern processors and architectures Obviously, this won't work if you don't do nan-propagation. It also won't work if you don't have vector ops at all, or if they're much slower than the scalar ops. I will add: if you are guaranteed a particular nan, you can just use that as your tag. (Although it looks like riscv uses a nan with an all-zero mantissa, which is unfortunate, as it means using it as the low-bits tag slows down integer math.) > you also have to worry about whether or not the compiler will guarantee NaN payload preservation The target audience is authors of compilers for dynamically-typed programming languages.

mckeed 4y ago

Wouldn't this strategy still allow performance gains when running on a processor that does NaN propagation?

zamadatix 4y ago
I think you'd also want to check the NaN route is actually faster in practice on the CPUs you are targeting but beyond that as long as you're willing to maintain the dedicated codepath for it (or are fine with saying it only runs on specific targets) then you should be good.
jcranmer 4y ago
You'd have to be sure that the compiler will also preserve NaN propagation through optimization, which is itself not a safe assumption (internal models for compiler IR often model floating-point as producing a nondeterministic choice of NaN representation, which means that it's not illegal for an optimization to fail to propagate NaNs). As for performance gains, well, the thing is you're not likely to see much of a gain. The post argues that "standard is to store the floats in the high 32 bits of the pointer, with the low 32 bits as a tag", except I've never seen a system like this (tbh, I haven't really done too many VM systems, so my experience isn't great). That tagging model seems like they're assuming a pointer-tagging system [0], rather than true NaN-boxing. With NaN-boxing, you'd want to use the high bits of the payload, so that the low 32-bits can be used directly for whatever value is boxed. See https://searchfox.org/mozilla-central/source/js/public/Value.h#554-557 https://searchfox.org/mozilla-central/source/js/public/Value... for an example of NaN-boxing in Firefox's JS engine [1]. What you save from somebody already using high payload bits from the tag is... an or instruction at the end to set the bits. Realistically, though, there's very little need for a VM to support 32-bit float types. They're not actually faster than 64-bit floats (except for division) in hardware, and the main benefit of smaller float types is more compact memory representation--except if you're boxing all the values anyways, the 32-bit float types also aren't any smaller. [0] Classical pointer tagging uses low bits for the tag, because you rely on pointer alignment. However, with 64-bit systems generally having only 48-bit pointers (57-bit with x86's 5-level page table, but this requires processes to opt in to using 5-level page tables anyways), it makes a lot of sense on 64-bit systems to also use high bits for the tag these days instead. [1] JS doesn't have 32-bit floats, but it does have 32-bit integers, so you can at least get an idea for how the payload would be set if the boxed value could represent 32-bit floats.
- bjourne 4y ago
  It really depends on how you are boxing. Assuming a four byte object header a boxed float32 consumes 8 bytes. A boxed float64 consumes 12 bytes but! Is quite likely to require 4 bytes of padding to align it to an 8 byte boundary. It adds up quickly if you have many floats.

andreareina 4y ago

I was working on a function to deduplicate (preserving order) collections in python. Very straightforward: take the next value, see if it's in the set of already-seen values, put it in the output list if not. Since it uses sets under the hood, the values have to be hashable. Testing was almost equally straightforward: I favor property testing[1] and just asked for examples from from_type(Sequence[Hashable]). Except. It turns out that Decimal is a hashable type, but there is a specific value that isn't: Decimal('sNaN'). Which of course the tests found pretty much right away (yay prop tests). sNaN: not even once. [1] specifically, using hypothesis

moonchild 4y ago

>> Also, any floating-point operation performed on a NaN will give back the same NaN. > This is not entirely true. As I say two sentences prior: > a couple of qualities near-ubiquitous on modern processors and architectures Obviously, this won't work if you don't do nan-propagation. It also won't work if you don't have vector ops at all, or if they're much slower than the scalar ops. I will add: if you are guaranteed a particular nan, you can just use that as your tag. (Although it looks like riscv uses a nan with an all-zero mantissa, which is unfortunate, as it means using it as the low-bits tag slows down integer math.) > you also have to worry about whether or not the compiler will guarantee NaN payload preservation The target audience is authors of compilers for dynamically-typed programming languages.