4 ms·

If you can look at a word of memory and differentiate pointers from values, garbage collection can become extremely simple. It's a shame that tagged architectur

If you can look at a word of memory and differentiate pointers from values, garbage collection can become extremely simple. It's a shame that tagged architectures have largely died out. As an experiment, I tried writing a garbage collector which used high-order bits of a word to identify pointers. The result is about a page of code in Forth: http://hastebin.com/raw/gabunowelo.fs http://hastebin.com/raw/gabunowelo.fs This example works exclusively with fixed-size "cons pair" allocations, but generalizing to arbitrary-sized allocations only increases the complexity of the system slightly. Obviously this bitflag technique is not "safe" in general, as arbitrary values on the stacks could produce false positives, but it's easy to imagine a 33-bit or 65-bit architecture that provided the necessary hardware support without such caveats.

derleth 14y ago
This is why, by default on 32-bit architectures, fixnums in GNU Emacs are 30 bits: http://stackoverflow.com/questions/106597/why-are-fixnums-in-emacs-only-29-bits http://stackoverflow.com/questions/106597/why-are-fixnums-in... http://www.gnu.org/software/emacs/manual/html_node/elisp/Integer-Basics.html http://www.gnu.org/software/emacs/manual/html_node/elisp/Int... SBCL has a more elaborate tag bit system: http://sbcl-internals.cliki.net/tag%20bit http://sbcl-internals.cliki.net/tag%20bit
alexrp 14y ago
Hey, you may be interested to know that in the upcoming ARM v8's AArch64 mode, the upper 8 bits of all pointers can be used freely for tagged pointers. See page 11 of: http://board.flatassembler.net/download.php?id=5698 http://board.flatassembler.net/download.php?id=5698
- barrkel 14y ago
  The issue isn't adding extra data to pointers; it's distinguishing a pointer from an integer of the same size. The extra bit needs to be "meta". Some x64 targeted languages already use tagged pointers without specific hardware support; e.g. I recall reading about JVM using several bits of object pointers in 64-bit to encode a class index, so that polymorphic inline caches can be checked without an indirection.
  - alexrp 14y ago
    Sure. This was just meant as an interesting tidbit. On ARM v8, you'll still need the compiler/VM to help you out as far as type precision goes, of course.
  - krichman 14y ago
    Right, any language could do this -- `malloc` and friends return pointers aligned to 16 bytes, giving you 4 bits at the bottom that are totally free. It can go even further than that; most systems only use 48 bits for addresses -- this leaves more than enough space to "NaN-box" objects by putting the address inside the extraneous bits of a 64 bit floating NaN.
    - stonemetal 14y ago
      Right, any language could do this -- `malloc` and friends return pointers aligned to 16 bytes How does the having the bottom 4 bits free in a pointer help if you can't use them to tell the difference between a pointer and an integer 1 or 2? He is asking for a reserved set of bits on every data type so that he can store minimal type information like pointer, not pointer.
      - krickle 14y ago
        To use this, you would have a tag for ints and a tag for pointers; when using the ints you shift right 4 bits, pointers would be masked before use.
sedachv 14y ago
> It's a shame that tagged architectures have largely died out. Judging by benchmarks, it's a good thing they did. Byte-addressed but word-aligned pointers plus pipelining and superscalar processors (branch prediction probably helps too) give you almost the same performance as explicit instructions for tag support. The amount of flexibility and the simplification in the instruction set you get from it is well worth it IMO. SPARC had such instructions, and on benchmarks (see http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html and http://www.cs.cmu.edu/~ram/pub/arch.ps http://www.cs.cmu.edu/~ram/pub/arch.ps) the difference in speed between using them and not was less than 5%. On a 64-bit machine, you have 30 different tags available (5 tag bits, since the smallest thing you'd want to point at is going to be two 64-bit words big, and two of the 5-bit patterns reserved for positive and negative fixnums, for 60-bit immediate integers). The problem is a lot of algorithms (especially crypto) are designed around 32 or 64 bit words, which typically means you have to make contortions and declarations to have your compiler operate on immediate representations. Typically, the compiler will set aside some registers on the CPU for dealing with these immediate values, so the garbage collector doesn't get confused. On x86 this might mean you don't have enough registers to run the algorithm efficiently, even if the compiler knows exactly what needs to be unboxed. Another problem is floating point values. On 64-bit systems there's a technique called NaN-boxing that can do something about this (http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation...), but I don't yet understand how it works. I do agree on one thing - slapping an extra byte onto word size would be awesome, as long as that extra byte is general purpose. Other things besides tagging that you could do with it would be error-correcting codes (the Symbolics Ivory actually had ECC for every word), and all kinds of metadata. Maybe it would even make sense to keep this extra byte out of the memory bus and just have it on registers; that's where most of the trouble with tagged values on modern machines seems to come from. This would make sense for load/store instruction sets.
- tomp 14y ago
  In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). The exponent 7FF (in binary: all ones) is reserved for special values: NaN and infinity. If the fraction is 0 (all zeroes), then the number is +/- inf, otherwise it is a NaN. NaN-tagging works by using the unused variations of NaN for pointers. The trick is that most processors only generate a single binary pattern for NaN, so all other binary patterns are never used to represent floating point numbers, and can thus be used to represent pointers. This works since the current x64 implementations only use 48 bits for the pointers, so all pointers can "fit" into the remaining 52 bits of NaN.

