From 9948e95674a267ab8175812745e2bdad93bbb877 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Sat, 23 Nov 2013 22:45:12 +0000
Subject: [PATCH] A much simpler fix is to simply change MEMSYS5 so that it
 takes any free block of the appropriate size (the first on the list of free
 blocks) rather than searching for the one with the smallest address.  This is
 also faster than using the min-heap algorithm.  Need to research to verify
 that the allocator still satisfies the Robson proof, however.

FossilOrigin-Name: 8191b512122c13d7fa61d8e5487652f13ec172f7
---
 manifest      | 15 +++++++++------
 manifest.uuid |  2 +-
 src/mem5.c    | 16 ++++++++++------
 3 files changed, 20 insertions(+), 13 deletions(-)

diff --git a/manifest b/manifest
index 47369b1136..3c26785d5b 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Add\snewlines\sat\sthe\send\sof\ssome\serror\smessages\sin\sspeedtest1.
-D 2013-11-23T21:29:07.429
+C A\smuch\ssimpler\sfix\sis\sto\ssimply\schange\sMEMSYS5\sso\sthat\sit\stakes\sany\sfree\nblock\sof\sthe\sappropriate\ssize\s(the\sfirst\son\sthe\slist\sof\sfree\sblocks)\srather\nthan\ssearching\sfor\sthe\sone\swith\sthe\ssmallest\saddress.\s\sThis\sis\salso\sfaster\nthan\susing\sthe\smin-heap\salgorithm.\s\sNeed\sto\sresearch\sto\sverify\sthat\sthe\nallocator\sstill\ssatisfies\sthe\sRobson\sproof,\showever.
+D 2013-11-23T22:45:12.906
 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f
 F Makefile.in e1a9b4258bbde53f5636f4e238c65b7e11459e2b
 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23
@@ -194,7 +194,7 @@ F src/mem0.c 6a55ebe57c46ca1a7d98da93aaa07f99f1059645
 F src/mem1.c c0c990fcaddff810ea277b4fb5d9138603dd5d4b
 F src/mem2.c dce31758da87ec2cfa52ba4c5df1aed6e07d8e8f
 F src/mem3.c 61c9d47b792908c532ca3a62b999cf21795c6534
-F src/mem5.c 0025308a93838022bd5696cf9627ff4e40b19918
+F src/mem5.c 77a525e6a4f623d1008f08a0a4050789e710d71e
 F src/memjournal.c 0683aac6cab6ec2b5374c0db37c0deb2436a3785
 F src/mutex.c d3b66a569368015e0fcb1ac15f81c119f504d3bc
 F src/mutex.h 5bc526e19dccc412b7ff04642f6fdad3fdfdabea
@@ -1142,7 +1142,10 @@ F tool/vdbe-compress.tcl f12c884766bd14277f4fcedcae07078011717381
 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4
 F tool/warnings.sh d1a6de74685f360ab718efda6265994b99bbea01
 F tool/win/sqlite.vsix 030f3eeaf2cb811a3692ab9c14d021a75ce41fff
-P 659f1a98ae698d062269f8fdac84f733a460f5de
-R 0d67753f14410df579db17c64fb3786e
+P 6b98f0af7a6522873245d30598d7c79b8aeb9fa0
+R e84ccd96a2888616670da3469dc947a5
+T *branch * memsys5-performance
+T *sym-memsys5-performance *
+T -sym-trunk *
 U drh
-Z 430a11d968198395db1db68b7169dc35
+Z 93975e1a1bc297cea7284502171ff001
diff --git a/manifest.uuid b/manifest.uuid
index fe94011755..a79b866a19 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-6b98f0af7a6522873245d30598d7c79b8aeb9fa0
\ No newline at end of file
+8191b512122c13d7fa61d8e5487652f13ec172f7
\ No newline at end of file
diff --git a/src/mem5.c b/src/mem5.c
index 5f99ebf43d..35719031f8 100644
--- a/src/mem5.c
+++ b/src/mem5.c
@@ -214,16 +214,20 @@ static int memsys5Size(void *p){
 ** entry and return its index. 
 */
 static int memsys5UnlinkFirst(int iLogsize){
-  int i;
   int iFirst;
 
   assert( iLogsize>=0 && iLogsize<=LOGMAX );
-  i = iFirst = mem5.aiFreelist[iLogsize];
-  assert( iFirst>=0 );
-  while( i>0 ){
-    if( i<iFirst ) iFirst = i;
-    i = MEM5LINK(i)->next;
+  iFirst = mem5.aiFreelist[iLogsize];
+#if 0
+  {
+    int i = iFirst;
+    assert( iFirst>=0 );
+    while( i>0 ){
+      if( i<iFirst ) iFirst = i;
+      i = MEM5LINK(i)->next;
+    }
   }
+#endif
   memsys5Unlink(iFirst, iLogsize);
   return iFirst;
 }
-- 
2.39.5