[m-dev.] 4 tag bits

[Paul Bone]

On Wed, Jul 06, 2016 at 12:14:07PM +1000, Michael Day wrote:
> It occurs to me that the number of tag bits in use could even be
> proportional to the size/alignment of the type being pointed to, if the
> garbage collector was type-aware :)

I don't think there's a need for type awareness in the GC.

That being said this is probably difficult add to the Mercury code at this
point.  However I can provide some information about the collector.  I'm
also making educated guesses that would need to be confirmed.

Boehm allocates memory within "blocks" each block is dedicated to
allocations of a specific size (with some rounding).  So if you you want 1
word, you get an allocation of 2 words (1 granule) within a block dedicated
to allocations of 2 words.

Depending on how blocks are laid out, power of 2 sized allocations are
always guaranteed to be aligned.  So if I allocate 4 words, and it goes to
block for allocating 4 word-sized allocations, then those allocations may be
aligned on 4 word boundaries (I think that meta-information is stored at the
end of the block, I'd need to confirm this).  Allocations made to this block
would have 5 available tag bits (64bit).

However that's not safe on its own.  First it only works for power-of-two
sized allocations, Allocations to other blocks may have different alignment
guarantees, some of them may be stronger than the usual 2 granules.
Second my description above over-simplifies the word-size to granule-size
mapping.  This mapping is 1:N and dynamic, 6-word allocations may be placed
on a block for 4-granule allocations (8 words).  This will usually remain
constant through a program's execution, but I suspect that it can change.
It looks as if every so often the word->granule map (an array) is rebuilt.

It might be possible to control the word->granule map, at least for objects
of specific sizes, to provide guarantees about the number of tag bits
available on those objects.  My point is, that this would be tricky, but not
impossible, and that the GC need not understand the types.

Ah, Another problem with this is that if I have a structure like:

:- type foo
    --->    foo1(thing)
            /* 8 things */
    ;       foo2(thing, thing, thing, thing, thing, thing, thing, thing).

Then instances of foo2 are 8 words (4 granules) big, and may go on a page
for 4 granule allocations and have more tag bits available.  However foo1
only has the usual 4 tag bits, because it will not be aligned.  To make use
of this optimisation we can only use the minimum number of tag bits of a
type's constructors.


-- 
Paul Bone