Changes between Version 2 and Version 3 of Commentary/Rts/Storage

Sep 12, 2006 2:35:38 PM (11 years ago)



  • Commentary/Rts/Storage

    v2 v3  
    99== The Block Allocator ==
     11Source: [[GhcFile(includes/Block.h)]], [[GhcFile(rts/BlockAlloc.h)]], [[GhcFile(rts/BlockAlloc.c)]].
     13The block allocator is where the storage manager derives much of its flexibilty.  Rather than keep our heap in a single contiguous region of memory, or one contiguous region per generation, we manage linked lists of memory blocks.  Managing contiguous regions is difficult, especially when you want to change the size of some of the areas.  A block-structured storage arrangement has several advantages:
     15 * resizing areas of memory is easy: just chain more blocks onto the list.
     17 * managing large objects without copying is easy: allocate each one a complete block, and use the block linkage to
     18   chain them together.
     20 * free memory can be recycled faster, because a block is a block.
     22The concept relies on the property that most data objects are significantly smaller than a block, and only rarely do we need to allocate objects that approach or exceed the size of a block.
     24=== Structure of blocks ===
     26We want to allocate memory in units of a small block (around 4k, say).  Furthermore, we want each block to have an associated small structure called a ''block descriptor'', which contains information about the block: its link field, which generation it belongs to, and so on.  We want a function `Bdescr(p)`, that, given an arbitrary pointer into a block, returns the address of the block descriptor that corresponds to the block containing that pointer.
     28There are two options:
     30 * Put the block descriptor at the start of the block.  `Bdescr(p) = p & ~BLOCK_SIZE`.  This option has problems if
     31   we need to allocate a contiguous region larger than a single block (GHC does this occasionally when allocating
     32   a large number of objects in one go).
     34 * Allocate memory in larger units (a ''megablock''), divide the megablock into blocks, and put all the block
     35   descriptors at the beginning.  The megablock is aligned, so that the address of the block descriptor for
     36   a block is a simple function of its address.  The 'Bdescr' function is more complicated than the first
     37   method, but it is easier to allocate contiguous regions (unless the contiguous region is larger than
     38   a megablock...).
    1143== The Garbage Collector ==