From 7c4185e2f13454aac730956f685c0e4c5779b206 Mon Sep 17 00:00:00 2001 From: danielk1977 Date: Fri, 25 Jul 2008 16:07:00 +0000 Subject: [PATCH] Further performance improvements to mem6.c. (CVS 5482) FossilOrigin-Name: 4528f7b1cce2d009f1bf32bfb8eeaf3ce5531f41 --- manifest | 14 +++--- manifest.uuid | 2 +- src/mem6.c | 126 +++++++++++++++++++++++++++----------------------- 3 files changed, 75 insertions(+), 67 deletions(-) diff --git a/manifest b/manifest index 44df1dd219..9870816a60 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Add\sthe\scapability\sto\strack\sthe\smaximum\sdepth\sof\sthe\sLALR(1)\sparser\sstack\nso\sthat\scritical\sapplications\scan\scheck\sto\ssee\sif\sthey\sare\sgetting\sclose\nto\slimits.\s(CVS\s5481) -D 2008-07-25T15:39:04 +C Further\sperformance\simprovements\sto\smem6.c.\s(CVS\s5482) +D 2008-07-25T16:07:01 F Makefile.arm-wince-mingw32ce-gcc fcd5e9cd67fe88836360bb4f9ef4cb7f8e2fb5a0 F Makefile.in d677b8dbc24fd815043e87e9350f8d296ab40f0d F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654 @@ -123,7 +123,7 @@ F src/mem2.c 87381b143530cc377592e868bd548e881c2498a3 F src/mem3.c c73e935d0b900abc51d5fa45f880937b062f4a9f F src/mem4.c 6703adb1717b26d9d70a1c2586b4b7b7ffee7909 F src/mem5.c 0b0ba1c2a02d86eb812dea6debacee841e3856f7 -F src/mem6.c c3987f7f63327338e0645bccfd923cbe6a2ef6c1 +F src/mem6.c d1767b3715c31b830955bda1f3f1852619dcb687 F src/mutex.c a485a0eac8ee2cd95f66e565b4c6696c18db968f F src/mutex.h e52ffa1dfc6a6077e8b1823d2c2b7dfcbcf85594 F src/mutex_os2.c 9c5637aa4c307c552566d0f0b3bd206245b54a97 @@ -612,7 +612,7 @@ F tool/speedtest16.c c8a9c793df96db7e4933f0852abb7a03d48f2e81 F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 1dbced29de5f59ba2ebf877edcadf171540374d1 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e -P 22177dac2e3cd9acafe7fcc71674a675fdd098ff -R 11e1cd41a325e7c59adaae6fe6ca47fe -U drh -Z 73c60297f94ac2927669701b9ab7fab2 +P ef0250f3dc769a4acd534f31fa06d90922d4145b +R 3a1f8b26d9d09e25bc3a5b4bbb94bcd2 +U danielk1977 +Z b88159d551f91e2db988e4c894c73dc0 diff --git a/manifest.uuid b/manifest.uuid index f76d873620..6b73b4bde0 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -ef0250f3dc769a4acd534f31fa06d90922d4145b \ No newline at end of file +4528f7b1cce2d009f1bf32bfb8eeaf3ce5531f41 \ No newline at end of file diff --git a/src/mem6.c b/src/mem6.c index 5b734cc186..aafa568ece 100644 --- a/src/mem6.c +++ b/src/mem6.c @@ -32,7 +32,7 @@ ** fragmentation. On some systems, heap fragmentation can cause a ** significant real-time slowdown. ** -** $Id: mem6.c,v 1.5 2008/07/25 10:40:19 danielk1977 Exp $ +** $Id: mem6.c,v 1.6 2008/07/25 16:07:01 danielk1977 Exp $ */ #ifdef SQLITE_ENABLE_MEMSYS6 @@ -56,6 +56,8 @@ */ #define MIN_CHUNKSIZE (1<<16) +#define LOG2_MINALLOC 4 + typedef struct Mem6Chunk Mem6Chunk; typedef struct Mem6Link Mem6Link; @@ -102,6 +104,14 @@ struct Mem6Chunk { #define MEM6LINK(idx) ((Mem6Link *)(&pChunk->zPool[(idx)*pChunk->nAtom])) +struct Mem6Global { + int nMinAlloc; /* Minimum allowed allocation size */ + int nThreshold; /* Allocs larger than this go to malloc() */ + int nLogThreshold; /* log2 of (nThreshold/nMinAlloc) */ + sqlite3_mutex *mutex; + Mem6Chunk *pChunk; /* Singly linked list of all memory chunks */ +} mem6; + /* ** Unlink the chunk at pChunk->aPool[i] from list it is currently ** on. It should be found on pChunk->aiFreelist[iLogsize]. @@ -109,7 +119,7 @@ struct Mem6Chunk { static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){ int next, prev; assert( i>=0 && inBlock ); - assert( iLogsize>=0 && iLogsize<=LOGMAX ); + assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold ); assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); next = MEM6LINK(i)->next; @@ -131,7 +141,7 @@ static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){ static void memsys6Link(Mem6Chunk *pChunk, int i, int iLogsize){ int x; assert( i>=0 && inBlock ); - assert( iLogsize>=0 && iLogsize<=LOGMAX ); + assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold ); assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); x = MEM6LINK(i)->next = pChunk->aiFreelist[iLogsize]; @@ -152,41 +162,59 @@ static int memsys6UnlinkFirst(Mem6Chunk *pChunk, int iLogsize){ int i; int iFirst; - assert( iLogsize>=0 && iLogsize<=LOGMAX ); + assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold ); i = iFirst = pChunk->aiFreelist[iLogsize]; assert( iFirst>=0 ); - while( i>0 ){ - if( inext; - } memsys6Unlink(pChunk, iFirst, iLogsize); return iFirst; } +static int roundupLog2(int n){ + static const char LogTable256[256] = { + 0, /* 1 */ + 1, /* 2 */ + 2, 2, /* 3..4 */ + 3, 3, 3, 3, /* 5..8 */ + 4, 4, 4, 4, 4, 4, 4, 4, /* 9..16 */ + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, /* 17..32 */ + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, /* 33..64 */ + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, /* 65..128 */ + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, /* 129..256 */ + }; + + assert(n<=(1<<16) && n>0); + if( n<=256 ) return LogTable256[n-1]; + return LogTable256[(n>>8) - ((n&0xFF)?0:1)] + 8; +} + /* -** Allocate and return a block of nByte bytes from chunk pChunk. If the -** allocation request cannot be satisfied, return 0. +** Allocate and return a block of (pChunk->nAtom << iLogsize) bytes from chunk +** pChunk. If the allocation request cannot be satisfied, return 0. */ -static void *chunkMalloc(Mem6Chunk *pChunk, int nByte){ +static void *chunkMalloc(Mem6Chunk *pChunk, int iLogsize){ int i; /* Index of a mem5.aPool[] slot */ int iBin; /* Index into mem5.aiFreelist[] */ - int iFullSz; /* Size of allocation rounded up to power of 2 */ - int iLogsize; /* Log2 of iFullSz/POW2_MIN */ - - /* Round nByte up to the next valid power of two */ - if( nByte>(pChunk->nBlock*pChunk->nAtom) ) return 0; - for(iFullSz=pChunk->nAtom, iLogsize=0; iFullSzaiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} - if( iBin>LOGMAX ) return 0; + for(iBin=iLogsize; pChunk->aiFreelist[iBin]<0 && iBin<=mem6.nLogThreshold; iBin++){} + if( iBin>mem6.nLogThreshold ) return 0; i = memsys6UnlinkFirst(pChunk, iBin); while( iBin>iLogsize ){ int newSize; - iBin--; newSize = 1 << iBin; pChunk->aCtrl[i+newSize] = CTRL_FREE | iBin; @@ -225,7 +253,7 @@ static void chunkFree(Mem6Chunk *pChunk, void *pOld){ pChunk->aCtrl[iBlock+size-1] |= CTRL_FREE; pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize; - while( iLogsize>iLogsize) & 1 ){ iBuddy = iBlock - size; @@ -291,31 +319,23 @@ static Mem6Chunk *chunkInit(u8 *zChunk, int nChunk, int nMinAlloc){ pChunk->zPool = (u8 *)&pChunk[1]; pChunk->aCtrl = &pChunk->zPool[pChunk->nBlock*pChunk->nAtom]; - for(ii=0; ii<=LOGMAX; ii++){ + for(ii=0; ii<=mem6.nLogThreshold; ii++){ pChunk->aiFreelist[ii] = -1; } iOffset = 0; - for(ii=LOGMAX; ii>=0; ii--){ + for(ii=mem6.nLogThreshold; ii>=0; ii--){ int nAlloc = (1<nBlock ){ + while( (iOffset+nAlloc)<=pChunk->nBlock ){ pChunk->aCtrl[iOffset] = ii | CTRL_FREE; memsys6Link(pChunk, iOffset, ii); iOffset += nAlloc; } - assert((iOffset+nAlloc)>pChunk->nBlock); } return pChunk; } -struct Mem6Global { - int nMinAlloc; /* Minimum allowed allocation size */ - int nThreshold; /* Allocs larger than this go to malloc() */ - sqlite3_mutex *mutex; - Mem6Chunk *pChunk; /* Singly linked list of all memory chunks */ -} mem6; - static void mem6Enter(void){ sqlite3_mutex_enter(mem6.mutex); @@ -338,21 +358,6 @@ static int nextChunkSize(void){ return iTotal; } -/* -** The argument is a pointer that may or may not have been allocated from -** one of the Mem6Chunk objects managed within mem6. If it is, return -** a pointer to the owner chunk. If not, return 0. -*/ -static Mem6Chunk *findChunk(u8 *p){ - Mem6Chunk *pChunk; - for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){ - if( p>=pChunk->zPool && p<=&pChunk->zPool[pChunk->nBlock*pChunk->nAtom] ){ - return pChunk; - } - } - return 0; -} - static void freeChunk(Mem6Chunk *pChunk){ Mem6Chunk **pp = &mem6.pChunk; for( pp=&mem6.pChunk; *pp!=pChunk; pp = &(*pp)->pNext ); @@ -366,17 +371,20 @@ static void *memsys6Malloc(int nByte){ int nTotal = nByte+8; int iOffset = 0; - mem6Enter(); if( nTotal>mem6.nThreshold ){ p = malloc(nTotal); }else{ + int iLogsize = 0; + if( nTotal>(1<pNext){ - p = chunkMalloc(pChunk, nTotal); + p = chunkMalloc(pChunk, iLogsize); if( p ){ break; } } - if( !p ){ int iSize = nextChunkSize(); p = malloc(iSize); @@ -384,14 +392,13 @@ static void *memsys6Malloc(int nByte){ pChunk = chunkInit((u8 *)p, iSize, mem6.nMinAlloc); pChunk->pNext = mem6.pChunk; mem6.pChunk = pChunk; - p = chunkMalloc(pChunk, nTotal); + p = chunkMalloc(pChunk, iLogsize); assert(p); } } - iOffset = ((u8*)p - (u8*)pChunk); + mem6Leave(); } - mem6Leave(); if( !p ){ return 0; @@ -439,25 +446,26 @@ static void *memsys6Realloc(void *p, int nByte){ return p2; } - static int memsys6Roundup(int n){ - int iFullSz; - for(iFullSz=mem6.nMinAlloc; iFullSzmem6.nThreshold ){ + return n; + }else{ + return (1<