[MLton] card and cross maps
Matthew Fluet
fluet@cs.cornell.edu
Sun, 11 Sep 2005 20:29:48 -0400 (EDT)
I'm trying to understand what precisely the card and cross maps in the GC
are representing. If I've got this right, we have the following:
* 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.
* 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. 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).
My question: why does the crossMap offset count 32-bit words, rather than
8-bit bytes? Simply to accomodate larger card sizes without needing to
grow the size of a crossMap entry? 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.