From 9cfefbd2c31206ec410434c299a3a0b176b0d714 Mon Sep 17 00:00:00 2001
From: drh <>
Date: Fri, 7 Apr 2023 11:55:58 +0000
Subject: [PATCH] Try to use a heap to make coalescence of adjacent free slots
 faster when freeing space on a btree page.  Turns out that the overhead of
 managing the heap overwhelms any performance gain and the result is slower.

FossilOrigin-Name: 5d7e833f25051000d24797bc3875aaaed8f2bdb3b9aa1ce3f4f466a7dcd923b8
---
 manifest      | 18 ++++++-------
 manifest.uuid |  2 +-
 src/btree.c   | 73 +++++++++++++++++++++++++++++----------------------
 3 files changed, 52 insertions(+), 41 deletions(-)

diff --git a/manifest b/manifest
index 7b23595ea4..a015c9e077 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Increase\sthe\ssize\sof\sthe\scache\sof\sfree\sblocks\sinside\sof\spageFreeArray()\sto\nreduce\sthe\snumber\sof\scalls\sto\sfreeSpace().
-D 2023-04-06T20:14:10.861
+C Try\sto\suse\sa\sheap\sto\smake\scoalescence\sof\sadjacent\sfree\sslots\sfaster\swhen\nfreeing\sspace\son\sa\sbtree\spage.\s\sTurns\sout\sthat\sthe\soverhead\sof\smanaging\nthe\sheap\soverwhelms\sany\sperformance\sgain\sand\sthe\sresult\sis\sslower.
+D 2023-04-07T11:55:58.282
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724
@@ -564,7 +564,7 @@ F src/auth.c f4fa91b6a90bbc8e0d0f738aa284551739c9543a367071f55574681e0f24f8cf
 F src/backup.c a2891172438e385fdbe97c11c9745676bec54f518d4447090af97189fd8e52d7
 F src/bitvec.c 7c849aac407230278445cb069bebc5f89bf2ddd87c5ed9459b070a9175707b3d
 F src/btmutex.c 6ffb0a22c19e2f9110be0964d0731d2ef1c67b5f7fabfbaeb7b9dabc4b7740ca
-F src/btree.c 1a5f31d548a68d2bd537919d8afa176540c3ea70787fe10d5873beb00f9db615
+F src/btree.c 8bd2f2b5e41d9ebb6e9f828f597e824af41c3a48315543027d741fbbc1fa89b0
 F src/btree.h aa354b9bad4120af71e214666b35132712b8f2ec11869cb2315c52c81fad45cc
 F src/btreeInt.h a3268a60cbc91f578001f44ba40aae9c1b8aecbb0d2c095dd7fc54b0872ea4b8
 F src/build.c 8357d6ca9a8c9afc297c431df28bc2af407b47f3ef2311875276c944b30c4d54
@@ -2052,11 +2052,11 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 56ea2c2fe6108d39833ac40957afab59ade01a216639d5bafdeeca53bbf4cd67
-R f4ea0d3a1a9bcf702848933fabd592b4
-T *branch * btree-freespace-opt
-T *sym-btree-freespace-opt *
-T -sym-trunk *
+P 27c59f1ea789f3ff245f23e79ded5cd71c48e3a51ffbb8c220b51101a4e69fd7
+R c1ff538937e36abd2cf16de04be70f7b
+T *branch * deadend
+T *sym-deadend *
+T -sym-btree-freespace-opt *
 U drh
-Z a279ebfc98f243d3f64ca427ad2184cf
+Z 10cff07ea83d09e599ad019612e5aecd
 # Remove this line to create a well-formed Fossil manifest.
diff --git a/manifest.uuid b/manifest.uuid
index 38cf4ef4af..f0864216f7 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-27c59f1ea789f3ff245f23e79ded5cd71c48e3a51ffbb8c220b51101a4e69fd7
\ No newline at end of file
+5d7e833f25051000d24797bc3875aaaed8f2bdb3b9aa1ce3f4f466a7dcd923b8
\ No newline at end of file
diff --git a/src/btree.c b/src/btree.c
index 86ff2b466f..eb4293960e 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -7033,6 +7033,7 @@ static int fillInCell(
   return SQLITE_OK;
 }
 
