[MLton] card and cross maps

[Stephen Weeks]

>   * the cardMap is an array whose cardinality is equal to the size of the
>     heap divided by the card size.  Hence, there is an element in the card
>     map for each card in the heap.  The card size is 2^8 = 256 bytes.
>     Each element in the array is interpreted as a boolean; true means that
>     some mutable field of some object in the portion of the heap
>     corresponding to the appropriate card has been written since the last
>     minor GC; hence, the corresponding card must be traced at the next
>     minor copying GC.

Yes.

>   * the crossMap is an array whose cardinality is also equal to the size of
>     the heap divided by the card size.  Each element in the array is
>     interpreted as an offset; the offset indicates the number of 32-bit
>     words from the start of the corresponding card at which point the last
>     object in the card starts.

Yes.

>     Hence, when scanning a card, the cross map
>     entry of the previous card is used to determine where precisely to
>     start scanning (since objects may not align on card boundaries).

Not quite the previous card, since the previous cross map entry may be
empty.  Instead, use the previous card among those with a nonempty
cross map entry.  Same idea.  BTW, the code
(forwardIntergenerationPointers) doesn't actually need to step back
through the cross map to find the nonempty entry, since, as it scans
the old generation from beginning to end, it maintains as an invariant
(objectStart) the last object prior to the current card.  Actually,
given that, I'm not quite sure why skipObjects is needed, since I
don't see how the object at objectStart could point earlier than the
card being scanned.  If it did, wouldn't the crossMap have caused us
to have moved objectStart forward?  Hmmm.  If you can figure out a
situation where minorBytesSkipped will be nonzero I'd like to see it.

> My question: why does the crossMap offset count 32-bit words, rather
> than 8-bit bytes?

I don't think it's anything deeper than the fact that all objects are
32-bit aligned, so why waste the extra 2 bits.  As you mention, it
does allow a larger card size (2^9) to be used.

> Simply to accomodate larger card sizes without needing to grow the
> size of a crossMap entry?

I don't recall ever considering making the card map and cross map of
different sizes.  Initially, the cross map did have a different
meaning than it does now (it was also a bit map), but it changed a
couple of years ago (r1980) to the current meaning.

> I note that an 8bit crossMap entry only admits card-sizes up to 2^9
> = 512 bytes, since the value 255 is reserved for EMPTY_CROSS_MAP.

I remember testing various card sizes, up to about 2^12 IIRC, but that
must have been when the crossMap had its old meaning as a bit-map.
You're right, I don't see how the current crossMap could support card
sizes of more than 2^9.  Anyways, I think the 1% space overhead of the
card map and cross map due to the current card size (2^8) has proved
quite acceptable, and there's no real need for experimentation of that
parameter.  We (i.e. I) even removed -card-size-log2 a while back.

So, if you want to change crossMap offset to use bytes instead of
words, I have no objection.  I'm curious to know why it might help,
though, or if it's more for general cleanliness and consistency.