[sqlite] optimization: slight faster linked list merge sorter

[Quan Yong Zhai]

Dear SQLIte developers,

Here is a small patch for the linked-list merge sorter in SQLite
to sort N items, 
It will save  about 2*N CPU instructions  by eliminate  unnecessary null 
pointer check,
Regards

make test passed.
fossil diff

Index: src/pcache.c
==================================================================
--- src/pcache.c
+++ src/pcache.c
@@ -690,21 +690,22 @@
** Do not both fixing the pDirtyPrev pointers.
*/
static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
   PgHdr result, *pTail;
   pTail = &result;
-  while( pA && pB ){
+  assert( pA && pB );
+  do{
     if( pA->pgno<pB->pgno ){
       pTail->pDirty = pA;
       pTail = pA;
       pA = pA->pDirty;
     }else{
       pTail->pDirty = pB;
       pTail = pB;
       pB = pB->pDirty;
     }
-  }
+  }while( pA && pB );
   if( pA ){
     pTail->pDirty = pA;
   }else if( pB ){
     pTail->pDirty = pB;
   }else{
@@ -748,11 +749,14 @@
       a[i] = pcacheMergeDirtyList(a[i], p);
     }
   }
   p = a[0];
   for(i=1; i<N_SORT_BUCKET; i++){
-    p = pcacheMergeDirtyList(p, a[i]);
+    if( !p )
+      p = a[i];
+    else if ( a[i] )
+      p = pcacheMergeDirtyList(p, a[i]);
   }
   return p;
}

 /*

Index: src/rowset.c
==================================================================
--- src/rowset.c
+++ src/rowset.c
@@ -240,11 +240,12 @@
){
   struct RowSetEntry head;
   struct RowSetEntry *pTail;

   pTail = &head;
-  while( pA && pB ){
+  assert( pA && pB );
+  do{
     assert( pA->pRight==0 || pA->v<=pA->pRight->v );
     assert( pB->pRight==0 || pB->v<=pB->pRight->v );
     if( pA->v<pB->v ){
       pTail->pRight = pA;
       pA = pA->pRight;
@@ -254,11 +255,11 @@
       pB = pB->pRight;
       pTail = pTail->pRight;
     }else{
       pA = pA->pRight;
     }
-  }
+  }while( pA && pB );
   if( pA ){
     assert( pA->pRight==0 || pA->v<=pA->pRight->v );
     pTail->pRight = pA;
   }else{
     assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
@@ -286,11 +287,14 @@
     aBucket[i] = pIn;
     pIn = pNext;
   }
   pIn = 0;
   for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
-    pIn = rowSetEntryMerge(pIn, aBucket[i]);
+    if( !pIn )
+      pIn = aBucket[i];
+    else if ( aBucket[i] )
+      pIn = rowSetEntryMerge(pIn, aBucket[i]);
   }
   return pIn;
}



Index: src/vdbesort.c
==================================================================
--- src/vdbesort.c
+++ src/vdbesort.c
@@ -1352,11 +1352,12 @@
){
   SorterRecord *pFinal = 0;
   SorterRecord **pp = &pFinal;
   int bCached = 0;

-  while( p1 && p2 ){
+  assert( p1 && p2 );
+  do{
     int res;
     res = pTask->xCompare(
         pTask, &bCached, SRVAL(p1), p1->nVal, SRVAL(p2), p2->nVal
     );

@@ -1368,11 +1369,11 @@
       *pp = p2;
       pp = &p2->u.pNext;
       p2 = p2->u.pNext;
       bCached = 0;
     }
-  }
+  }while( p1 && p2 );
   *pp = p1 ? p1 : p2;
   *ppOut = pFinal;
}

 /*
@@ -1432,11 +1433,14 @@
     p = pNext;
   }

   p = 0;
   for(i=0; i<64; i++){
-    vdbeSorterMerge(pTask, p, aSlot[i], &p);
+    if( !p )
+      p = aSlot[i];
+    else if( aSlot[i] )
+      vdbeSorterMerge(pTask, p, aSlot[i], &p);
   }
   pList->pList = p;

   sqlite3_free(aSlot);
   assert( pTask->pUnpacked->errCode==SQLITE_OK