Hacker News Reader

Comment by Vogtinator | Hacker News Reader

I wonder why they set the LSB to indicate an integer and clear it for other types. If they did it the other way, integer operations could be faster as the +1/-1 would not be necessary any longer.

View on HN

But then a pointer would not be a pointer, the bottom bit would have to be masked before each use. Or I guess you could dealign everything but that has its own problems.

Most current CPUs support word loads with byte offsets, so instead of masking the implementation could just load with an odd byte offset. Probably you'd want offset 255 (or whatever matches the maximum negative offset that can be encoded directly in a load instruction) because it enables direct access to more fields.

What is also interesting is that negative (-4 or -8) offsets are already used. The pointer actually points to the first byte of the data, but there is a header located before the data which tells you how long the data is and some other runtime info used by the GC.

  +------------+------------+------------+------------+ - - -
  | header     | data[0]    | data[1]    | data[2]    |
  +------------+------------+------------+------------+ - - -
                ^
                pointer

(The real data part can be all kinds of things including stuff opaque to the GC like strings).

I'm still a bit unconvinced that swapping the sense of pointers vs ints is useful for OCaml, as it would be a massive change with no current evidence base. It seems better to me to work on better compiler optimizations so that integers can be kept in registers with their true value more often.

I was about to write that this needs an extra decoding step because an addressing mode that uses a base register, a scaled index register, and a byte offset is a very CISCy thing. But of course with 0-based integers, it's no longer necessary to decode the index, so it's probably a wash.

They explain it in the article, it is to differenciate between an int directly or a pointer. Pointers are aligned so they cannot have their LSB at 1.

Also less well known (even amongst OCaml programmers) is that the "10" bottom bits combination is used to indicate a result containing an exception. So all pointers must be aligned to at least 4 bytes, of course not a problem since 16 bit arches are not supported.

One can re-align when accessing; this is how SBCL e.g. handles tagging. e.g. the first slot would be accessed by MOV RAX, [RBX - 1].

Lisps have had this for decades. The realization that one could do this was one of the things that killed lisp machines, since it enabled lisps to be implemented efficiently on stock microprocessors, which were much cheaper due to economies of scale.

In SBCL, this also allows cons cells to have their own offset, so car and cdr are implemented with one instruction and are safe (that is, throw an exception if applied to something they don't work on) even in code compiled at (safety 0).

Now just waiting for parallel GC in SBCL. ;) Well, also waiting for some other things, I will admit.

> so car and cdr are implemented with one instruction and are safe (that is, throw an exception if applied to something they don't work on) even in code compiled at (safety 0).

It is? By default x86 will happily do unaligned accesses, and I'm pretty sure SBCL doesn't change that. Not sure about other instruction sets.

SBCL also uses double-word alignment and 4-bit tags, so you could CDR (expecting lowtag #b0111) a structure object (lowtag #b1111).

Um, you're right. I have no idea why I thought that was the case.

In your defense, I recall Self did use unaligned traps to deal with dispatching on heap object/immediate, when immediates didn't usually appear at a call site.

That is the way the FLINT fmpz type does it. The benefit is that you can check for pointers once and then use the operands like ordinary ints without the +1/-1 adjustments. For example, to multiply two integer matrices, you can do O(n^2) pointer checks and then do O(n^3) arithmetic operations without overhead. But if the pointer check is done each operation then the representation doesn't make much difference; whether you use the LSB or MSB as a tag, what kills performance is checking and branching based on a tag bit in the first place. What you'd want is a sufficiently smart compiler (TM) that can eliminate as many such checks as possible.

Reply on news.ycombinator.com