[GHC] #8609: Clean up block allocator

[GHC]

#8609: Clean up block allocator
-------------------------------------+-------------------------------------
       Reporter:  ezyang             |             Owner:  ezyang
           Type:  bug                |            Status:  new
       Priority:  low                |         Milestone:
      Component:  Runtime System     |           Version:  7.7
       Keywords:  patch              |  Operating System:  Unknown/Multiple
   Architecture:  Unknown/Multiple   |   Type of failure:  Runtime
     Difficulty:  Easy (less than 1  |  performance bug
  hour)                              |         Test Case:
     Blocked By:                     |          Blocking:
Related Tickets:                     |
-------------------------------------+-------------------------------------
 For fun, I was reimplementing GHC's block allocator in Rust, and I noticed
 that there are a number of things the current block allocator code does
 that result in extra, unnecessary work:

 * Upon a perfect match, `alloc_mega_group` initializes the returned block
 group (`initGroup`). This is unnecessary, because the caller of
 `alloc_mega_group` is responsible for initializing the block groups.

 * The `initGroup` function uses the `blocks` to figure out how many block
 descriptors it needs to initialize. However, in the case of a multi-
 megablock group, blocks will larger than BLOCKS_PER_MBLOCK, so this
 process will march into the first block and write information to block
 descriptors which will be later be overwritten by the user data. So,
 `initGroup` should cap at the block descriptors of the first megablock.
 One can go even further: if a block group spans multiple megablocks, then
 in practice, the only block descriptor we care about is the very first
 one, since we're not allowed to have internal GC'd pointers to the block
 group (as not every address in the group has a valid bdescr associated
 with it).

 * The commentary should add a bit about mblock groups. Essentially, the
 mblock free list has a different set of invariants: the first mblock's
 start pointers are guaranteed to be initialized (the mblock was
 `initMBlock` 'd), and the blocks and link fields of the first bdescr will
 be something appropriate; there are no other guarantees.

 Here are the proposed functional changes (obviously some extra
 documentation is necessary; replace the XXX marked expression with
 BLOCKS_PER_MBLOCK if you want to do the more conservative changes for
 larger than mblock block chains):

 {{{
 diff --git a/rts/sm/BlockAlloc.c b/rts/sm/BlockAlloc.c
 index 18c167f..33530d8 100644
 --- a/rts/sm/BlockAlloc.c
 +++ b/rts/sm/BlockAlloc.c
 @@ -170,7 +170,7 @@ initGroup(bdescr *head)
    bdescr *bd;
    W_ i, n;

 -  n = head->blocks;
 +  n = head->blocks > BLOCKS_PER_MBLOCK ? 1 /* XXX */ : head->blocks;
    head->free   = head->start;
    head->link   = NULL;
    for (i=1, bd = head+1; i < n; i++, bd++) {
 @@ -278,7 +278,6 @@ alloc_mega_group (StgWord mblocks)
              } else {
                  free_mblock_list = bd->link;
              }
 -            initGroup(bd);
              return bd;
          }
          else if (bd->blocks > n)
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8609>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler