optimisation to freeGroup() to avoid an O(N^2) pathalogical case
authorSimon Marlow <simonmar@microsoft.com>
Tue, 21 Nov 2006 13:45:51 +0000 (13:45 +0000)
committerSimon Marlow <simonmar@microsoft.com>
Tue, 21 Nov 2006 13:45:51 +0000 (13:45 +0000)
commitfec956d14d1cbad5a28a1cad7c7d5c0859136f69
treebc8b4d24b43d1b1b1f58136f019299c0f61e5efc
parent2b49cf43578194443e0481b4680c3542c3d31bff
optimisation to freeGroup() to avoid an O(N^2) pathalogical case
In the free list, we don't strictly speaking need to have every block
in a coalesced group point to the head block, although this is an
invariant for non-free blocks.  Dropping this invariant for the free
list means that coalesce() is O(1) rather than O(N), and freeGroup()
is therefore O(N) not O(N^2).

The bad case probably didn't happen most of the time, indeed it has
never shown up in a profile that I've seen.  I had a report from a
while back that this was a problem with really large heaps, though.
Fortunately the fix is easy.
rts/sm/BlockAlloc.c