Hacker News Reader

Comment by praptak | Hacker News Reader

SBCL uses a single zero bit to tag integers. This trick means the representation of n is just 2n, so you can add the values directly without any decoding.

It obviously also means that all the other tag values have to use 1 as the last bit.

View on HN

Why do they use the bottom bit for tag and not the top bit?

Traditionally it has been done because the last three bits in an object pointer typically are always zero because of alignment, so you could just put a tag there and mask it off (or load it with lea and an offset, especially useful if you have a data structure where you'd use an offset anyway like pairs or vectors). In 64-bit architectures there are two bytes at the top that aren't used (one byte with five-level paging), but they must be masked, since they must be 0x00 or 0xff when used for pointers. In 32-bit archs the high bits were used and unsuitable for tags. All in all, I think the low bits still are the most useful for tags, even if 32-bit is not an important consideration anymore.

The sibling comment explains why we prefer to use the lower bits as a tag (these are guaranteed to be zero if the value is a pointer on a 64-bit system).

Another reason why we wouldn’t want to use the top bit is that, as the parent comment suggested, the tagged pointer representation of a fixnum integer isn’t a pointer at all but is instead twice the number it represents. Generally speaking, we represent integers in twos-complement representation which uses that top bit to determine if the value is positive or negative.

That also implies that NIL cannot be represented as 0, which is a pity since testing the Z flag would be quick. I'd think someone ran the numbers and found the chosen encoding superior, but that would have been long ago (in the CMUCL code base).

I suspect with modern CPU pipelining and branch prediction that most of the (very interesting) debates about exactly how to tag values and pointers have become inconsequential above the noise level.

Would love to see recent work demonstrating this isn’t true!

That’s so cool. I did not know that.

Reply on news.ycombinator.com