3 ms·
I just implemented NaN boxing for TXR Lisp several days ago. https://www.kylheku.com/cgit/txr/commit/?id=073e4a84090b11fdc12a7fbc8f50df5e7b1ae25a https://www.k
by kazinator 4y ago
I 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.