_PyMalloc_Free(): As was already done for _PyMalloc_Malloc, rearranged

the code so that the most frequent cases come first.  Added comments.
Found a hidden assumption that a pool contains room for at least two
blocks, and added an assert to catch a violation if it ever happens in
a place where that matters.  Gave the normal "I allocated this block"
case a longer basic block to work with before it has to do its first
branch (via breaking apart an embedded assignment in an "if", and
hoisting common code out of both branches).

1 files changed, 47 insertions, 37 deletions

diff --git a/Objects/obmalloc.c b/Objects/obmalloc.c
index 8ec5dfc..6a55a14 100644
--- a/Objects/obmalloc.c
+++ b/Objects/obmalloc.c
@@ -667,6 +667,7 @@ void
 _PyMalloc_Free(void *p)
 {
 	poolp pool;
+	block *lastfree;
 	poolp next, prev;
 	uint size;
 
@@ -679,57 +680,66 @@ _PyMalloc_Free(void *p)
 		LOCK();
 		INCMINE;
 		/*
-		 * At this point, the pool is not empty
+		 * Link p to the start of the pool's freeblock list.  Since
+		 * the pool had at least the p block outstanding, the pool
+		 * wasn't empty (so it's already in a usedpools[] list, or
+		 * was full and is in no list -- it's not in the freeblocks
+		 * list in any case).
 		 */
-		if ((*(block **)p = pool->freeblock) == NULL) {
+		*(block **)p = lastfree = pool->freeblock;
+		pool->freeblock = (block *)p;
+		if (lastfree) {
 			/*
-			 * Pool was full
+			 * freeblock wasn't NULL, so the pool wasn't full,
+			 * and the pool is in a usedpools[] list.
 			 */
-			pool->freeblock = (block *)p;
-			--pool->ref.count;
+			assert(pool->ref.count < pool.capacity);
+			if (--pool->ref.count != 0) {
+				/* pool isn't empty:  leave it in usedpools */
+				UNLOCK();
+				return;
+			}
 			/*
-			 * Frontlink to used pools
-			 * This mimics LRU pool usage for new allocations and
-			 * targets optimal filling when several pools contain
-			 * blocks of the same size class.
+			 * Pool is now empty:  unlink from usedpools, and
+			 * link to the front of usedpools.  This ensures that
+			 * previously freed pools will be allocated later
+			 * (being not referenced, they are perhaps paged out).
 			 */
-			size = pool->szidx;
-			next = usedpools[size + size];
-			prev = next->prevpool;
-			pool->nextpool = next;
-			pool->prevpool = prev;
-			next->prevpool = pool;
-			prev->nextpool = pool;
-			UNLOCK();
-			return;
-		}
-		/*
-		 * Pool was not full
-		 */
-		pool->freeblock = (block *)p;
-		if (--pool->ref.count != 0) {
+			next = pool->nextpool;
+			prev = pool->prevpool;
+			next->prevpool = prev;
+			prev->nextpool = next;
+			/* Link to freepools.  This is a singly-linked list,
+			 * and pool->prevpool isn't used there.
+			 */
+			pool->nextpool = freepools;
+			freepools = pool;
 			UNLOCK();
 			return;
 		}
 		/*
-		 * Pool is now empty, unlink from used pools
-		 */
-		next = pool->nextpool;
-		prev = pool->prevpool;
-		next->prevpool = prev;
-		prev->nextpool = next;
-		/*
-		 * Frontlink to free pools
-		 * This ensures that previously freed pools will be allocated
-		 * later (being not referenced, they are perhaps paged out).
+		 * Pool was full, so doesn't currently live in any list:
+		 * link it to the front of the appropriate usedpools[] list.
+		 * This mimics LRU pool usage for new allocations and
+		 * targets optimal filling when several pools contain
+		 * blocks of the same size class.
 		 */
-		pool->nextpool = freepools;
-		freepools = pool;
+		assert(pool->ref.count == pool->capacity); /* else not full */
+		--pool->ref.count;
+		assert(pool->ref.count > 0);	/* else the pool is empty */
+		size = pool->szidx;
+		next = usedpools[size + size];
+		prev = next->prevpool;
+		/* insert pool before next:   prev <-> pool <-> next */
+		pool->nextpool = next;
+		pool->prevpool = prev;
+		next->prevpool = pool;
+		prev->nextpool = pool;
 		UNLOCK();
 		return;
 	}
 
-	/* We did not allocate this address. */
+	/* We didn't allocate this address. */
 	INCTHEIRS;
 	PyMem_FREE(p);
 }