From 9f8e3e82dd2c2bb98f72b6e026b72d9c47d5ad62 Mon Sep 17 00:00:00 2001
From: "Barton E. Schaefer" <schaefer@zsh.org>
Date: Sun, 11 Oct 2015 21:11:10 -0700
Subject: 36834: freeheap preserves last allocated heap

This is the first of two optimizations to improve heap performance when
there are a large number of mostly-filled heap arenas.
---
 Src/mem.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 52 insertions(+), 13 deletions(-)

(limited to 'Src')

diff --git a/Src/mem.c b/Src/mem.c
index b9569ea0c..d49f685fe 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
-- 
cgit 1.4.1