3 ms·

The purpose of NaN Boxing

24 points by akg 14y ago

gus_massa 14y ago
In Racket, they use the alignment of the memory blocks: * The even integer numbers are pointers. * The odd integers represent fixnums (small integers) (n <---> 2*n+1). With this representation the calculations with fixnums are quite fast because they don't need unboxing.
- apaprocki 14y ago
  It probably isn't relevant to most people anymore, but misaligned memory access on certain architectures (e.g. Sparc) incurs a penalty.
  - rayiner 14y ago
    The tagging scheme mentioned above accounts for that. Objects are stored at aligned addresses, which leaves a couple or three bits available for signifying integers and other data types. On architectures that trap on unaligned accesses, you can actually use the trap to avoid an explicit type check if you're expecting a pointer and someone passes an integer.
  - dfox 14y ago
    Almost any implementation masks off the bit(s) before using the value as pointer (when they are not defined as zero for pointers as in this case :)) and stores the objects aligned in memory. As for performance penalty, unaligned memory accesses are (at least potentially) slower than aligned on almost any architecture. On some architectures they are simple not implemented in hardware and cause an exception (which includes SPARC and essentially anything purporting to be any kind of RISC) As for SPARC: SPARC actually even has hardware support for similar tagging mechanism: TADDcc and related instructions. Idea is that integers are taged by having two LSB's set to 00. These additional instructions do arithmetic as normal, but also set overflow flag (and optionally cause exception) when any of the operands have tag different from 00. Thus code can do the common case of fixnum arithmetic in one instruction (and possibly OF check) and only when overflow is detected fallback to slower codepath that handles fixnum->bignum overflows and non-fixnum datatypes.
  - awda 14y ago
    Still totally relevant -- x86 misaligned memory accesses hurt.
- cygx 14y ago
  See also the blue book (Smalltalk-80: The Language and its Implementation), keyword 'Small Integers'.
- loeg 14y ago
  Ruby follows this same model. See the macro FIXNUM_P()[0] and FIXNUM_FLAG[1]. Edit: Every ruby value is either an fixnum (invalid pointer marked with FIXNUM_FLAG), a pointer to a real ruby value, or possibly an invalid, sentinel pointer. The comment block starting at [2] is informative. [0]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L355 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b... [1]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L425 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b... Edit: It is assumed that pointers will be at least 16-bit aligned and thus, an odd-value pointer is never valid. So they can safely re-use half of the value space for integer values. So, you get fast integer arithmetic, but you don't get the fast floating point math like you do with NaN-boxing. [2]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L383 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b...
  - loeg 14y ago
    Edit-period has expired, so I'm replying to myself. The sentinel pointers work like this: the zero page is assumed to never point to a valid Ruby object (NULL through NULL+PAGE_SIZE-1), so they just use some otherwise "pointer" shaped numbers in that range as special values (nil, true, false).
malkia 14y ago
luajit was the first implementation I've seen, but it's author Mike Pall said soemewhere that this was an old technique, or more like that it could've been known before. I remember reading aome lisp paper from th 90s where sifferent encoding techniques/boxings were mentioned, and one of them was it (I thnink).
- krickle 14y ago
  I first read about it on wingolog.org, and IIRC there was mention of an implementation of Guile using it. I think that supports your paper as evidence. Very cool technique, but I would rather give preference to integers and pointers.
lmkg 14y ago
NaN-boxing is morally equivalent to using tagged unions to represent values of any type. It optimizes for fast floating-point operations, and for allowing a larger amount of meaningful values to be represented in 64 bits. Most tagged-union approaches use some sort of punning so that at least one type of value is directly meaningful, without any bit manipulation. For example, some Common Lisp implementations will choose their tag bits for Cons cells such that NIL is represented with all zeros. Since NIL is the only falsey value and everything else is truthy, this means that any bit-pattern can be used directly for testing conditionals, with the correct semantics. NaN-boxing is choosing a different type of punning for the tags, to optimize a different use case. First, all bit-patterns can be used directly as 64-bit floats with technically correct semantics--anything that's NaN-boxed is actually not a floating-point number. I'm given to understand that modern architectures are slow to mix float and bit ops, so it's nice that you don't need to mask your tags off of your float before operating on them. Second, (double-precision) floats are usually the only type that require the full 64 bits to have meaning. In many applications, 50ish bits is 'good enough' for ints and pointers (with some extra ops to handle overflow), but floats are mandated by a standard and don't scale down gracefully. A tagged union wouldn't be able to contain a 64-bit float directly without spilling into an extra machine word. Unless, of course, the tags are punned to be part of the float value itself. And that's exactly what NaN-boxing is.
bitwize 14y ago
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. The use of "signalling NaNs" is supported by IEEE 754. It may be a hack, but it's a hack that's in the standard.
general_failure 14y ago
v8 doesn't use this technique - the use SMI. Read also http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation...

24 points by akg 14y ago

