Re: Slowdown around 5.0.5-dev-0

[Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx>]

On Oct 11, 10:39am, Sebastian Gniazdowski wrote:
}
} Zprof says there is no change:

Well, that's not entirely surprising.  It probably just means that there
is some space in a lot of arenas, so fpop doesn't move far from the head
of the list.  Or it could mean that the real problem is popheap() rather
than freeheap().

} BTW, the patch didn't apply to head or to 23f98c3,

Curious.  "git diff master origin/master" shows no diffs for my local
repository, and the patch was just a straight "git diff".

There were additional changes committed after 23f98c3 so there's no
reason to have expected it would apply to that.

In any case here's another stab at it.  Should apply to 83a1757.  This
should help if there's a lot of freeheap() happening, but not so much
if there's a lot of push/pop (in fact it may be worse in that case).

If it's push/pop that's the issue, the next step would be to try to
identify the crucial pushheap() and replace it with NEWHEAPS() if the
scope permits.


diff --git a/Src/mem.c b/Src/mem.c
index b9569ea..d49f685 100644
--- a/Src/mem.c
+++ b/Src/mem.c
@@ -294,7 +294,7 @@ pushheap(void)
 #endif
 
     for (h = heaps; h; h = h->next) {
-	DPUTS(!h->used, "BUG: empty heap");
+	DPUTS(!h->used && h->next, "BUG: empty heap");
 	hs = (Heapstack) zalloc(sizeof(*hs));
 	hs->next = h->sp;
 	h->sp = hs;
@@ -334,17 +334,15 @@ freeheap(void)
      *
      * Whenever fheap is NULL here, the loop below sweeps back over the
      * entire heap list again, resetting the free space in every arena to
-     * the amount stashed by pushheap() and finding the first arena with
+     * the amount stashed by pushheap() and finding the arena with the most
      * free space to optimize zhalloc()'s next search.  When there's a lot
      * of stuff already on the heap, this is an enormous amount of work,
      * and performance goes to hell.
      *
-     * However, if the arena to which fheap points is unused, we want to
-     * free it, so we have no choice but to do the sweep for a new fheap.
-     */
-    if (fheap && !fheap->sp)
-	fheap = NULL;	/* We used to do this unconditionally */
-    /*
+     * Therefore, we defer freeing the most recently allocated arena until
+     * we reach popheap().  This may fail to reclaim some space in earlier
+     * arenas.
+     *
      * In other cases, either fheap is already correct, or it has never
      * been set and this loop will do it, or it'll be reset from scratch
      * on the next popheap().  So all that's needed here is to pick up
@@ -361,7 +359,11 @@ freeheap(void)
 	    memset(arena(h) + h->sp->used, 0xff, h->used - h->sp->used);
 #endif
 	    h->used = h->sp->used;
-	    if (!fheap && h->used < ARENA_SIZEOF(h))
+	    if (!fheap) {
+		if (h->used < ARENA_SIZEOF(h))
+		    fheap = h;
+	    } else if (ARENA_SIZEOF(h) - h->used >
+		       ARENA_SIZEOF(fheap) - fheap->used)
 		fheap = h;
 	    hl = h;
 #ifdef ZSH_HEAP_DEBUG
@@ -384,6 +386,26 @@ freeheap(void)
 	    VALGRIND_MEMPOOL_TRIM((char *)h, (char *)arena(h), h->used);
 #endif
 	} else {
+	    if (h->next) {
+		/* We want to cut this out of the arena list if we can */
+		if (h == heaps)
+		    hl = heaps = h->next;
+		else if (hl && hl->next == h)
+		    hl->next = h->next;
+		else {
+		    DPUTS(hl, "hl->next != h when freeing");
+		    hl = h;
+		    continue;
+		}
+		h->next = NULL;
+	    } else {
+		/* Leave an empty arena at the end until popped */
+		h->used = 0;
+		fheap = hl = h;
+		break;
+	    }
+	    if (fheap == h)
+		fheap = NULL;
 #ifdef USE_MMAP
 	    munmap((void *) h, h->size);
 #else
@@ -441,12 +463,29 @@ popheap(void)
 #ifdef ZSH_VALGRIND
 	    VALGRIND_MEMPOOL_TRIM((char *)h, (char *)arena(h), h->used);
 #endif
-	    if (!fheap && h->used < ARENA_SIZEOF(h))
+	    if (!fheap) {
+		if (h->used < ARENA_SIZEOF(h))
+		    fheap = h;
+	    } else if (ARENA_SIZEOF(h) - h->used >
+		       ARENA_SIZEOF(fheap) - fheap->used)
 		fheap = h;
 	    zfree(hs, sizeof(*hs));
 
 	    hl = h;
 	} else {
+	    if (h->next) {
+		/* We want to cut this out of the arena list if we can */
+		if (h == heaps)
+		    hl = heaps = h->next;
+		else if (hl && hl->next == h)
+		    hl->next = h->next;
+		else {
+		    DPUTS(hl, "hl->next != h when popping");
+		    hl = h;
+		    continue;
+		}
+		h->next = NULL;
+	    }
 #ifdef USE_MMAP
 	    munmap((void *) h, h->size);
 #else
@@ -524,7 +563,7 @@ zheapptr(void *p)
 mod_export void *
 zhalloc(size_t size)
 {
-    Heap h;
+    Heap h, hp = NULL;
     size_t n;
 #ifdef ZSH_VALGRIND
     size_t req_size = size;
@@ -546,6 +585,7 @@ zhalloc(size_t size)
     for (h = ((fheap && ARENA_SIZEOF(fheap) >= (size + fheap->used))
 	      ? fheap : heaps);
 	 h; h = h->next) {
+	hp = h;
 	if (ARENA_SIZEOF(h) >= (n = size + h->used)) {
 	    void *ret;
 
@@ -566,7 +606,6 @@ zhalloc(size_t size)
 	}
     }
     {
-	Heap hp;
         /* not found, allocate new heap */
 #if defined(ZSH_MEM) && !defined(USE_MMAP)
 	static int called = 0;
@@ -575,7 +614,6 @@ zhalloc(size_t size)
 #endif
 
 	n = HEAP_ARENA_SIZE > size ? HEAPSIZE : size + sizeof(*h);
-	for (hp = NULL, h = heaps; h; hp = h, h = h->next);
 
 #ifdef USE_MMAP
 	h = mmap_heap_alloc(&n);
@@ -607,6 +645,7 @@ zhalloc(size_t size)
 	VALGRIND_MEMPOOL_ALLOC((char *)h, (char *)arena(h), req_size);
 #endif
 
+	DPUTS(hp && hp->next, "failed to find end of chain in zhalloc");
 	if (hp)
 	    hp->next = h;
 	else