SQLite

Check-in [12e612e8e7]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:The MEMSYS5 algorithm does not have to return the block with the lowest address. Any block of the appropriate size will do. Use the first block found on the freelist for the appropriate size for a performance improvement.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 12e612e8e7c4a6f83acf0daf5608151fb5ec1575
User & Date: drh 2013-11-24 00:46:00.452
Context
2013-11-24
01:14
Add the --scratch parameter to speedtest1. Improved error messages when misconfiguring memory parameters in speedtest1. (check-in: 8f3c767a30 user: drh tags: trunk)
00:46
The MEMSYS5 algorithm does not have to return the block with the lowest address. Any block of the appropriate size will do. Use the first block found on the freelist for the appropriate size for a performance improvement. (check-in: 12e612e8e7 user: drh tags: trunk)
2013-11-23
22:45
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. (Closed-Leaf check-in: 8191b51212 user: drh tags: memsys5-performance)
21:29
Add newlines at the end of some error messages in speedtest1. (check-in: 6b98f0af7a user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/mem5.c.
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
    int i = ((u8 *)p-mem5.zPool)/mem5.szAtom;
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}

/*
** Find the first entry on the freelist iLogsize.  Unlink that
** 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;
  }
  memsys5Unlink(iFirst, iLogsize);
  return iFirst;
}

/*
** Return a block of memory of at least nBytes in size.
** Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte is positive.
**
** The caller has obtained a mutex prior to invoking this







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







205
206
207
208
209
210
211



















212
213
214
215
216
217
218
    int i = ((u8 *)p-mem5.zPool)/mem5.szAtom;
    assert( i>=0 && i<mem5.nBlock );
    iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
  }
  return iSize;
}




















/*
** Return a block of memory of at least nBytes in size.
** Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte is positive.
**
** The caller has obtained a mutex prior to invoking this
269
270
271
272
273
274
275

276
277
278
279
280
281
282
283
  */
  for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ){
    testcase( sqlite3GlobalConfig.xLog!=0 );
    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
    return 0;
  }

  i = memsys5UnlinkFirst(iBin);
  while( iBin>iLogsize ){
    int newSize;

    iBin--;
    newSize = 1 << iBin;
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
    memsys5Link(i+newSize, iBin);







>
|







250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
  */
  for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
  if( iBin>LOGMAX ){
    testcase( sqlite3GlobalConfig.xLog!=0 );
    sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte);
    return 0;
  }
  i = mem5.aiFreelist[iBin];
  memsys5Unlink(i, iBin);
  while( iBin>iLogsize ){
    int newSize;

    iBin--;
    newSize = 1 << iBin;
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
    memsys5Link(i+newSize, iBin);