In Racket, they use the alignment of the memory blocks: * The even integer numbers are pointers. * The odd integers represent fixnums (small integers) (n <---> 2*n+1). With this representation the calculations with fixnums are quite fast because they don't need unboxing.

apaprocki 14y ago
It probably isn't relevant to most people anymore, but misaligned memory access on certain architectures (e.g. Sparc) incurs a penalty.
- rayiner 14y ago
  The tagging scheme mentioned above accounts for that. Objects are stored at aligned addresses, which leaves a couple or three bits available for signifying integers and other data types. On architectures that trap on unaligned accesses, you can actually use the trap to avoid an explicit type check if you're expecting a pointer and someone passes an integer.
- dfox 14y ago
  Almost any implementation masks off the bit(s) before using the value as pointer (when they are not defined as zero for pointers as in this case :)) and stores the objects aligned in memory. As for performance penalty, unaligned memory accesses are (at least potentially) slower than aligned on almost any architecture. On some architectures they are simple not implemented in hardware and cause an exception (which includes SPARC and essentially anything purporting to be any kind of RISC) As for SPARC: SPARC actually even has hardware support for similar tagging mechanism: TADDcc and related instructions. Idea is that integers are taged by having two LSB's set to 00. These additional instructions do arithmetic as normal, but also set overflow flag (and optionally cause exception) when any of the operands have tag different from 00. Thus code can do the common case of fixnum arithmetic in one instruction (and possibly OF check) and only when overflow is detected fallback to slower codepath that handles fixnum->bignum overflows and non-fixnum datatypes.
- awda 14y ago
  Still totally relevant -- x86 misaligned memory accesses hurt.
cygx 14y ago
See also the blue book (Smalltalk-80: The Language and its Implementation), keyword 'Small Integers'.
loeg 14y ago
Ruby follows this same model. See the macro FIXNUM_P()[0] and FIXNUM_FLAG[1]. Edit: Every ruby value is either an fixnum (invalid pointer marked with FIXNUM_FLAG), a pointer to a real ruby value, or possibly an invalid, sentinel pointer. The comment block starting at [2] is informative. [0]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L355 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b... [1]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L425 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b... Edit: It is assumed that pointers will be at least 16-bit aligned and thus, an odd-value pointer is never valid. So they can safely re-use half of the value space for integer values. So, you get fast integer arithmetic, but you don't get the fast floating point math like you do with NaN-boxing. [2]: https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25bbb692aad90b864/include/ruby/ruby.h#L383 https://github.com/ruby/ruby/blob/cbd1f2571af6bf93d5c4d4c25b...
- loeg 14y ago
  Edit-period has expired, so I'm replying to myself. The sentinel pointers work like this: the zero page is assumed to never point to a valid Ruby object (NULL through NULL+PAGE_SIZE-1), so they just use some otherwise "pointer" shaped numbers in that range as special values (nil, true, false).

malkia 14y ago

luajit was the first implementation I've seen, but it's author Mike Pall said soemewhere that this was an old technique, or more like that it could've been known before. I remember reading aome lisp paper from th 90s where sifferent encoding techniques/boxings were mentioned, and one of them was it (I thnink).

krickle 14y ago
I first read about it on wingolog.org, and IIRC there was mention of an implementation of Guile using it. I think that supports your paper as evidence. Very cool technique, but I would rather give preference to integers and pointers.

lmkg 14y ago

NaN-boxing is morally equivalent to using tagged unions to represent values of any type. It optimizes for fast floating-point operations, and for allowing a larger amount of meaningful values to be represented in 64 bits. Most tagged-union approaches use some sort of punning so that at least one type of value is directly meaningful, without any bit manipulation. For example, some Common Lisp implementations will choose their tag bits for Cons cells such that NIL is represented with all zeros. Since NIL is the only falsey value and everything else is truthy, this means that any bit-pattern can be used directly for testing conditionals, with the correct semantics. NaN-boxing is choosing a different type of punning for the tags, to optimize a different use case. First, all bit-patterns can be used directly as 64-bit floats with technically correct semantics--anything that's NaN-boxed is actually not a floating-point number. I'm given to understand that modern architectures are slow to mix float and bit ops, so it's nice that you don't need to mask your tags off of your float before operating on them. Second, (double-precision) floats are usually the only type that require the full 64 bits to have meaning. In many applications, 50ish bits is 'good enough' for ints and pointers (with some extra ops to handle overflow), but floats are mandated by a standard and don't scale down gracefully. A tagged union wouldn't be able to contain a 64-bit float directly without spilling into an extra machine word. Unless, of course, the tags are punned to be part of the float value itself. And that's exactly what NaN-boxing is.

bitwize 14y ago

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. The use of "signalling NaNs" is supported by IEEE 754. It may be a hack, but it's a hack that's in the standard.

general_failure 14y ago

v8 doesn't use this technique - the use SMI. Read also http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation...