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