NaN-Boxing

How do dynamicly typed languages allow any variable to hold any type? There are a few different techniques, but the one I use for sink is NaN-boxing.

I first heard about this technique from an old article when reading about technical details of Google’s V8 JavaScript engine. The V8 engine does not use NaN-boxing, but Firefox did at the time.

Tagged Union

First, let’s demonstrate the most obvious solution for holding multiple values in the same type – a tagged union:

typedef enum {
  TYPE_BOOL,
  TYPE_NUMBER,
  TYPE_STRING,
  TYPE_LIST,
  TYPE_OBJECT
} val_type;

typedef struct {
  val_type tag;
  union {
    bool   b;
    double num;
    string str;
    list   lst;
    object obj;
  } u;
} val;

Remeber that a union in C actually overlaps all the memory – so the bool b, double num, string str, etc, all use the same memory.

We use the tag enumerator to tell us which union member to actually use. This is why it’s called a tagged union.

Doubles

NaN-boxing instead crams the tag into a NaN double value.

To understand this technique, we’ll have to look up what a floating point value actually is, as defined by IEEE 754:

The IEEE 754 standard specifies a binary64 as having:

  • Sign bit: 1 bit
  • Exponent: 11 bits
  • Significand precision: 53 bits (52 explicitly stored)

That means it looks like this:

Double Bit Format

What is a NaN?

So what is a NaN?

NaN stands for Not-a-Number. It is a special value a floating point number can hold (so, paradoxically, a NaN value is actually a number).

It is used when a calculation cannot produce a meaningful value, like dividing 0 by 0, or taking the arc-cosine of 200.

More importantly, there are two types of NaN values:

  • Quiet NaN – this is what bad calculations can produce, and will propagate through math operations without raising any errors.
  • Signaling NaN – this is a special NaN that, when used in a calculation, causes a floating point exception to occur.

Depending on your architecture and compiler, a signaling NaN can behave different ways. Here is a short program that demonstrates the difference between quiet NaNs and signaling NaNs on Mac OSX:

#include <stdio.h>
#include <stdint.h>
#include <xmmintrin.h>

int main(int argc, char **argv){
  // goofy way to enable SIGFPE on Mac OSX:
  _MM_SET_EXCEPTION_MASK(
    _MM_GET_EXCEPTION_MASK() & ~_MM_MASK_INVALID);

  union {
    double f;
    uint64_t u;
  } value;

  // perform math with a quiet NaN:
  value.u = 0xFFF8000000000000ULL;
  printf("qNaN math: %g\n", value.f + 4.0);

  // perform math with a signaling NaN:
  value.u = 0xFFF4000000000000ULL;
  printf("sNaN math: %g\n", value.f + 4.0);

  return 0;
}

This has the following results:

$ clang nan.c
$ ./a.out
qNaN math: nan
fish: Job 1, './a.out' terminated by signal SIGFPE (Floating
point exception)

Notice that the quiet NaN will not throw an exception, and will simply pass the NaN through to the output. The signaling NaN will cause the program to terminate immediately.

Creating NaNs

So how do we even create a NaN in the first place?

IEEE 754 NaNs are represented with the exponent field filled with ones (like infinity values), and some non-zero number in the significand.

Easy enough.

NaN Bit Format

How do we distinguish between quiet and signaling NaNs?

The 2008 revision of the IEEE 754 standard (IEEE 754-2008) makes formal recommendations for the encoding of the signaling/quiet state.

For binary formats, the most significant bit of the significand field should be an ‘is_quiet’ flag. I.e. this bit is non-zero if the NaN is quiet, and zero if the NaN is signaling.

Perfect! So we use the left-most significand bit.

Now the sample program above should make sense:

value.u = 0xFFF8000000000000ULL; // quiet NaN
value.u = 0xFFF4000000000000ULL; // signaling NaN

Payload

And now we notice a wonderful feature of the NaN:

Most of the bits aren’t used!

We can use these however we want, as long as we satisfy the NaN requirements. These unused bits are called the payload.

There’s one final catch:

We should probably avoid using the payload of a quiet NaN, because normal math operations can return quiet NaNs – for example, dividing 0 by 0.

We can’t predict the exact bits returned from math operations, but we do know that no math operation returns a signaling NaN.

Therefore, if we forbid signaling NaNs to be created in our programming language, then we are free to use them to pack in a payload that tells us what the dynamic value actually is – just like a tagged union.

Packing Into Signaling NaNs

There are a lot of options at this point – given roughly 52 bits of payload, how should we store our actual data types?

There are different tricks for cramming pointers directly into the signaling NaN payload, but I prefer a more predictable approach:

Use the higher bits to tag the type, and the lower 32 bits as an index into a huge array.

Something like this:

typedef union {
  double f;
  uint64_t u;
} value;

//                           index -----------VVVVVVVV
//                             tag -------VVVV
//                            sNaN ---VVVV
const value VALUE_NIL      = { .u = 0xFFF0000100000000ULL };
const value VALUE_TRUE     = { .u = 0xFFF0000200000000ULL };
const value VALUE_FALSE    = { .u = 0xFFF0000300000000ULL };
const uint64_t TAG_STRING  =        0xFFF0000400000000ULL;
const uint64_t TAG_LIST    =        0xFFF0000500000000ULL;
const uint64_t TAG_OBJECT  =        0xFFF0000600000000ULL;
const uint64_t TAG_MASK    =        0xFFFFFFFF00000000ULL;
const uint64_t INDEX_MASK  =        0x00000000FFFFFFFFULL;

static inline bool value_is_string(value v){
  return (v.u & TAG_MASK) == TAG_STRING;
}

static inline uint32_t value_to_index(value v){
  return (uint32_t)(v.u & INDEX_MASK);
}

static inline value new_list(uint32_t index){
  return (value){ .u = TAG_LIST | (uint64_t)index };
}

Notice a few things here:

  1. Our tags start counting at 1, and leave the left-most significand bit 0, so that we’re guaranteed our values are always signaling NaNs.
  2. We use the bitwise and & operator to mask away the index when checking for the tag.
  3. We use the lower 32-bits of the value as an index.
  4. We use the bitwise or | operator to pack the tag and index into a signaling NaN.

This can look really intimidating at first, but just review how the bitwise operators work, and the bit format of signaling NaNs, and you’ll see it’s exactly as described above:

We are using the payload bits of a signaling NaN to store a tag and an index.

Summary

Now when you look at the actual sink source code, the strange hexadecimal values and masks should start to make sense: they’re simply used to manipulate the tag and index in a 64-bit signaling NaN.

It can seem a bit crazy at first, but once you know the idea, it’s a pretty clever and useful trick.

Have fun!

permanent link
back to top

posted 26 Nov 2016 by Sean
tags: sink, c

View All Articles