What is the purpose of NaN boxing?

Question

Reading 21st Century C I arrived at chapter 6 at the section "Marking Exceptional Numeric Values with NaNs", where it explains the use of the bits in the mantissa to store some arbitrary bit patterns, to use them as markers or pointers (the book mentions that WebKit uses this technique).

I'm not really sure I understood the utility of this technique, that I see as an hack (it relies on the hardware not caring on the value of the mantissa in a NaN) but coming from a Java background I'm not used to the roughness of C.

Here is the snippet of code that sets and reads a marker in a NaN

#include <stdio.h>
#include <math.h> //isnan

double ref;

double set_na(){
    if (!ref) {
        ref=0/0.;
        char *cr = (char *)(&ref);
        cr[2]='a';
    }
    return ref;
}

int is_na(double in){
    if (!ref) return 0;  //set_na was never called==>no NAs yet.

    char *cc = (char *)(&in);
    char *cr = (char *)(&ref);
    for (int i=0; i< sizeof(double); i++)
        if (cc[i] != cr[i]) return 0;
    return 1;
}

int main(){
    double x = set_na();
    double y = x;
    printf("Is x=set_na() NA? %i\n", is_na(x));
    printf("Is x=set_na() NAN? %i\n", isnan(x));
    printf("Is y=x NA? %i\n", is_na(y));
    printf("Is 0/0 NA? %i\n", is_na(0/0.));
    printf("Is 8 NA? %i\n", is_na(8));
}

it prints:

Is x=set_na() NA? 1
Is x=set_na() NAN? 1
Is y=x NA? 1
Is 0/0 NA? 0
Is 8 NA? 0

and at JSValue.h webkit explains the encoding, but not why it's used.

What is the purpose of this technique? Are the benefits of space/performance high enough to balance its hackish nature?

Answer 1

When you are implementing a dynamically typed language, you've got to have a single type which can hold any of your objects. There are three different approaches I'm aware of for this:

Firstly, you can pass around pointers. This is what the CPython implementation does. Every object is a PyObject pointer. These pointers get passed around and operations are performed by looking at details in the PyObject struct to figure out the type.

The disadvantage is that small values like numbers get stored as boxed values, So your little 5 gets stored as a block of memory somewhere. So this leads us to the union approach, which is used by Lua. Instead of a PyObject*, each value is a struct which one field to specify the type, and then a union of all the different supported types. That way we avoid allocating any memory for small values, instead storing them directly in the union.

The NaN approach stores everything as doubles, and reuses the unused portion of NaN for the extra storage. The advantage over the union method is that we save the type field. If it's a valid double, it's a double otherwise the mantissa is a pointer to the actual object.

Remember, this is every javascript object. Every variable, every value in an object, every expression. If we can reduce all of those from 96 bits to 64 bits that is pretty impressive.

Is it worth the hack? Recall that there is a lot of demand for efficient Javascript. Javascript is the bottleneck in many web applications, and so making it faster is a higher priority. It's reasonable to introduce a certain degree of hackiness for performance reasons. For most cases, it'd be a bad idea, because its introducing a degree of complexity for little gain. But in this specific case, it is worthwhile for memory and speed improvements.

Answer 2

Using NaN for "exceptional values" is a well known and sometimes helpful technique to avoid the need of an extra boolean variable this_value_is_invalid. Used wisely, it can help one to make his code more concise, cleaner, simpler, better readable without any performance trade-offs.

This technique has some pitfalls, of course (see here http://ppkwok.blogspot.co.uk/2012/11/java-cafe-1-never-write-nan-nan_24.html), but in languages like Java (or very similar C#) there are standard library functions like Float.isNaN to make dealing with NaNs simple. Of course, in Java you could use alternatively theFloat and Double class and in C# the nullable value types float? and double?, giving you the possibility of using null instead of NaN for invalid floating point numbers, but those techniques can have a significant negative influence on the performance and memory usage of your program.

In C the use of NaN is not 100% portable, that is true, but you can use it everywhere where the IEEE 754 floating point standard is available. AFAIK this is quite almost every mainstream hardware today (or at least the runtime environment of most compilers support it). For example, this SO post contains some information to find out more details about the use of NaN in C.