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

Ian Lynagh <[email protected]>
Newsgroups gmane.comp.lang.haskell.cvs.all
Message-ID <20061126040642.GA12444__9085.83264467797$1164514019$gmane$org@cvs.haskell.org>
Tue Nov 21 05:45:51 PST 2006  Simon Marlow <[email protected]>
  * 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/BlockAlloc.c -11 +14
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.