From d9fabbcc5beff63ef8eb29d36dee0ffae55b67b6 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Wed, 10 Aug 2016 11:50:12 +0000
Subject: [PATCH] Fix pcache1TruncateUnsafe() run faster for the case where
 iLimit is very close to iMaxKey.

FossilOrigin-Name: b07a26df06a2ffb946ff8a1cc7f43eaf701a94b5
---
 manifest      | 13 +++++++------
 manifest.uuid |  2 +-
 src/pcache1.c | 34 +++++++++++++++++++++++++++-------
 3 files changed, 35 insertions(+), 14 deletions(-)

diff --git a/manifest b/manifest
index 679af7eda6..316b95fb86 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Performance\soptimization\sin\sthe\syy_find_shift_action()\sroutine\sof\sthe\nLemon-generated\sparser.
-D 2016-08-10T01:43:30.837
+C Fix\spcache1TruncateUnsafe()\srun\sfaster\sfor\sthe\scase\swhere\siLimit\sis\nvery\sclose\sto\siMaxKey.
+D 2016-08-10T11:50:12.345
 F Makefile.in cfd8fb987cd7a6af046daa87daa146d5aad0e088
 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434
 F Makefile.msc d66d0395c38571aab3804f8db0fa20707ae4609a
@@ -376,7 +376,7 @@ F src/pager.h 966d2769e76ae347c8a32c4165faf6e6cb64546d
 F src/parse.y 99b676e6fc2f4e331ab93e76b3987cffdbd28efa
 F src/pcache.c 5583c8ade4b05075a60ba953ef471d1c1a9c05df
 F src/pcache.h 2cedcd8407eb23017d92790b112186886e179490
-F src/pcache1.c 7f51d2b541aab57596adf62db2c4bb025d34f04d
+F src/pcache1.c dc8a6052e5136d6b5e6afe51f37485145646f5ab
 F src/pragma.c c8b499756658cb8b82cfdbb5845c22cf11f297aa
 F src/pragma.h 64c78a648751b9f4f297276c4eb7507b14b4628c
 F src/prepare.c 22df6171aec1d86904ed2ad30c2348a5748aa04e
@@ -1510,7 +1510,8 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 9a5a4f6e3bc265fecf79a7f63d14abbf239da636
-R fb6cb5f47404a4ca8ae3044e53622029
+P ba6663beefcc8060e6f3be6ab37c13fdbb08b7de
+Q +9ab53605d562a926c5620cba9dc96a3b812a432f
+R 045183d4dc58e68027bf139105903731
 U drh
-Z 1ed24d5681cad4ee5c357b2d89914ae1
+Z 7fb6739dae3ac730e38720df5d5c1de9
diff --git a/manifest.uuid b/manifest.uuid
index f5266c615d..5bb9a78a83 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-ba6663beefcc8060e6f3be6ab37c13fdbb08b7de
\ No newline at end of file
+b07a26df06a2ffb946ff8a1cc7f43eaf701a94b5
\ No newline at end of file
diff --git a/src/pcache1.c b/src/pcache1.c
index 5fe963ad05..1af1ef5bb7 100644
--- a/src/pcache1.c
+++ b/src/pcache1.c
@@ -632,12 +632,30 @@ static void pcache1TruncateUnsafe(
   PCache1 *pCache,             /* The cache to truncate */
   unsigned int iLimit          /* Drop pages with this pgno or larger */
 ){
-  TESTONLY( unsigned int nPage = 0; )  /* To assert pCache->nPage is correct */
-  unsigned int h;
+  TESTONLY( int nPage = 0; )  /* To assert pCache->nPage is correct */
+  unsigned int h, iStop;
   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
-  for(h=0; h<pCache->nHash; h++){
-    PgHdr1 **pp = &pCache->apHash[h]; 
+  assert( pCache->iMaxKey >= iLimit );
+  assert( pCache->nHash > 0 );
+  if( pCache->iMaxKey - iLimit < pCache->nHash/2 ){
+    /* If we are just shaving the last few pages off the end of the
+    ** cache, then there is no point in scanning the entire hash table.
+    ** Only scan those hash slots that might contain pages that need to
+    ** be removed. */
+    iStop = iLimit % pCache->nHash;
+    h = pCache->iMaxKey % pCache->nHash;
+    TESTONLY( nPage = -10; )  /* Disable the pCache->nPage validity check */
+  }else{
+    /* This is the general case where many pages are being removed.
+    ** It is necessary to scan the entire hash table */
+    iStop = 0;
+    h = pCache->nHash - 1;
+  }
+  for(;;){
+    PgHdr1 **pp;
     PgHdr1 *pPage;
+    assert( h<pCache->nHash );
+    pp = &pCache->apHash[h]; 
     while( (pPage = *pp)!=0 ){
       if( pPage->iKey>=iLimit ){
         pCache->nPage--;
@@ -646,11 +664,13 @@ static void pcache1TruncateUnsafe(
         pcache1FreePage(pPage);
       }else{
         pp = &pPage->pNext;
-        TESTONLY( nPage++; )
+        TESTONLY( if( nPage>=0 ) nPage++; )
       }
     }
+    if( h==iStop ) break;
+    h = h ? h-1 : pCache->nHash - 1;
   }
-  assert( pCache->nPage==nPage );
+  assert( nPage<0 || pCache->nPage==(unsigned)nPage );
 }
 
 /******************************************************************************/
@@ -1127,7 +1147,7 @@ static void pcache1Destroy(sqlite3_pcache *p){
   PGroup *pGroup = pCache->pGroup;
   assert( pCache->bPurgeable || (pCache->nMax==0 && pCache->nMin==0) );
   pcache1EnterMutex(pGroup);
-  pcache1TruncateUnsafe(pCache, 0);
+  if( pCache->nPage ) pcache1TruncateUnsafe(pCache, 0);
   assert( pGroup->nMaxPage >= pCache->nMax );
   pGroup->nMaxPage -= pCache->nMax;
   assert( pGroup->nMinPage >= pCache->nMin );
-- 
2.47.2