8 ms·
NaN Boxing (2020)
- sosodev 4y agoI know we're supposed to stay on topic, but I seriously thought this was going to be an article about elderly women punching each other.
- proto_lambda 4y agoHN title mangling strikes again. "NaN Boxing", which is very likely what the OP submitted it as, would've been obvious.
- blowski 4y agoFor a while, this was a popular Christmas novelty gift. https://www.gigglegadgets.co.uk/home/307-boxing-grannies.html https://www.gigglegadgets.co.uk/home/307-boxing-grannies.htm...
- throwawaymaths 4y agoI wonder if you could do better; instead of stuffing that bit at the bottom as an int marker, do your best to represent the int faithfully (with higher order nan bits doing their thing) so you optimistically perform the add and issue the add at the same time as you issue the conditional, then by the time the conditional resolves both your float addition and integer addition have come back and you pick the winner with no branching
- ridiculous_fish 4y agoIt's an interesting idea. In practice one must also consider int + double and double + int, so there's four possible paths.
- an1sotropy 4y agoSome other things on the same topic: https://leonardschuetz.ch/blog/nan-boxing/ https://leonardschuetz.ch/blog/nan-boxing/ https://anniecherkaev.com/the-secret-life-of-nan https://anniecherkaev.com/the-secret-life-of-nan Is NaN-boxing actually used in the major browser JS engines?
- moonchild 4y agoAfaik, it is not used by chrome, but it is used by firefox. Luajit also uses it.
- ridiculous_fish 4y agov8 does not use NaN-boxes; instead they use the low bit to distinguish between a 31-bit small integer ("smi") or a pointer. Doubles are additionally sometimes stored inline ("double field unboxing") I'm not sure how this works exactly. Other times they are heap-allocated. I am not sure if there is a specialized double-allocator, I'd like to know. JavaScriptCore uses a tweaked NaN-box [1]: values are stored via a NaN box minus a constant, which avoids requiring a mask when chasing pointers. This makes pointers cheaper but floating point operations more expensive. SpiderMonkey and Hermes both use straight NaN-boxing to my knowledge. https://github.com/WebKit/WebKit/blob/ec6b5337e777f9b460ec6b8b9a82a648fe461764/Source/JavaScriptCore/runtime/JSCJSValue.h#L403 https://github.com/WebKit/WebKit/blob/ec6b5337e777f9b460ec6b...
- moonchild 4y ago> avoids requiring a mask when chasing pointers This, unfortunately, is an artificial limitation; negative nans may correspond to canonical addresses, but most oses won't let you map negative memory, keeping it all to themselves.
- repiret 4y agoIt’s not even always architecturally possible - ARMv8 doesn’t support user-space mappings with bit 63 set, for example.
- kmeisthax 4y agoNaN boxing sounds like it would have very significant pointer provenance issues. CHERI would also stick its nose up at it. The tagged pointer type has the advantage of holding real pointers, meaning that any machine[0] that sticks extra information onto its pointers transparently just works. And reading the int half of the union to check if the pointer is valid should always be sound, but I'm not 100% sure on that. Architectures that don't enforce alignment are also probably not the sort of thing we care about running on, and I doubt there's a way for an optimizer to legally screw over programs that depend on pointer alignment being there on architectures where it has to be there. But, then again, that's what we said about int-to-pointer casts... [0] Real or virtual. Remember that when you compile your program with an optimizing compiler or JIT, it is executing on two architectures: 1. The compiler's expression/AST interpreter, which enforces ISO C undefined behavior rules 2. The target architecture, where those undefined behaviors become merely unspecified.
- klodolph 4y agoI don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back, which is what's happening here, and you get pointer provenance problems because different pointers may be supposed to point to different objects. Basically, casting to an integer and back is supposed to be "safe", but doing math and getting pointers to different objects is not. Note that there are some implementation-dependent factors here which I'm not getting into. > And reading the int half of the union to check if the pointer is valid should always be sound, but I'm not 100% sure on that. After various alias problems a while back (Linux kernel folks had some words), everyone got together and agreed that you can do type punning through a union... you just get the byte representation of one type, reinterpreted as the byte representation of another type. This was codified a few C standards ago and it's fairly explicit in the spec now. I'll also just mention that you don't need an architecture than enforces alignment--you just need an allocator that returns aligned pointers.
- MaulingMonkey 4y ago> I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back It's worth noting that Rust is experimenting with making this not so free for one to do: https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-pointer-roundtrips-and-exposed-provenance https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-p...
- beagle3 4y agoYou can also double the boxed space by using subnormals (nee denormals) if you don't need them for precision (and if you do need them .... my condolences).
- an1sotropy 4y agoCan you explain this more? I mean why is the space doubled, exactly?
- sjrd 4y agoBecause there are as many subnormal values as NaN values. At least if you don't count the two 0's, which are "paired" with the two infinities.
- an1sotropy 4y agooh right - sorry stupid question.
- deleted 4y ago[deleted]
- maglite77 4y agoIt's been ages, but this use of unions reminds me of the VARIANT structure definition from Windows OA/COM: [1]: https://docs.microsoft.com/en-us/windows/win32/api/oaidl/ns-oaidl-variant?source=recommendations https://docs.microsoft.com/en-us/windows/win32/api/oaidl/ns-...
- Waterluvian 4y agoI’m curious for feedback about the very beginning of this post. How many people see the “let a” example as “the variable ‘a’ keeps changing shape/type” and how many see it as, “three different things were created and the variable ‘a’ kept getting reassigned to point at the newest one.” Or is this not really a distinction people see?
- skybrian 4y agoIt seems like the beginning of the post avoids the issue. "First a was this, now it's this" doesn't take a position on whether it's really the same object, just how it appears in the debugger.
- glenjamin 4y agoMy mental model of JavaScript is that the name/label “a” in that scope was re-used 3 times, but for a different value each time
- deleted 4y ago[deleted]
- Taniwha 4y agoNaN-boxing has other uses - RISC-V systems that support FP have 32 FP registers that are used for 32-bit floats, 64-bit doubles (and possibly 128-bit doubles). According to the spec in a system with 64-bit FP registers 32-bit floats are stored (in the registers) with the upper 32-bits as 0xffff_ffff - a NaN for 64-bit FP values (the same for systems with 128-bit floats) - this catches (some) code that mixes 32/64 bit floats without conversion
- userbinator 4y agoNote that the benchmark code is inconsistent - nanb3 and nanb4 allocate 10x the number of objects of nanb and nanb2, so I was getting very surprising results until I realised that and fixed it. On a 32-bit system, it seems tagged pointers have the advantage: nanb 18.562s - NaN boxing nanb2 17.484s - tagged pointer nanb3 25.468s - tagged structure nanb3 with pack(1) 26.000s nanb4 20.093s - tagged union nanb4 with pack(1) 19.109s I also tried with pack(1) to see if cache effects would show up, and although it made the tagged structure slightly slower, indeed you can see that the tagged union became faster without alignment padding.
- kazinator 4y agoI just implemented NaN boxing for TXR Lisp several days ago. https://www.kylheku.com/cgit/txr/commit/?id=073e4a84090b11fdc12a7fbc8f50df5e7b1ae25a https://www.kylheku.com/cgit/txr/commit/?id=073e4a84090b11fd... I'm rolling out a release; it's going to be enabled by default on 64 bits by the build configure script. I tested on PPC, RISC-V, AArch64, X86-64 so far. I will do Loongarch64 and Mips64 also. I developed my own "flavor" of NaN boxing, which gets us the maximum width of fixnum integers, and harmonizes with the pointer tagging scheme (which is still there, configurable at build time). Some of the decisions made were to keep the code base common between the pointer tagging and NaN boxing. This arises in the arithmetic library code. The representation is "pointer favoring"; so floating-point values are not represented as themselves; an offset has to be added to their integer image. I chose the offset 0x0004 0000 0000 0000. What this means is that in the upper 16 bits, the values 0x0000, 0x0001, 0x0002 and 0x0003 can be used as tags for whatever purpose. We make the 0x0000 one denote pointers. Floating-point values start at 0x0004. This fits perfectly into TXR Lisp which has two tag bits in the pointer tagging scheme: tags 0, 1, 2 and 3. We keep exactly the same tags. When the upper 14 bits are all 1 (0xFFFC), which is the non-signaling NaN, the remaining 50 bits are a fixnum integer: the most we can have. So we have 48 bit pointers, 50 bit integers, plus three addititional kinds of values that have 48 bits of room. Under the pointer tagging scheme, the three values are characters, integers and C string literals. Since we otherwise represent integers under NaN, one of the tags, TAG_NUM (value 1) is not actually used. The function which returns a value's tag fakes out this TAG_NUM value when it detects a NaN-coded integer, which has no such tag. This value must be returned because tons of code depends on it. There has to be compatibility between pointer tagging and NaN boxing not to have to rewrite a bunch of code in two ways.
- xfer 4y agoIs that a good trade-off sacrificing fixnum bits? I guess it would make sense when the language is intended for scientific programming.
- kazinator 4y agoHard to say. It hurts in the compiler which uses integer bitmasks for register sets. Fewer registers are handled without boxing. But I see hardly any difference in the library compile time. fixnum-max is 562949953421311, which is still astronomically large. It can represent 5.6 trillion dollars, in integer cents. We could do the accounting of some large multi-nationals in fixnums. We will never need an array index that cannot fit into this. (Proof: pointers are 48 bits under this scheme, so using positive integers, we can enumerate every nybble.) We can seek 562 terabytes into a file, which doesn't seem too shabby. There are situations in which having anything less than the full 64 bits in the integer hurts, like externally imposed bitfields and masks.
- pwdisswordfish9 4y ago> Because of that, 64-bit architectures use only 48 lowest bits of every pointer which still give plenty of addresses. It means that only 48 bits in a pointer are significant and that is enough for our NaN boxing. Congratulations, you have just ruined your software's forward c11y. Those 16 bits aren't going to stay reserved forever.
- chrisseaton 4y agoI don’t understand what you mean. In your process, you can control the address range of your memory, so the address range of your pointers. It’s irrelevant if the 16 bits are reserved by the architecture or not - just don’t map space that uses them. What’s the issue?
- userbinator 4y agoWhen? Too long to care. How long will it be until 256TB of RAM (which is what 48 bits will address) becomes even remotely common in a single system? Even 256GB, 1024x less, is not common today, except in huge servers. How long will it take to change the implementation when/if it does? I've seen far too much "future proofing" that makes the present worse, for a future that might never even happen.
- sparkie 4y agoQuad-precision floats will be widespread before applications that use >256TiB of memory are common. In that case, we can NaN-box the quad float and have up to 112 bits of pointer space to play with. Lets assume we double the number of pointer bits to 96 - we can support YiBs of address space.
- dzaima 4y agoIn fact, today already there are CPUs that support larger address spaces. But OSes should be smart and only provide pointers with the top 16 bits free while the application fits - even if some programs in the future end up using >256TB of address space, not all will, and those that don't should be able to take advantage of 48-bit pointers. Moreover, a single program could even take advantage of a "low heap" that stores metadata, and can have 48-bit pointers pointing to it, and a "high heap" of the actual large data (whose addresses take the full 64 bits, but may include tagged pointers to the low heap without doubling the memory footprint of the already humongous 256TB)
- sbf501 4y agoAll I see is 1% performance improvement for 1,000% complexity increase.
- chrisseaton 4y agoBut a very small team of compiler people take on the extra complexity so a huge team of users can get the performance improvement.
- kazinator 4y agoNot boxing floating-point values on the heap can be a big deal. I retrofitted NaN boxing into a production Lisp implementation literally in one evening and morning, with minimal impact to all the existing code in the implementation that is built around the pointer tagging scheme that existed for 13 years. It's nicely delimited with #if CONFIG_NAN_BOXING. Accumulator-incrementing loop on pointer tagging: This is the TXR Lisp interactive listener of TXR 281. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. 1> (compile-toplevel '(for ((i 1.0) (acc 0.0)) ((< i 100000000.0) acc) ((inc acc i) (inc i)))) #<sys:vm-desc: 188b8d0> 2> (pprof [*1]) malloc bytes: 0 gc heap bytes: 6399999936 total: 6399999936 milliseconds: 5860 4.99999995e15 NaN Boxing: This is the TXR Lisp interactive listener of TXR 281. Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet. 1> (compile-toplevel '(for ((i 1.0) (acc 0.0)) ((< i 100000000.0) acc) ((inc acc i) (inc i)))) #<sys:vm-desc: 24b7dc0> 2> (pprof [*1]) malloc bytes: 0 gc heap bytes: 0 total: 0 milliseconds: 4079 4.99999995e15 The speedup is 43.6% here. 3> (/ (- 5860 4079) 4079) 0.436626624172591 This is not native code. The difference would be more emphasized in native code. However, code that doesn't do floating-point calculation (or even some that does) will see a small performance penalty due to the more complex access to all values. That is a bummer. At least users can choose; if you don't care about floating-point, build it with pointer tagging.
- sbf501 4y agoI was referring to the table on their original web page. The last two rows are a 1.5% performance difference.
- kazinator 4y agoI released TXR 282 with NaN boxing support. The pre-built binary for Android doesn't use it though; I discovered late in the release process that on Android's Bionic Libc, pointers are coming out of the heap with 64-bit-wide values like 0xb40000NNNNNNNNNN. So, swift crash in early startup. I will research into this for the next release. Anyone finding things dead in the water like this has to use ./configure --no-nan-boxing. Another issue I ran into is that when I tested with gcc 12.2 on a RISC-V machine, the double to integer conversion code threw a weird uninitialized warning, not just the warning about strict aliasing against the use of u in the second line: ucnum u = coerce(ucnum, num) - NAN_FLNUM_DELTA; return *coerce(double *, &u); I added pragmas to suppress that. Anyway, everything built and tests passed on that installation.
- kazinator 4y agoHere is the issue: https://source.android.com/docs/security/test/tagged-pointers https://source.android.com/docs/security/test/tagged-pointer... Android is tagging the top byte of a pointer to check for misuses, like a pointer into the stack being passed to free() and such. I have successfully worked around it. The only pointers affected by this that we care about are Lisp heap objects. These are allocated in large block. When we allocate a heap block, we clear the top 16 bits of the pointer, and save that value in heap->tag. Then, if and when we free that heap block, instead of calling free(heap), we first mask back the heap->tag that we stripped away and free the resulting pointer. Everything builds on a Pixel 4a; tests pass. In spite of the rude language in that Android documentation, whereby some troglodytes disparage the work of their superiors, and give grave admonishments, it's possible to peacefully coexist.
- spacechild1 4y ago> A compiler can also change the order of fields if this could improve the speed of reading them No, C does NOT allow that! C++ theoretically allows to reorder sections with different access specifiers (public, protected, private), but I don't think any compiler actually does this. It would just create a big mess for little gain.