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
_______________________________________________
Cvs-ghc mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/cvs-ghc
