From 6971952c650cdf1d4e76e63fdb89165bac5c1af0 Mon Sep 17 00:00:00 2001 From: dan Date: Thu, 27 Mar 2014 19:25:02 +0000 Subject: [PATCH] Instead of allocating a single large buffer at the beginning of each sort operation, start with a small buffer and extend it using realloc() as required. FossilOrigin-Name: 81987c8ceb64f051528a6ca42673821d9ab7c0ff --- manifest | 12 ++-- manifest.uuid | 2 +- src/vdbesort.c | 185 +++++++++++++++++++++++++++++++++---------------- 3 files changed, 131 insertions(+), 68 deletions(-) diff --git a/manifest b/manifest index dc6ca295c7..986addf1fe 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Use\sxFetch()\sto\saccess\stemporary\sfiles\sin\svdbesort.c.\sUse\sa\ssingle\slarge\sallocation\sinstead\sof\smany\ssmall\sallocations\swhen\saccumulating\srecords\sin\svdbesort.c.\sThis\sis\san\sinterim\scommit\s-\sit\sallocates\sa\sbuffer\sthe\ssize\sof\sthe\spage-cache\severy\stime\sdata\sis\ssorted. -D 2014-03-27T17:23:41.403 +C Instead\sof\sallocating\sa\ssingle\slarge\sbuffer\sat\sthe\sbeginning\sof\seach\ssort\soperation,\sstart\swith\sa\ssmall\sbuffer\sand\sextend\sit\susing\srealloc()\sas\srequired. +D 2014-03-27T19:25:02.222 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 2ef13430cd359f7b361bb863504e227b25cc7f81 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -285,7 +285,7 @@ F src/vdbeapi.c 0ed6053f947edd0b30f64ce5aeb811872a3450a4 F src/vdbeaux.c f81ef920dcf76aceaa1ce77081e9fc5d7a0993dd F src/vdbeblob.c 15377abfb59251bccedd5a9c7d014a895f0c04aa F src/vdbemem.c 6fc77594c60f6155404f3f8d71bf36d1fdeb4447 -F src/vdbesort.c d46f384af1997a4441ef9c65759181954efc89cf +F src/vdbesort.c 08d5e1ee199599d9571942f0560f84963c7a1a9b F src/vdbetrace.c 6f52bc0c51e144b7efdcfb2a8f771167a8816767 F src/vtab.c 21b932841e51ebd7d075e2d0ad1415dce8d2d5fd F src/wal.c 76e7fc6de229bea8b30bb2539110f03a494dc3a8 @@ -1159,7 +1159,7 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh d1a6de74685f360ab718efda6265994b99bbea01 F tool/win/sqlite.vsix 030f3eeaf2cb811a3692ab9c14d021a75ce41fff -P 0b35346c32dba14963c85ec178f2b46aa2bbf6dc -R 8f417577dbf4ab5b5ce5a802872c70f0 +P f4ac1bf28c4ba395ccab8f1c9df72614a61095a7 +R 5fefa7763a5f0d580046ba5219de21a5 U dan -Z 2c1a0a402e8f93dd4df9cfe6e1bca5e6 +Z 8f7301353335dd4530b24cac1ad9c37a diff --git a/manifest.uuid b/manifest.uuid index 853b60d3d3..cf2496b0b2 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -f4ac1bf28c4ba395ccab8f1c9df72614a61095a7 \ No newline at end of file +81987c8ceb64f051528a6ca42673821d9ab7c0ff \ No newline at end of file diff --git a/src/vdbesort.c b/src/vdbesort.c index 2a15168fd2..f229b1f18b 100644 --- a/src/vdbesort.c +++ b/src/vdbesort.c @@ -107,6 +107,7 @@ struct VdbeSorter { UnpackedRecord *pUnpacked; /* Used to unpack keys */ u8* aMemory; /* Block to allocate records from */ int iMemory; /* Offset of free space in aMemory */ + int nMemory; /* Current size of allocation at aMemory */ }; /* @@ -144,15 +145,37 @@ struct FileWriter { /* ** A structure to store a single record. All in-memory records are connected -** together into a linked list headed at VdbeSorter.pRecord using the -** SorterRecord.pNext pointer. +** together into a linked list headed at VdbeSorter.pRecord. +** +** How the linked list is connected depends on how memory is being managed +** by this module. If using a separate allocation for each in-memory record +** (VdbeSorter.aMemory==0), then the list is always connected using the +** SorterRecord.u.pNext pointers. +** +** Or, if using the single large allocation method (VdbeSorter.aMemory!=0), +** then while records are being accumulated the list is linked using the +** SorterRecord.u.iNext offset. This is because the aMemory[] array may +** be sqlite3Realloc()ed while records are being accumulated. Once the VM +** has finished passing records to the sorter, or when the in-memory buffer +** is full, the list is sorted. As part of the sorting process, it is +** converted to use the SorterRecord.u.pNext pointers. See function +** vdbeSorterSort() for details. */ struct SorterRecord { - void *pVal; int nVal; - SorterRecord *pNext; + union { + SorterRecord *pNext; /* Pointer to next record in list */ + int iNext; /* Offset within aMemory of next record */ + } u; }; +/* Return a pointer to the buffer containing the record data for SorterRecord +** object p. Should be used as if: +** +** void *SRVAL(SorterRecord *p) { return (void*)&p[1]; } +*/ +#define SRVAL(p) ((void*)((SorterRecord*)(p) + 1)) + /* Minimum allowable value for the VdbeSorter.nWorking variable */ #define SORTER_MIN_WORKING 10 @@ -513,9 +536,15 @@ int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ if( mxCachemxPmaSize = mxCache * pgsz; - pSorter->aMemory = (u8*)sqlite3DbMallocRaw(db, pSorter->mxPmaSize); - assert( pSorter->iMemory==0 ); - if( !pSorter->aMemory ) return SQLITE_NOMEM; + /* If the application is using memsys3 or memsys5, use a separate + ** allocation for each sort-key in memory. Otherwise, use a single big + ** allocation at pSorter->aMemory for all sort-keys. */ + if( sqlite3GlobalConfig.pHeap==0 ){ + assert( pSorter->iMemory==0 ); + pSorter->nMemory = pgsz; + pSorter->aMemory = (u8*)sqlite3Malloc(pSorter->nMemory); + if( !pSorter->aMemory ) return SQLITE_NOMEM; + } } return SQLITE_OK; @@ -528,7 +557,7 @@ static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){ SorterRecord *p; SorterRecord *pNext; for(p=pRecord; p; p=pNext){ - pNext = p->pNext; + pNext = p->u.pNext; sqlite3DbFree(db, p); } } @@ -611,22 +640,22 @@ static void vdbeSorterMerge( ){ SorterRecord *pFinal = 0; SorterRecord **pp = &pFinal; - void *pVal2 = p2 ? p2->pVal : 0; + void *pVal2 = p2 ? SRVAL(p2) : 0; while( p1 && p2 ){ int res; - vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res); + vdbeSorterCompare(pCsr, 0, SRVAL(p1), p1->nVal, pVal2, p2->nVal, &res); if( res<=0 ){ *pp = p1; - pp = &p1->pNext; - p1 = p1->pNext; + pp = &p1->u.pNext; + p1 = p1->u.pNext; pVal2 = 0; }else{ *pp = p2; - pp = &p2->pNext; - p2 = p2->pNext; + pp = &p2->u.pNext; + p2 = p2->u.pNext; if( p2==0 ) break; - pVal2 = p2->pVal; + pVal2 = SRVAL(p2); } } *pp = p1 ? p1 : p2; @@ -656,8 +685,18 @@ static int vdbeSorterSort(const VdbeCursor *pCsr){ p = pSorter->pRecord; while( p ){ - SorterRecord *pNext = p->pNext; - p->pNext = 0; + SorterRecord *pNext; + if( pSorter->aMemory ){ + assert( p->u.iNextnMemory ); + if( (u8*)p==pSorter->aMemory ){ + pNext = 0; + }else{ + pNext = (SorterRecord*)&pSorter->aMemory[p->u.iNext]; + } + }else{ + pNext = p->u.pNext; + } + p->u.pNext = 0; for(i=0; aSlot[i]; i++){ vdbeSorterMerge(pCsr, p, aSlot[i], &p); aSlot[i] = 0; @@ -835,9 +874,9 @@ static int vdbeSorterListToPMA(sqlite3 *db, const VdbeCursor *pCsr){ pSorter->nPMA++; fileWriterWriteVarint(&writer, pSorter->nInMemory); for(p=pSorter->pRecord; p; p=pNext){ - pNext = p->pNext; + pNext = p->u.pNext; fileWriterWriteVarint(&writer, p->nVal); - fileWriterWrite(&writer, p->pVal, p->nVal); + fileWriterWrite(&writer, SRVAL(p), p->nVal); if( pSorter->aMemory==0 ) sqlite3DbFree(db, p); } pSorter->pRecord = p; @@ -858,39 +897,24 @@ int sqlite3VdbeSorterWrite( Mem *pVal /* Memory cell containing record */ ){ VdbeSorter *pSorter = pCsr->pSorter; - SorterRecord sRecord; /* Used for aMemory overflow record */ int rc = SQLITE_OK; /* Return Code */ SorterRecord *pNew; /* New list element */ - assert( pSorter ); - pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n; - - if( pSorter->aMemory ){ - int nReq = sizeof(SorterRecord) + pVal->n; - if( (pSorter->iMemory+nReq) > pSorter->mxPmaSize ){ - pNew = &sRecord; - pNew->pVal = pVal->z; - }else{ - pNew = &pSorter->aMemory[pSorter->iMemory]; - pSorter->iMemory += ROUND8(nReq); - } - }else{ - pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n+sizeof(SorterRecord)); - if( pNew==0 ){ - return SQLITE_NOMEM; - } - } + int bFlush; /* True to flush contents of memory to PMA */ + int nReq; /* Bytes of memory required */ + int nPMA; /* Bytes of PMA space required */ - if( pNew!=&sRecord ){ - pNew->pVal = (void*)&pNew[1]; - memcpy(pNew->pVal, pVal->z, pVal->n); - } - pNew->nVal = pVal->n; - pNew->pNext = pSorter->pRecord; - pSorter->pRecord = pNew; + assert( pSorter ); - /* See if the contents of the sorter should now be written out. They - ** are written out when either of the following are true: + /* Figure out whether or not the current contents of memory should be + ** flushed to a PMA before continuing. If so, do so. + ** + ** If using the single large allocation mode (pSorter->aMemory!=0), then + ** flush the contents of memory to a new PMA if (a) at least one value is + ** already in memory and (b) the new value will not fit in memory. + ** + ** Or, if using separate allocations for each record, flush the contents + ** of memory to a PMA if either of the following are true: ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * cache-size), or @@ -898,24 +922,63 @@ int sqlite3VdbeSorterWrite( ** * The total memory allocated for the in-memory list is greater ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true. */ - if( pSorter->mxPmaSize>0 ){ - if( (pNew==&sRecord) || (pSorter->aMemory==0 && ( + nReq = pVal->n + sizeof(SorterRecord); + nPMA = pVal->n + sqlite3VarintLen(pVal->n); + if( pSorter->aMemory ){ + bFlush = pSorter->iMemory && (pSorter->iMemory+nReq) > pSorter->mxPmaSize; + }else{ + bFlush = ( (pSorter->nInMemory > pSorter->mxPmaSize) || (pSorter->nInMemory > pSorter->mnPmaSize && sqlite3HeapNearlyFull()) - ))){ + ); + } + if( bFlush ){ #ifdef SQLITE_DEBUG - i64 nExpect = pSorter->iWriteOff - + sqlite3VarintLen(pSorter->nInMemory) - + pSorter->nInMemory; + i64 nExpect = pSorter->iWriteOff + + sqlite3VarintLen(pSorter->nInMemory) + + pSorter->nInMemory; #endif - rc = vdbeSorterListToPMA(db, pCsr); - pSorter->nInMemory = 0; - pSorter->iMemory = 0; - assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) ); - assert( rc!=SQLITE_OK || pSorter->pRecord==0 ); + rc = vdbeSorterListToPMA(db, pCsr); + pSorter->nInMemory = 0; + pSorter->iMemory = 0; + assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) ); + assert( rc!=SQLITE_OK || pSorter->pRecord==0 ); + } + + pSorter->nInMemory += nPMA; + + if( pSorter->aMemory ){ + int nMin = pSorter->iMemory + nReq; + + if( nMin>pSorter->nMemory ){ + u8 *aNew; + int nNew = pSorter->nMemory * 2; + while( nNew < nMin ) nNew = nNew*2; + if( nNew > pSorter->mxPmaSize ) nNew = pSorter->mxPmaSize; + if( nNew < nMin ) nNew = nMin; + + aNew = sqlite3Realloc(pSorter->aMemory, nNew); + if( !aNew ) return SQLITE_NOMEM; + pSorter->pRecord = aNew + ((u8*)pSorter->pRecord - pSorter->aMemory); + pSorter->aMemory = aNew; + pSorter->nMemory = nNew; + } + + pNew = (SorterRecord*)&pSorter->aMemory[pSorter->iMemory]; + pSorter->iMemory += ROUND8(nReq); + pNew->u.iNext = (u8*)(pSorter->pRecord) - pSorter->aMemory; + }else{ + pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n+sizeof(SorterRecord)); + if( pNew==0 ){ + return SQLITE_NOMEM; } + pNew->u.pNext = pSorter->pRecord; } + memcpy(SRVAL(pNew), pVal->z, pVal->n); + pNew->nVal = pVal->n; + pSorter->pRecord = pNew; + return rc; } @@ -1127,8 +1190,8 @@ int sqlite3VdbeSorterNext(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){ } }else{ SorterRecord *pFree = pSorter->pRecord; - pSorter->pRecord = pFree->pNext; - pFree->pNext = 0; + pSorter->pRecord = pFree->u.pNext; + pFree->u.pNext = 0; if( pSorter->aMemory==0 ){ vdbeSorterRecordFree(db, pFree); } @@ -1154,7 +1217,7 @@ static void *vdbeSorterRowkey( pKey = pIter->aKey; }else{ *pnKey = pSorter->pRecord->nVal; - pKey = pSorter->pRecord->pVal; + pKey = SRVAL(pSorter->pRecord); } return pKey; } -- 2.47.2