3 ms·

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

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.

rwmj 3y ago
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.
- fweimer 3y ago
  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.
  - rwmj 3y ago
    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.
    - fweimer 3y ago
      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.
gbin 3y ago
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.
- rwmj 3y ago
  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.
- hayley-patton 3y ago
  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].
  - pfdietz 3y ago
    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.
    - hayley-patton 3y ago
      > 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).
fdej 3y ago
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.

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.

rwmj 3y ago

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.

fweimer 3y ago
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.
- rwmj 3y ago
  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.
  - fweimer 3y ago
    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.

gbin 3y ago

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.

rwmj 3y ago
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.
hayley-patton 3y ago
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].
- pfdietz 3y ago
  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.
  - hayley-patton 3y ago
    > 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).

fdej 3y ago

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.