3
$\begingroup$

I recently heard about NaN-Boxing as an alternative to tagging for pointers. What would implementing NaN-Boxing really mean for a language?

Primarily, I'm wondering whether it would limit the capabilities of the language in a practical sense or what kind of languages would not want to use it?

$\endgroup$
3
  • $\begingroup$ It's purely an optimisation, so it has no implications for the language, it only has performance implications for an implementation of the language. $\endgroup$
    – kaya3
    Jan 5 at 15:21
  • $\begingroup$ @kaya3: Your comment is actually an answer... $\endgroup$ Jan 5 at 15:27
  • 4
    $\begingroup$ @MatthieuM. But I am not sure the question is focused enough ─ "what are the implications of ..." in general is too broad. It's not clear to me that the question is only about semantic implications for the language, and if I posted the above as an answer it might be unsatisfactory, since it doesn't discuss what the performance implications are. $\endgroup$
    – kaya3
    Jan 5 at 15:31

2 Answers 2

4
$\begingroup$

What would implementing NaN-Boxing really mean for a language?

NaN-boxing is an implementation technique, a programming language is an abstract construct and does not concern itself with implementations, therefore an implementation technique has no effect whatsoever on a programming language.

I'm wondering whether it would limit the capabilities of the language in a practical sense.

NaN-boxing is about polymorphism, allowing a value to be either a double or a pointer.

It is largely irrelevant to statically typed languages like C, C++, or Rust where the type of a value is known in advance, and most relevant to dynamically typed languages where the type of a value is not generally known in advance and a uniform representation is therefore valuable.

In terms of limitations, it depends how you use it.

JavaScript for example is particular amenable to it because the language only has a concept of "number", no separate floating-point vs integer. This allows it to represent all numbers as 64-bits floating point values, at the cost of limiting integer magnitude to 53 bits (the size of the mantissa): above 53 bits, not all integer values can be represented exactly.

If JavaScript had been specified as having 64-bits width integers, then NaN-boxing could have been used, but only by "promoting" large integer values to full object, rather than keeping in double.

what kind of languages would not want to use it?

There is no "one" NaN-boxing technique, so any language implementation could find some value in NaN-boxing and avoid using it when not suitable for the purpose.

$\endgroup$
2
  • $\begingroup$ I see, so it is useful to dynamic languages because every pointer would otherwise need to have a type tagged alongside it, whereas for static languages, that type is already known. It's not about reducing the memory footprint of a pointer, which is 64-bits in either implementation, but about abstracting from the type information for a language that would have to specify it. $\endgroup$ Jan 5 at 16:28
  • $\begingroup$ It's about avoiding allocation while keeping a uniform value representation requiring less-to-no further context to know what the bits are. You could allocate every integer, floating point, even bool on the heap and only deal with pointers, no NaN-boxing required. But all those allocations have a cost. NaN-boxing allows keeping numbers as floating points while embedding pointers for non-numbers inside the NaN payload, saving up on allocation costs, cache misses, etc... $\endgroup$ Jan 5 at 17:21
-2
$\begingroup$

What are the implications: You cannot use floating-point numbers with NaN values, because they would be mistaken for pointers.

Your logical address space is limited to 53 bits (the 52 mantissa bits and the sign bit of an NaN) or 52 bits (if you don’t use the sign bit of an Nan which might be a tiny bit faster), but that is over 8000 TB and should be no practical problem for a few years.

And since the mantissa of an NaN cannot be all bits zero, you need to decide how you represent null.

BTW In the ieee 754 standard, all numbers with max exponenent and nonzero mantissa are nans.

$\endgroup$
6
  • 2
    $\begingroup$ You can reserve a nan value (or multiple of them!) to act as the floating point value nan. $\endgroup$
    – Moonchild
    Jan 9 at 10:26
  • 1
    $\begingroup$ Based on this introduction to NaN-boxing, none of these are correct. 64-bit processors generally only implement a 48-bit address space, so you have plenty of space to store that, including 48 zero bits with an appropriate prefix for the null pointer. By using that prefix as a type marker, you can not only reserve values for real NaNs, but also for non-pointer types like booleans; and even box short strings, and 32-bit integers into that same 48-bit space. $\endgroup$
    – IMSoP
    Jan 9 at 17:12
  • $\begingroup$ Recent intel processors have a 57-bit address space, and arm extended to iirc 52 bits. $\endgroup$
    – Moonchild
    Jan 10 at 20:56
  • $\begingroup$ @Moonchild Fair enough. Then a limitation could be "you're limited to 48-bit pointers, even on architectures which allow longer, because you need a few bits spare for type markers, and to reserve at least one value for NaN itself". $\endgroup$
    – IMSoP
    Jan 11 at 19:09
  • 1
    $\begingroup$ Regards the last sentence added in an edit: yes, that's why the whole thing is possible. Because you don't actually need nine quadrillion different ways to express NaN, it's possible to re-purpose those bit sequences, knowing they're very unlikely to accidentally show up as actual floating point values. It's called "NaN-boxing" not just "float-boxing", because it's only NaN values that you're repurposing. $\endgroup$
    – IMSoP
    Jan 11 at 19:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .