676189 - [meta] sqlite3.c botches rounding up allocation sizes to a power-of-two, wasting memory, and under-reporting its memory usage

Assignee

Description

•

13 years ago

In various places sqlite3.c carefully allocates heap blocks that are power-of-two sized, to avoid the heap allocator rounding up the requested size.

One example (note the 1024):

  static int growOpArray(Vdbe *p){
    VdbeOp *pNew;
    int nNew = (p->nOpAlloc ? p->nOpAlloc*2 : (int)(1024/sizeof(Op)));
    pNew = sqlite3DbRealloc(p->db, p->aOp, nNew*sizeof(Op));

Another example:

  ** The size chosen is a little less than a power of two.  That way,
  ** the FileChunk object will have a size that almost exactly fills
  ** a power-of-two allocation.  This mimimizes wasted space in power-of-two
  ** memory allocators.
  */
  #define JOURNAL_CHUNKSIZE ((int)(1024-sizeof(FileChunk*)))
  
  struct FileChunk {
    FileChunk *pNext;               /* Next chunk in the journal */
    u8 zChunk[JOURNAL_CHUNKSIZE];   /* Content of this chunk */
  };

ROWSET_ENTRY_PER_CHUNK is another case like this.


Unfortunately, sqlite3.c adds 8 bytes to every allocation request before it gets sent to the heap allocator, in order to store the request size:

  /*
  ** Like malloc(), but remember the size of the allocation
  ** so that we can find it later using sqlite3MemSize().
  */  
  static void *sqlite3MemMalloc(int nByte){
    sqlite3_int64 *p;
    assert( nByte>0 );
    nByte = ROUND8(nByte);
    p = malloc( nByte+8 );
    if( p ){
      p[0] = nByte;
      p++;
    }else{
      testcase( sqlite3GlobalConfig.xLog!=0 );
      sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes of memory", nByte);
    }
    return (void *)p;
  }

So those carefully computed sizes of 1024 become 1032 and subsequently get rounded up by jemalloc to 2048.  And ironically enough, this renders sqlite3MemSize (which uses the stored size) completely inaccurate -- it underestimates these botched allocations by almost 2x.  Argh!

This accounts for at least 1.3MB of waste in the cumulative allocations that occur when I start up Firefox and load Gmail.  I don't have numbers on how many of those allocations are live at once.

What would be ideal would be to change sqlite3MemSize to just use malloc_usable_size.  That would avoid this rounding botch, and also save 8 bytes per allocation.  Can we change sqlite3.c?

Marco Bonardo [:mak]

Comment 1

•

13 years ago

no, we can't touch sqlite3.c, we can contact sqlite team and suggest upstream fixes though.

Kyle Huey (Exited; not receiving bugmail, old account, do not use)

Comment 2

•

13 years ago

I don't think we should be afraid to patch sqlite in our tree, but we should definitely make the changes upstream too and pick them up when they trickle back.

Whiteboard: [MemShrink] → [MemShrink][clownshoes]

Marco Bonardo [:mak]

Comment 3

•

13 years ago

we are not afraid, we cannot afaict.

Justin Lebar (not reading bugmail)

Comment 4

•

13 years ago

(In reply to comment #3)
> we are not afraid, we cannot afaict.

Why is this?  We patch almost every other library we import...

D. Richard Hipp

Comment 5

•

13 years ago

Background information: SQLite uses a start-time pluggable memory allocator. (Details at http://www.sqlite.org/malloc.html) The default memory allocator is standard library malloc() though SQLite also comes with a memory allocator that allocates from a large static buffer using a power-of-two first-fit algorithm. Or, applications can plug in a different memory allocator of their own choosing. (Note that the test harnesses for SQLite plug in their own custom memory allocators to facilitate testing of out-of-memory (OOM) errors.)

The memory allocator used by SQLite must have four routines. There is the traditional malloc(), realloc(), and free(). And there is a fourth routine (call it size()) which returns the size of an outstanding allocation.

The standard library memory allocators only supports the first three routines. So, when using the standard library memory allocator, SQLite has to wrap it inside a set of routines that store the size of each allocation in the first 8 bytes. This causes the allocations to be larger than requested by 8 bytes, as you have observed.

One possible solution here (assuming jemalloc has a size() interface) is to register jemalloc as the memory allocator directly, without going through the wrapper that adds the 8-byte overhead at the beginning of each allocation. This has the advantage of using less memory and being faster. But it depends on jemalloc supporting a size() interface and it requires some extra code at start-time to register the new malloc implementation with SQLite.

If that approach is not going to work for you, we can add a cpp macro SQLITE_MALLOC_OVERHEAD that defaults to 0, but which you can set to 8 at compile-time, and arrange for those power-of-two memory allocations you identify to request SQLITE_MALLOC_OVERHEAD bytes fewer than a power of two.

The optimal solution in terms of performance and efficient memory utilization will be the first one. But that solution is also more work for FF devs. The SQLITE_MALLOC_OVERHEAD approach is simpler for FF devs, but it not quite as efficient.

We (the SQLite devs) will go ahead and start working on the SQLITE_MALLOC_OVERHEAD approach, which you (the FF devs) can use or not use as you see fit. Let us know if you want further advice on how to plug jemalloc directly into SQLite, bypassing the standard library malloc wrapper.

Kyle Huey (Exited; not receiving bugmail, old account, do not use)

Comment 6

•

13 years ago

(In reply to comment #5)
> The standard library memory allocators only supports the first three
> routines.  So, when using the standard library memory allocator, SQLite has
> to wrap it inside a set of routines that store the size of each allocation
> in the first 8 bytes.  This causes the allocations to be larger than
> requested by 8 bytes, as you have observed.
> 
> One possible solution here (assuming jemalloc has a size() interface) is to
> register jemalloc as the memory allocator directly, without going through
> the wrapper that adds the 8-byte overhead at the beginning of each
> allocation.  This has the advantage of using less memory and being faster. 
> But it depends on jemalloc supporting a size() interface and it requires
> some extra code at start-time to register the new malloc implementation with
> SQLite.

jemalloc supports size() (as malloc_usable_size()), so we should do this.

Thanks for the explanation.

Justin Lebar (not reading bugmail)

Comment 7

•

13 years ago

I'll see if I can get this to work.

Assignee: nobody → justin.lebar+bug

Benjamin Smedberg

Comment 8

•

13 years ago

But be aware that on Linux at least we can't assume that jemalloc is active even when it is built. This is because libxul is sometimes delay loaded, so it really depends on whether the initial binary is linked against jemalloc.