derleth 14y ago

This is why, by default on 32-bit architectures, fixnums in GNU Emacs are 30 bits: http://stackoverflow.com/questions/106597/why-are-fixnums-in-emacs-only-29-bits http://stackoverflow.com/questions/106597/why-are-fixnums-in... http://www.gnu.org/software/emacs/manual/html_node/elisp/Integer-Basics.html http://www.gnu.org/software/emacs/manual/html_node/elisp/Int... SBCL has a more elaborate tag bit system: http://sbcl-internals.cliki.net/tag%20bit http://sbcl-internals.cliki.net/tag%20bit

alexrp 14y ago

Hey, you may be interested to know that in the upcoming ARM v8's AArch64 mode, the upper 8 bits of all pointers can be used freely for tagged pointers. See page 11 of: http://board.flatassembler.net/download.php?id=5698 http://board.flatassembler.net/download.php?id=5698

barrkel 14y ago
The issue isn't adding extra data to pointers; it's distinguishing a pointer from an integer of the same size. The extra bit needs to be "meta". Some x64 targeted languages already use tagged pointers without specific hardware support; e.g. I recall reading about JVM using several bits of object pointers in 64-bit to encode a class index, so that polymorphic inline caches can be checked without an indirection.
- alexrp 14y ago
  Sure. This was just meant as an interesting tidbit. On ARM v8, you'll still need the compiler/VM to help you out as far as type precision goes, of course.
- krichman 14y ago
  Right, any language could do this -- `malloc` and friends return pointers aligned to 16 bytes, giving you 4 bits at the bottom that are totally free. It can go even further than that; most systems only use 48 bits for addresses -- this leaves more than enough space to "NaN-box" objects by putting the address inside the extraneous bits of a 64 bit floating NaN.
  - stonemetal 14y ago
    Right, any language could do this -- `malloc` and friends return pointers aligned to 16 bytes How does the having the bottom 4 bits free in a pointer help if you can't use them to tell the difference between a pointer and an integer 1 or 2? He is asking for a reserved set of bits on every data type so that he can store minimal type information like pointer, not pointer.
    - krickle 14y ago
      To use this, you would have a tag for ints and a tag for pointers; when using the ints you shift right 4 bits, pointers would be masked before use.

sedachv 14y ago

> It's a shame that tagged architectures have largely died out. Judging by benchmarks, it's a good thing they did. Byte-addressed but word-aligned pointers plus pipelining and superscalar processors (branch prediction probably helps too) give you almost the same performance as explicit instructions for tag support. The amount of flexibility and the simplification in the instruction set you get from it is well worth it IMO. SPARC had such instructions, and on benchmarks (see http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html and http://www.cs.cmu.edu/~ram/pub/arch.ps http://www.cs.cmu.edu/~ram/pub/arch.ps) the difference in speed between using them and not was less than 5%. On a 64-bit machine, you have 30 different tags available (5 tag bits, since the smallest thing you'd want to point at is going to be two 64-bit words big, and two of the 5-bit patterns reserved for positive and negative fixnums, for 60-bit immediate integers). The problem is a lot of algorithms (especially crypto) are designed around 32 or 64 bit words, which typically means you have to make contortions and declarations to have your compiler operate on immediate representations. Typically, the compiler will set aside some registers on the CPU for dealing with these immediate values, so the garbage collector doesn't get confused. On x86 this might mean you don't have enough registers to run the algorithm efficiently, even if the compiler knows exactly what needs to be unboxed. Another problem is floating point values. On 64-bit systems there's a technique called NaN-boxing that can do something about this (http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation...), but I don't yet understand how it works. I do agree on one thing - slapping an extra byte onto word size would be awesome, as long as that extra byte is general purpose. Other things besides tagging that you could do with it would be error-correcting codes (the Symbolics Ivory actually had ECC for every word), and all kinds of metadata. Maybe it would even make sense to keep this extra byte out of the memory bus and just have it on registers; that's where most of the trouble with tagged values on modern machines seems to come from. This would make sense for load/store instruction sets.

tomp 14y ago
In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). The exponent 7FF (in binary: all ones) is reserved for special values: NaN and infinity. If the fraction is 0 (all zeroes), then the number is +/- inf, otherwise it is a NaN. NaN-tagging works by using the unused variations of NaN for pointers. The trick is that most processors only generate a single binary pattern for NaN, so all other binary patterns are never used to represent floating point numbers, and can thus be used to represent pointers. This works since the current x64 implementations only use 48 bits for the pointers, so all pointers can "fit" into the remaining 52 bits of NaN.