+
 /*
 ** Remove the i-th cell from pPage.  This routine effects pPage only.
 ** The cell content is not freed or deallocated.  It is assumed that
@@ -7477,6 +7478,38 @@ static int pageInsertArray(
   return 0;
 }
 
+static void btreeHeapInsert(u32 *aHeap, u32 x);
+static int btreeHeapPull(u32 *aHeap, u32 *pOut);
+
+/*
+** Add all of the cells on aHep to the freelist for a page.
+*/
+static void btreeFreeCellsOnHeap(MemPage *pPg, u32 *aHeap){
+  u32 x;
+  int iOfst;
+  int iSize;
+
+  assert( aHeap[0] );
+  btreeHeapPull(aHeap, &x);
+  iSize = x & 0xffff;
+  iOfst = x>>16;
+  while( aHeap[0] ){
+    int iNxOfst;
+    int iNxSize;
+    btreeHeapPull(aHeap, &x);
+    iNxSize = x & 0xffff;
+    iNxOfst = x>>16;
+    if( iSize+iOfst==iNxOfst ){
+      iSize += iNxSize;
+    }else{
+      freeSpace(pPg, iOfst, iSize);
+      iOfst = iNxOfst;
+      iSize = iNxSize;
+    }
+  }
+  freeSpace(pPg, iOfst, iSize);
+}
+
 /*
 ** The pCArray object contains pointers to b-tree cells and their sizes.
 **
@@ -7496,50 +7529,28 @@ static int pageFreeArray(
   u8 * const pEnd = &aData[pPg->pBt->usableSize];
   u8 * const pStart = &aData[pPg->hdrOffset + 8 + pPg->childPtrSize];
   int nRet = 0;
-  int i, j;
+  int i;
   int iEnd = iFirst + nCell;
-  int nFree = 0;
-  int aOfst[10];
-  int aAfter[10];
+  u32 aHeap[100];
 
+  aHeap[0] = 0;
   for(i=iFirst; i<iEnd; i++){
     u8 *pCell = pCArray->apCell[i];
     if( SQLITE_WITHIN(pCell, pStart, pEnd) ){
-      int sz;
-      int iAfter;
-      int iOfst;
+      u16 sz;
+      u16 iOfst;
+
       /* No need to use cachedCellSize() here.  The sizes of all cells that
       ** are to be freed have already been computing while deciding which
       ** cells need freeing */
       sz = pCArray->szCell[i];  assert( sz>0 );
       iOfst = (u16)(pCell - aData);
-      iAfter = iOfst+sz;
-      for(j=0; j<nFree; j++){
-        if( aOfst[j]==iAfter ){
-          aOfst[j] = iOfst;
-          break;
-        }else if( aAfter[j]==iOfst ){
-          aAfter[j] = iAfter;
-          break;
-        }
-      }
-      if( j>=nFree ){
-        if( nFree>=sizeof(aOfst)/sizeof(aOfst[0]) ){
-          for(j=0; j<nFree; j++){
-            freeSpace(pPg, aOfst[j], aAfter[j]-aOfst[j]);
-          }
-          nFree = 0;
-        }
-        aOfst[nFree] = iOfst;
-        aAfter[nFree] = iAfter;
-        nFree++;
-      }
+      btreeHeapInsert(aHeap, (iOfst<<16)|sz);
+      if( aHeap[0]>=90 ) btreeFreeCellsOnHeap(pPg, aHeap);
       nRet++;
     }
   }
-  for(j=0; j<nFree; j++){
-    freeSpace(pPg, aOfst[j], aAfter[j]-aOfst[j]);
-  }
+  if( aHeap[0] ) btreeFreeCellsOnHeap(pPg, aHeap);
   return nRet;
 }
 
-- 
2.39.5