Documentation Source Text

Check-in [2722f22a04]
Login

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

Overview
Comment:Updates to the malloc.html document.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2722f22a04a927e8500f9e3b9d6907f0b9ebc117
User & Date: drh 2008-08-04 22:01:43
Context
2008-08-05
03:35
Continuing work on the malloc.html document. check-in: f0f85bacb3 user: drh tags: trunk
2008-08-04
22:01
Updates to the malloc.html document. check-in: 2722f22a04 user: drh tags: trunk
18:08
Continuing work on the memory allocator documentation. check-in: 080d9901f8 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/malloc.in.



1
2
3
4
5
6
7
...
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
...
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558

559






560
561
562
563
564
565
566
567
568
569
...
712
713
714
715
716
717
718
719
720

721
722
723
724
725
726



727
728




729









730




































































































































731
732
733
734
735
736
737


<h1>Dynamic Memory Allocation In SQLite</h1>
<tcl>hd_keywords {memory allocation}</tcl>

<p>SQLite makes extensive use of dynamic memory allocation to obtain
the memory it needs to store various objects
(ex: [database connections] and [prepared statements]) and to build
a memory cache of the database file and to hold the results of queries.
................................................................................
<p>If SQLite needs a page-cache entry that is larger than "sz" bytes or
if it needs more than N entries, it falls back to using the
general-purpose memory allocator.</p>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] frequently need to make numerous
small and relatively short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  These small memory
allocations are used to hold things such as the names of tables
and columns, parse tree nodes, individual query results values,
and b-tree cursor objects.  These small memory allocations result
in many calls to malloc() and free() - so many that malloc() and
free() end up using a significant fraction of the CPU time allocated
to SQLite.</p>

<p>SQLite [version 3.6.1] introduced the lookaside optimization to
help reduce the memory allocation load.  In the lookaside optimization,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size pieces of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with a the [database connection] that are small enough are
allocated one of the pieces of the lookaside pool rather than calling
the general-purpose memory allocator.  Larger allocations continue to
use the general-purpose memory allocator, as do allocations that occur
when all the lookaside pool entries are already checked out.  
But in many cases, the memory
allocations are small enough and there are few enough outstanding that
the memory allocation requests can be satisfied from the lookaside
pool.</p>

