From: Simon Marlow <simonmar@microsoft.com>
Date: Tue, 21 Nov 2006 13:45:51 +0000 (+0000)
Subject: optimisation to freeGroup() to avoid an O(N^2) pathalogical case
X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=commitdiff_plain;h=fec956d14d1cbad5a28a1cad7c7d5c0859136f69

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.
---

diff --git a/rts/sm/BlockAlloc.c b/rts/sm/BlockAlloc.c
index d2f08ee..1149260 100644
--- a/rts/sm/BlockAlloc.c
+++ b/rts/sm/BlockAlloc.c
@@ -80,10 +80,7 @@ allocGroup(nat n)
   for (bd = free_list; bd != NULL; bd = bd->link) {
     if (bd->blocks == n) {	/* exactly the right size! */
       *last = bd->link;
-      /* no initialisation necessary - this is already a
-       * self-contained block group. */
-      bd->free = bd->start;	/* block isn't free now */
-      bd->link = NULL;
+      initGroup(n, bd);		/* initialise it */
       return bd;
     }
     if (bd->blocks >  n) {	/* block too big... */
@@ -219,20 +216,26 @@ allocMegaGroup(nat n)
 STATIC_INLINE bdescr *
 coalesce(bdescr *p)
 {
-  bdescr *bd, *q;
-  nat i, blocks;
+  bdescr *q;
 
   q = p->link;
   if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
     /* can coalesce */
     p->blocks += q->blocks;
     p->link    = q->link;
-    blocks = q->blocks;
-    for (i = 0, bd = q; i < blocks; bd++, i++) {
-	bd->free = 0;
-	bd->blocks = 0;
-	bd->link = p;
+#ifdef DEBUG
+    {
+	nat i, blocks;
+	bdescr *bd;
+	// not strictly necessary to do this, but helpful if we have a 
+	// random ptr and want to figure out what block it belongs to.
+	for (i = 0, bd = q; i < q->blocks; bd++, i++) {
+	    bd->free = 0;
+	    bd->blocks = 0;
+	    bd->link = p;
+	}
     }
+#endif
     return p;
   }
   return q;