Clean up block allocator
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 ofalloc_mega_group
is responsible for initializing the block groups. - The
initGroup
function uses theblocks
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)
Trac metadata
Trac field | Value |
---|---|
Version | 7.7 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | low |
Resolution | Unresolved |
Component | Runtime System |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | simonmar |
Operating system | |
Architecture |