12 ms·

I've seen that pointer sharing thing in other languages in the past. Back in the 80's we did that in an app in MacOS when the memory pointers didn't require all

I've seen that pointer sharing thing in other languages in the past. Back in the 80's we did that in an app in MacOS when the memory pointers didn't require all the bits.

mikeash 9y ago
This is usually called a tagged pointer and is a common way to optimize highly dynamic languages: https://en.wikipedia.org/wiki/Tagged_pointer https://en.wikipedia.org/wiki/Tagged_pointer (I just noticed that two of my articles are cited for that page. How neat!) For more examples, Objective-C does this on 64-bit, and many Lisp implementations use it. Swift uses it for certain enum payloads. An interesting variant is to stuff your pointers into the payload of an IEEE754 NaN value. This is popular in JavaScript, since JS numbers are IEEE754 doubles.
- brandur 9y ago
  Fascinating — I had no idea the technique had a name (the Ruby source isn't very heavy on comments). I'll update the article to include it.
  - wrs 9y ago
    This technique is so common in dynamic language implementations that it even has hardware support in some architectures, such as the SPARC TADD instruction that adds two registers and sets a condition code if any of the lower bits were set.
  - xfer 9y ago
    Here is a common-lisp compiler using tagged pointers for some common objects. https://github.com/sbcl/sbcl/blob/master/doc/internals/objects-in-memory.texinfo https://github.com/sbcl/sbcl/blob/master/doc/internals/objec... That is how Lisps speedup list operations since it is the most used data structure.
- cben 9y ago
  Nice article covering both tagged integers and pointers in NaN: https://nikic.github.io/2012/02/02/Pointer-magic-for-efficient-dynamic-value-representations.html https://nikic.github.io/2012/02/02/Pointer-magic-for-efficie... Copy of Mozilla's article presenting their switch to NaN tagging: https://evilpie.github.io/sayrer-fatval-backup/cache.aspx.htm#post-485 https://evilpie.github.io/sayrer-fatval-backup/cache.aspx.ht... HN discussion with more history & links: https://news.ycombinator.com/item?id=1569825 https://news.ycombinator.com/item?id=1569825
astrange 9y ago
Since most pointers in macOS are 4-byte aligned (guaranteed by malloc), you can use the low bits for flags without having to shift anything. Of course Obj-C already uses this for tagged-pointer numbers/strings/etc, so you've got competition if you want to start using this for something.

I've seen that pointer sharing thing in other languages in the past. Back in the 80's we did that in an app in MacOS when the memory pointers didn't require all the bits.

mikeash 9y ago

This is usually called a tagged pointer and is a common way to optimize highly dynamic languages: https://en.wikipedia.org/wiki/Tagged_pointer https://en.wikipedia.org/wiki/Tagged_pointer (I just noticed that two of my articles are cited for that page. How neat!) For more examples, Objective-C does this on 64-bit, and many Lisp implementations use it. Swift uses it for certain enum payloads. An interesting variant is to stuff your pointers into the payload of an IEEE754 NaN value. This is popular in JavaScript, since JS numbers are IEEE754 doubles.

brandur 9y ago
Fascinating — I had no idea the technique had a name (the Ruby source isn't very heavy on comments). I'll update the article to include it.
- wrs 9y ago
  This technique is so common in dynamic language implementations that it even has hardware support in some architectures, such as the SPARC TADD instruction that adds two registers and sets a condition code if any of the lower bits were set.
- xfer 9y ago
  Here is a common-lisp compiler using tagged pointers for some common objects. https://github.com/sbcl/sbcl/blob/master/doc/internals/objects-in-memory.texinfo https://github.com/sbcl/sbcl/blob/master/doc/internals/objec... That is how Lisps speedup list operations since it is the most used data structure.
cben 9y ago
Nice article covering both tagged integers and pointers in NaN: https://nikic.github.io/2012/02/02/Pointer-magic-for-efficient-dynamic-value-representations.html https://nikic.github.io/2012/02/02/Pointer-magic-for-efficie... Copy of Mozilla's article presenting their switch to NaN tagging: https://evilpie.github.io/sayrer-fatval-backup/cache.aspx.htm#post-485 https://evilpie.github.io/sayrer-fatval-backup/cache.aspx.ht... HN discussion with more history & links: https://news.ycombinator.com/item?id=1569825 https://news.ycombinator.com/item?id=1569825

astrange 9y ago

Since most pointers in macOS are 4-byte aligned (guaranteed by malloc), you can use the low bits for flags without having to shift anything. Of course Obj-C already uses this for tagged-pointer numbers/strings/etc, so you've got competition if you want to start using this for something.