[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.