patch applied (ghc): optimisation to freeGroup() to avoid an O(N^2) pathalogical case

Simon Marlow simonmar at microsoft.com
Tue Nov 21 08:54:44 EST 2006


Tue Nov 21 05:45:51 PST 2006  Simon Marlow <simonmar at microsoft.com>
  * 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.

    M ./rts/sm/BlockAlloc.c -11 +14


More information about the Cvs-ghc mailing list