Hacker News Reader

Comment by RodgerTheGreat | Hacker News Reader

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

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.

View on HN

> 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 and 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...), 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.

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.

> 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).

On reading this I immediately read the standard, hoping to discover that the word "fraction" wasn't used, only to find that "fraction" is defined as the part of the significand (mantissa) lying to the right of the implied binary point. In essence then (because the bit to the "left" of the binary point is only ever implied, never explicit), "fraction" stands as a synonym for significand.

Unfortunate terminology. And why? Here's why:

A fraction: 1/3

A significand, base ten: 0.3333333333333333

IEEE 754 can provide the second, but it cannot provide the first.

IEEE 754:

http://kfe.fjfi.cvut.cz/~klimo/nm/ieee754.pdf

Significand:

http://en.wikipedia.org/wiki/Significand

A quote: "The significand (also coefficient or mantissa) is part of a floating-point number, consisting of its significant digits."

p.s. this is not a correction, it's a lament.

It's actually even more complicated...

Remember, this is binary, so the only possible digits are 0 and 1. For example, 1/3 in binary is 0.01010101010101...;

Encoding that in "floating point", we first get:

  1.0101010101 * 2^-2;

We can see that in this format, the first digit of the number is always 1; thus, the first digit of the significand, for any number, is ALWAYS 1 (in binary)! IEEE754 makes the optimization to not store this leading 1 as part of the fraction, so the the approximation to 1/3 is actually encoded as:

  0 01111111101 0101010101010101010101010101010101010101010101010101
  ^      ^            ^
  |      +-----+      |
  sign bit     |    fraction = 1.33333... = 1.01010101010101...0101010101010101b
               |                              |---  this part is included  ---|
               |
        exponent = 01111111101b - 1023 = 1021 - 1023 = -2

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

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.

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.

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.

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.

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.

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...

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

Reply on news.ycombinator.com