Totally relevant to my interests! I’m glad you’re posting these and I’m about to read the older posts.
I was surprised by what you described as the common solutions, since that doesn’t match my experience. The only integer optimization I’ve personally seen in dynamic languages is pointer-tagging. It goes back to the earliest versions of LISP — the 1980s LISP machines even had a special architecture to add extra tag bits to every machine word. Smalltalk-80 used it as well. JS and Lua use the NaN-tagging variant.
So it felt a little weird to me that you would list two other optimizations, then say “i think we can do better…” which could be read as taking credit for pointer tagging (though I’m sure that wasn’t your intent!)
As for NaN tagging — I recently implemented it, and I think it’s useful even if ‘double’ isn’t your primary number type. Doubles have 53(?) bits of mantissa, so they can exactly represent integers up to +/-2^52. It’s easy to pull out the int part with some bit-twiddling. Ints outside that range can be allocated on the heap. What you gain is of course that doubles are cheap as well as ints, which is a big boon in some use cases.
In my implementation I used a few of the extra NaN bits as tags for other types, so I can store Booleans and even short (6-byte) strings or blobs inline. (My C++ code isn’t currently in a public repo, but I could publish it if there’s interest. It’s tied into other parts of my runtime, but the code should be clear enough to read at least.)
Thanks for the comment! I will adjust the wording. I’m definitely not trying to take credit for the idea – see all the pre existing projects I mention throughout the posts :)
Adjusted the wording to make it clear I did not come up with the idea.
Re: common solutions: CPython uses the small integer pool (they cache -5 to 256, inclusive) and a lot of runtimes use string interning.
Re: other types: it’s possible to fit strings, booleans, integers, some other objects, and pointers all into the same tagging scheme with pointer tagging, too!
I’m really enjoying this series! I recently came across NaN boxing in the browser engines while trying to figure out how safe it really is to use the 16 high bits of a u64 while doing some pointer swizzling in sled. Aspects of it kind of seem sketchy, but if the major browser engines are doing it, maybe it’s alright? But I’m likely to fall back to just using the bottom 2 bits and allocating sometimes to ensure future compatibility with more architectures.
In GNUstep, I encode 8-character 7-bit ASCII strings in 64-bit pointers (3 tag bits, 61 bits total, giving 8 characters + 5 bits which are enough for the length and two spare, one of which can be used as a ‘has-null-terminator’ tag). For some applications, I found 20% of total object allocations were this kind of string (path components, dictionary keys, and so on.
We’re planning on making the compiler use this kind of representation for union types in Verona so that you can trivially implement efficient storage types by doing things like T* | i60.
Totally relevant to my interests! I’m glad you’re posting these and I’m about to read the older posts.
I was surprised by what you described as the common solutions, since that doesn’t match my experience. The only integer optimization I’ve personally seen in dynamic languages is pointer-tagging. It goes back to the earliest versions of LISP — the 1980s LISP machines even had a special architecture to add extra tag bits to every machine word. Smalltalk-80 used it as well. JS and Lua use the NaN-tagging variant.
So it felt a little weird to me that you would list two other optimizations, then say “i think we can do better…” which could be read as taking credit for pointer tagging (though I’m sure that wasn’t your intent!)
As for NaN tagging — I recently implemented it, and I think it’s useful even if ‘double’ isn’t your primary number type. Doubles have 53(?) bits of mantissa, so they can exactly represent integers up to +/-2^52. It’s easy to pull out the int part with some bit-twiddling. Ints outside that range can be allocated on the heap. What you gain is of course that doubles are cheap as well as ints, which is a big boon in some use cases.
In my implementation I used a few of the extra NaN bits as tags for other types, so I can store Booleans and even short (6-byte) strings or blobs inline. (My C++ code isn’t currently in a public repo, but I could publish it if there’s interest. It’s tied into other parts of my runtime, but the code should be clear enough to read at least.)
Thanks for the comment! I will adjust the wording. I’m definitely not trying to take credit for the idea – see all the pre existing projects I mention throughout the posts :)
Adjusted the wording to make it clear I did not come up with the idea.
Re: common solutions: CPython uses the small integer pool (they cache -5 to 256, inclusive) and a lot of runtimes use string interning.
Re: other types: it’s possible to fit strings, booleans, integers, some other objects, and pointers all into the same tagging scheme with pointer tagging, too!
I’m really enjoying this series! I recently came across NaN boxing in the browser engines while trying to figure out how safe it really is to use the 16 high bits of a u64 while doing some pointer swizzling in sled. Aspects of it kind of seem sketchy, but if the major browser engines are doing it, maybe it’s alright? But I’m likely to fall back to just using the bottom 2 bits and allocating sometimes to ensure future compatibility with more architectures.
Please let me know what you think about this post or the others in the series!
Great article. It would be nice to mention NaN boxing. Some years ago I wrote up the operations you need for addition and multiplication if you want to use the carry bit to detect overflow, having worked them out from scratch and discovered that a few Smalltalk implementations were already doing this but others were still doing the naive thing of shifting out the tag bits.
In GNUstep, I encode 8-character 7-bit ASCII strings in 64-bit pointers (3 tag bits, 61 bits total, giving 8 characters + 5 bits which are enough for the length and two spare, one of which can be used as a ‘has-null-terminator’ tag). For some applications, I found 20% of total object allocations were this kind of string (path components, dictionary keys, and so on.
We’re planning on making the compiler use this kind of representation for union types in Verona so that you can trivially implement efficient storage types by doing things like
T* | i60.I do mention NaN boxing :)
Ah, sorry, I missed the note at the end.
I believe
new_intneeds a cast to avoid potentially left-shifting negative values.Ahhh I’ll take a look. Casting to uword is probably the move
Fixed!
as_intalso needed a cast