<p>Because lookaside allocations are always the same size, the allocation
and deallocation algorithms are fast and efficient.  There is no
need to coalesce adjacent free allocations nor search for an allocation
of a particular size.  Each [database connection] maintains a singly-linked
list of unused allocations.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] is assumed to already be
running in a single thread (and in fact there are mutexes already in
place to enforce this) so no mutexing is required to pull or push
entries from the lookaside freelist.  Consequently, lookaside memory
allocations and deallocations are very fast.  In speed tests on
................................................................................
To change the default size of the lookaside memory pool use the 
following interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each piece of the
allocation.  The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots.  The default value is 500
slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection by default is 50 kilobytes in size.
(Note: default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The size of the lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

<blockquote><pre>
[sqlite3_db_config](db, [SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>


<p>The lookaside memory pool size can only be changed when there are






no lookaside allocations outstanding for the database connection.
Hence, the size should be set immediately after creating the database
connection using [sqlite3_open()] (or related function) and before
evaluating any SQL statements on the connection.</p>

<tcl>hd_fragment memstatus {memory statistics}</tcl>
<h3>3.5 Memory status</h3>

<p>By default, SQLite keeps statistics on its memory usage.  These
statistics are useful in helping to determine how much memory an
................................................................................
for <b>N</b> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  The memory pool will never become
so fragmented that a new memory allocation request cannot be satisfied.
This is an important property for
applications where a software fault could cause injury, physical harm,
loss of irreplaceable data, or significant financial loss.</p>

<p>
<i>To be done:  Discuss how to minimize <b>M</b> and <b>n</b> and

consequently <b>N</b>.</i>
</p>

<p>
<i>To be done:  Discuss how to measure <b>M</b> and <b>n</b> using
[memory statistics].</i>



</p>





















































































































































<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and
>
>







 







|
|






|
|


|
|


|

|
|


|


|




|

|







 







|
|





|



|



|


>
|
>
>
>
>
>
>
|
|
|







 







|
<
>
|
|

|
|
|
>
>
>
|

>
>
>
>

>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
...
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
...
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
...
721
722
723
724
725
726
727
728

729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
<title>Dynamic Memory Allocation In SQLite</title>

<h1>Dynamic Memory Allocation In SQLite</h1>
<tcl>hd_keywords {memory allocation}</tcl>

<p>SQLite makes extensive use of dynamic memory allocation to obtain
the memory it needs to store various objects
(ex: [database connections] and [prepared statements]) and to build
a memory cache of the database file and to hold the results of queries.
................................................................................
<p>If SQLite needs a page-cache entry that is larger than "sz" bytes or
if it needs more than N entries, it falls back to using the
general-purpose memory allocator.</p>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] make numerous
small and short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  These small memory
allocations are used to hold things such as the names of tables
and columns, parse tree nodes, individual query results values,
and b-tree cursor objects.  These small memory allocations result
in many calls to malloc() and free() - so many calls that malloc() and
free() end up using a significant fraction of the CPU time assigned
to SQLite.</p>

<p>SQLite [version 3.6.1] introduced the lookaside memory allocator to
help reduce the memory allocation load.  In the lookaside allocator,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are small enough are
allocated as one of the pieces of the lookaside pool rather than by calling
the general-purpose memory allocator.  Larger allocations continue to
use the general-purpose memory allocator, as do allocations that occur
when all the lookaside pool slots are already checked out.  
But in many cases, the memory
allocations are small enough and there are few enough outstanding that
the new memory requests can be satisfied from the lookaside
pool.</p>

<p>Because lookaside allocations are always the same size, the allocation
and deallocation algorithms are fast and efficient.  There is no
need to coalesce adjacent free slots nor search for a slot
of a particular size.  Each [database connection] maintains a singly-linked
list of unused slots.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] is assumed to already be
running in a single thread (and in fact there are mutexes already in
place to enforce this) so no mutexing is required to pull or push
entries from the lookaside freelist.  Consequently, lookaside memory
allocations and deallocations are very fast.  In speed tests on
................................................................................
To change the default size of the lookaside memory pool use the 
following interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each lookaside slot.
The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots.  The default value is 500
slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection by default is 50 kilobytes in size.
(Note: these default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

<blockquote><pre>
[sqlite3_db_config](db, [SQLITE_DBCONFIG_LOOKASIDE], pBuf, sz, cnt);
</pre></blockquote>

<p>The "pBuf" parameter is a pointer to memory space that will be
used for the lookaside memory pool.  If pBuf is NULL, then SQLite
will obtain its own space for the memory pool using [sqlite3_malloc()].
The "sz" and "cnt" parameters are the size of each lookaside slot
and the number of slots, respectively.  If pBuf is not NULL, then it
must point to at least sz*cnt bytes of memory.</p>

<p>The lookaside configuration can only be changed while there are
no outstanding lookaside allocations for the database connection.
Hence, the configuration should be set immediately after creating the 
database connection using [sqlite3_open()] (or equivalent) and before
evaluating any SQL statements on the connection.</p>

<tcl>hd_fragment memstatus {memory statistics}</tcl>
<h3>3.5 Memory status</h3>

<p>By default, SQLite keeps statistics on its memory usage.  These
statistics are useful in helping to determine how much memory an
................................................................................
for <b>N</b> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  The memory pool will never become
so fragmented that a new memory allocation request cannot be satisfied.
This is an important property for
applications where a software fault could cause injury, physical harm,
loss of irreplaceable data, or significant financial loss.</p>

<h3>4.1 Computing and controlling parameters <b>M</b> and <b>n</b></h3>


<p>The Robson proof applies separately to each of the memory allocators
used by SQLite:</p>

<ul>
<li>The general-purpose memory allocator (usually [memsys5] for
    applications that care about the Robson proof.)</li>
<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For all memory allocators other than the general-purpose memory
allocator, all memory allocations are of the same size.  Hence, <b>n</b>=1
and therefore <b>N</b>=<b>M</b>.  In other words, the memory pool need
be no larger than the largest amount of memory in use at any given moment.</p>

<p>SQLite guarantees that no thread will ever use more than a single
scratch memory slot at one time.  So if an application allocates as many
scratch memory slots as there are threads, and assuming the the size of
each slot is large enough, there is never a chance of overflowing the
scratch memory allocator.  An upper bound on the size of scratch memory
allocations is six times the largest page size.  It is easy, therefore,
to guarantee breakdown-free operation of the scratch memory allocator.
Simply assign buffers shows size is larger than six times the maximum
page size and at least one buffer per thread.</p>

<p>The usage of pagecache memory is somewhat harder to control in
SQLite version 3.6.1, though mechanisms are planned for subsequent
releases that will make controlling pagecache memory much easier.
Prior to the introduction of these new mechanisms, the only way
to control pagecache memory is using the [cache_size pragma].</p>

<p>Safety-critical applications will usually want to modify the
default lookaside memory configuration so that when the initial
lookaside memory buffer is allocated during [sqlite3_open()] the
resulting memory allocation is not so large as to force the <b>n</b>
parameter to be too large.  In order to keep <b>n</b> under control,
it is best to try to keep the largest memory allocation below 2 or 4
kilobytes.  Hence, a reasonable default setup for the lookaside
memory allocator might any one of the following:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 32);  /* 1K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 32);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 64);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 64);  /* 4K */
</pre></blockquote>

<p>Another approach is to initially disable the lookaside memory
allocator:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 0, 0);
</pre></blockquote>

<p>Then let the application maintain a separate pool of larger
lookaside memory buffers that it can distribute to [database connections]
as they are created.  In the common case, the application will only
have a single [database connection] and so the lookaside memory pool
can consist of a single large buffer.</p>

<blockquote><pre>
sqlite3_db_config(db, SQLITE_DBCONFIG_LOOKASIDE, aStatic, 256, 500);
</pre></blockquote>

<p>The lookaside memory allocator is really intended as performance
optimization, not as a method for assuring breakdown-free memory allocation,
so it is not unreasonable to completely disable the lookaside memory
allocator for safety-critical opertions.</p>

<p>The general purpose memory allocator is the most difficult memory pool
to manage, since it support allocations of varying sizes.  Since 
<b>n</b> is a multiplier on <b>M</b> we want to keep <b>n</b> as small
as possible.  This argues for keeping the minimum allocation size for
[memsys5] as large as possible.  In most appliations, the
[lookaside memory allocator] is able to handle small allocations.  So
it is reasonable to set the minimum allocation size for [memsys5] to
2, 4 or even 8 times the maximum size of a lookaside allocation.  
A minimum allocation size of 512 is a reasonable setting.</p>

<p>Large memory allocations might come from several sources:</p>

<ol>
<li>SQL table rows that contain large strings or blobs.</li>
<li>Complex SQL queries that compile down to large [prepared statements].</li>
<li>SQL parser objects used internally by [sqlite3_prepare_v2()].</li>
<li>Storage space for [database connection] objects.</li>
<li>Scratch memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Page cache memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Lookaside buffer allocations for new [database connections].</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the scratch memory allocator, pagecache memory allocator,
and lookaside memory allocator appropriate, as described above.
The storage space required for [database connection] objects depends
to some extent on the length of the filename of the database file, but
rarely exceeds 2KB on 32-bit systems.  (More space is required on
64-bit systems due to the increased size of pointers.)
Each parser object uses about 1.6KB of memory.  Thus, elements 3 through 7
above can easily be controlled to keep the maximum memory allocation
size below 2KB.</p>

<p>If the application is designed to manage data in small pieces,
then the database should never contain any large strings or BLOBs
and hence element 1 above should not be a factor.  If the database
does contain large strings or BLOBs, they should be read using
[sqlite3_blob | incremental BLOB I/O] and rows that contain the
large strings or BLOBs should never be update by any means other
than [sqlite3_blob | incremental BLOB I/O].  Otherwise, the 
[sqlite3_step()] routine will need to read the entire row into
contiguous memory at some point, and that will involve at least
one large memory allocation.</p>

<p>The final source of large memory allocations is the space to hold
the [prepared statements] that result from compiling complex SQL
operations.  Ongoing work by the SQLite developers is reducing the
amount of space required here.  But large and complex queries might
still require [prepared statements] that are several kilobytes in
size.  The only workaround at the moment is for the application to
break complex SQL operations up into two or smaller and simpler 
operations contained in separate [prepared statements].</p>

<p>All things considered, applications should normally be able to
hold their maximum memory allocation size below 2K or 4K.  This
gives a value for log<sub>2</sub>(<b>n</b>) of 2 or 3.  This will
limit <b>N</b> to between 2 and 2.5 times <b>M</b>.</p>

<p>The maximum amount of general-purpose memory needed by the application
is determined by such factors as how many simultaneous open 
[database connection] and [prepared statement] objects the application
uses, and on the complexity of the [prepared statements].  For any
given application, these factors are normally fixed and can be
determined experiementally using [SQLITE_STATUS_MEMORY_USED].
A typical application might only use about 40KB of general-purpose
memory.  This gives a value of <b>N</b> of about 100KB.</p>

<h3>4.2 Ductile failure</h3>

<p>Safety-critical appliations should include a safety margin
in memory sizing calculations and should monitor memory usage at
run-time using the [sqlite3_status()] and [sqlite3_db_status()] 
interfaces to make sure that memory usage does not exceed design 
limits.  Nevertheless, we observe that even if memory usage does
exceed limits, SQLite will usually continue to operate normally.
The [scratch memory allocator], the [pagecache memory allocator],
and the [lookaside memory allocator] all automatically failover
to the general-purpose memory allocator.  And it is usually the
case that the [memsys5] memory allocator will continue to function
without fragmentation even if <b>M</b> exceeds the <b>N/n</b> limit
imposed by the Robson proof.  It is possible for a memory allocation
to fail in this circumstance, but a failure requires an especially
dispicable sequence of allocations and deallocations - a sequence that
SQLite has never been observed to follow.  So it is often the case
that the limits imposed by Robson can be exceeded by a factor of
two with not ill effect. </p>

<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and