Debian Codegraph @

www/cpu.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>Measuring and Reducing CPU Usage in SQLite</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 Measuring and Reducing CPU Usage in SQLite
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div>
126 <div class="fancy-toc1"><a href="#measuring_performance">2. Measuring Performance</a></div>
127 <div class="fancy-toc2"><a href="#compile_options">2.1. Compile Options</a></div>
128 <div class="fancy-toc2"><a href="#workload">2.2. Workload</a></div>
129 <div class="fancy-toc3"><a href="#update_as_of_2026_01_06">2.2.1. Update As Of 2026-01-06</a></div>
130 <div class="fancy-toc2"><a href="#performance_measurement">2.3. Performance Measurement</a></div>
131 <div class="fancy-toc2"><a href="#microoptimizations">2.4. Microoptimizations</a></div>
132 <div class="fancy-toc1"><a href="#performance_measurement_workflow">3. Performance Measurement Workflow</a></div>
133 <div class="fancy-toc1"><a href="#limitations">4. Limitations</a></div>
134 <div class="fancy-toc1"><a href="#why_does_the_graph_end_in_2025_">5. Why Does The Graph End In 2025?</a></div>
135 </div>
136 </details>
137 </div>
138
139
140
141
142
143 <h1 id="overview"><span>1. </span>Overview</h1>
144
145 <p>The graph below shows the number of CPU cycles used by SQLite on a
146 standard workload, for versions of SQLite between 3.6.1 (2008-08-06)
147 and 3.48.0 (2025-01-14), a span of about 16.4 years.
148 Over this interval, the number of CPU cycles used dropped from about
149 3.376 million down to 0.965 million. So by 2025, SQLite required only
150 about 29% as many CPU cycles as it did in 2008.
151
152 </p><p>
153 This article describes how the SQLite developers measure CPU usage,
154 what those measurements actually mean, and the techniques used by
155 SQLite developers on their continuing quest to further reduce the
156 CPU usage of the SQLite library.
157 </p>
158
159 <center>
160 <hr>
161 <div class="imgcontainer">
162 <img src="./images/cpuusage.png"></div><br>
163 Measured using cachegrind on Ubuntu 16.04 on x64 with gcc 5.4.0 and -Os.<br>
164 <hr>
165 </center>
166
167 <h1 id="measuring_performance"><span>2. </span>Measuring Performance</h1>
168
169 <p>In brief, the CPU performance of SQLite is measured as follows:
170
171 </p><p></p><ol>
172 <li> Compile SQLite in an as-delivered configuration, without any special
173 telemetry or debugging options.
174 </li><li> Link SQLite against a test program that runs approximately 30,000
175 SQL statements representing a typical workload.
176 </li><li> Count the number of CPU cycles consumed using
177 <a href="http://valgrind.org/docs/manual/cg-manual.html">cachegrind</a>.
178 </li></ol>
179
180 <h2 id="compile_options"><span>2.1. </span>Compile Options</h2>
181
182 <p>For performance measurement, SQLite is compiled in approximately the same
183 way as it would be for use in production systems. The compile-time configuration
184 is "approximate" in the sense that every production use of SQLite is
185 different. Compile-time options used by one system are not necessarily
186 the same as those used by others. The key point is that options that
187 significantly impact the generated machine code are avoided. For example,
188 the -DSQLITE_DEBUG option is omitted because that option inserts thousands
189 of assert() statements in the middle of performance critical sections of the
190 SQLite library. The -pg option (on GCC) is omitted because it causes the
191 compiler to emit extra probabilistic performance measuring code which interferes
192 with actual performance measurements.
193
194 </p><p>
195 For performance measurements,
196 the -Os option is used (optimize for size) rather than -O2 because the
197 -O2 option creates so much code movement that it is difficult to associate
198 specific CPU instructions to C source code lines.
199
200 </p><h2 id="workload"><span>2.2. </span>Workload</h2>
201
202 <p>
203 The "typical" workload is generated by the
204 <a href="https://sqlite.org/src/file/test/speedtest1.c">speedtest1.c</a>
205 program in the canonical SQLite source tree. This program strives to
206 exercise the SQLite library in a way that is typical of real-world
207 applications. Of course, every application is different, and so
208 no test program can exactly mirror the behavior of all applications.
209
210 </p><p>
211 The speedtest1.c program is updated from time to time as the SQLite
212 developers' understanding of what constitutes "typical" usage evolves.
213
214 </p><p>
215 The
216 <a href="https://sqlite.org/src/file/tool/speed-check.sh">speed-check.sh</a> shell
217 script, also in the canonical source tree, is used to run the speedtest1.c
218 program. To replicate the performance measurements, collect the following
219 files into a single directory:
220 </p><ul>
221 <li> the "speed-check.sh" script,
222 </li><li> the "speedtest1.c" test program, and
223 </li><li> the <a href="amalgamation.html">SQLite amalgamation</a> source files "sqlite3.c" and
224 "sqlite3.h"
225 </li></ul>
226 <p>
227 Then run "sh speed-check.sh trunk".
228
229 </p><h3 id="update_as_of_2026_01_06"><span>2.2.1. </span>Update As Of 2026-01-06</h3>
230
231 <p>This article was originally written on 2016-12-08.
232 The speed-check.sh script is no longer used. A new script named
233 <a href="https://sqlite.org/src/file/test/speedtest.tcl">speedtest.tcl</a> has
234 been devised and has been used since early 2025. See the
235 <a href="https://sqlite.org/src/file/test/speedtest.md">speedtest.md</a>
236 documentation file for details. This article continues to
237 reference the older performance measurement script, as part of
238 the historical record.
239
240 </p><h2 id="performance_measurement"><span>2.3. </span>Performance Measurement</h2>
241
242 <p>
243 <a href="http://valgrind.org/docs/manual/cg-manual.html">Cachegrind</a> is used to
244 measure performance because it gives answers that are repeatable to
245 7 or more significant digits. In comparison, actual (wall-clock)
246 run times are scarcely repeatable beyond one significant digit.
247
248 <a name="microopt"></a>
249
250 </p><h2 id="microoptimizations"><span>2.4. </span>Microoptimizations</h2>
251
252 <p>
253 The high repeatability of cachegrind allows the SQLite developers to
254 implement and measure "microoptimizations". A microoptimization is
255 a change to the code that results in a very small performance increase.
256 Typical micro-optimizations reduce the number of CPU cycles by 0.1% or
257 0.05% or even less. Such improvements are impossible to measure with
258 real-world timings. But hundreds or thousands of microoptimizations
259 add up, resulting in measurable real-world performance gains.
260
261 </p><h1 id="performance_measurement_workflow"><span>3. </span>Performance Measurement Workflow</h1>
262
263 <p>
264 As SQLite developers edit the SQLite source code, they run the
265 <a href="https://sqlite.org/src/file/tool/speed-check.sh">speed-check.sh</a>
266 shell script to track the performance impact of changes. This
267 script compiles the speedtest1.c program, runs it under cachegrind,
268 processes the cachegrind output using the
269 <a href="https://sqlite.org/src/file/tool/cg_anno.tcl">cg_anno.tcl</a> TCL
270 script, then saves the results in a series of text files.
271 Typical output from the speed-check.sh script looks like this:
272
273 </p><blockquote><pre>
274 ==8683==
275 ==8683== I refs: <font color="red">1,060,925,768</font>
276 ==8683== I1 misses: 23,731,246
277 ==8683== LLi misses: 5,176
278 ==8683== I1 miss rate: 2.24%
279 ==8683== LLi miss rate: 0.00%
280 ==8683==
281 ==8683== D refs: 557,686,925 (361,828,925 rd + 195,858,000 wr)
282 ==8683== D1 misses: 5,067,063 ( 3,544,278 rd + 1,522,785 wr)
283 ==8683== LLd misses: 57,958 ( 16,067 rd + 41,891 wr)
284 ==8683== D1 miss rate: 0.9% ( 1.0% + 0.8% )
285 ==8683== LLd miss rate: 0.0% ( 0.0% + 0.0% )
286 ==8683==
287 ==8683== LL refs: 28,798,309 ( 27,275,524 rd + 1,522,785 wr)
288 ==8683== LL misses: 63,134 ( 21,243 rd + 41,891 wr)
289 ==8683== LL miss rate: 0.0% ( 0.0% + 0.0% )
290 text data bss dec hex filename
291 523044 8240 1976 <font color="red">533260</font> 8230c sqlite3.o
292 220507 1007870 7769352 sqlite3.c
293 </pre></blockquote>
294
295 <p>The important parts of the output (the parts that the developers pay
296 the most attention to) are shown in red.
297 Basically, the developers want to know the size of the compiled SQLite
298 library and how many CPU cycles were needed to run the performance test.
299
300 </p><p>The output from the
301 <a href="https://sqlite.org/src/file/tool/cg_anno.tcl">cg_anno.tcl</a> script
302 shows the number of CPU cycles spent on each line of code.
303 The report is approximately 80,000 lines long. The following is a brief
304 snippet taken from the middle of the report to show what it looks like:
305
306 </p><blockquote><pre>
307 . SQLITE_PRIVATE int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
308 . MemPage *pPage;
309 . assert( cursorOwnsBtShared(pCur) );
310 . assert( pRes!=0 );
311 . assert( *pRes==0 || *pRes==1 );
312 . assert( pCur-&gt;skipNext==0 || pCur-&gt;eState!=CURSOR_VALID );
313 369,648 pCur-&gt;info.nSize = 0;
314 369,648 pCur-&gt;curFlags &amp;= ~(BTCF_ValidNKey|BTCF_ValidOvfl);
315 369,648 *pRes = 0;
316 739,296 if( pCur-&gt;eState!=CURSOR_VALID ) return btreeNext(pCur, pRes);
317 1,473,580 pPage = pCur-&gt;apPage&#91;pCur-&gt;iPage&#93;;
318 1,841,975 if( (++pCur-&gt;aiIdx&#91;pCur-&gt;iPage&#93;)&gt;=pPage-&gt;nCell ){
319 4,340 pCur-&gt;aiIdx&#91;pCur-&gt;iPage&#93;--;
320 5,593 return btreeNext(pCur, pRes);
321 . }
322 728,110 if( pPage-&gt;leaf ){
323 . return SQLITE_OK;
324 . }else{
325 3,117 return moveToLeftmost(pCur);
326 . }
327 721,876 }
328 </pre></blockquote>
329
330 <p>
331 The numbers on the left are the CPU cycle counts for that line of code,
332 of course.
333
334 </p><p>
335 The cg_anno.tcl script removes extraneous details from the default
336 cachegrind annotation
337 output so that before-and-after reports can be compared using a
338 side-by-side diff to view specific details of how a
339 micro-optimization attempt affected performance.
340
341
342 </p><h1 id="limitations"><span>4. </span>Limitations</h1>
343
344 <p>The use of the standardized speedtest1.c workload and cachegrind has
345 enabled significant performance improvement.
346 However, it is important to recognize the limitations of this approach:
347
348 </p><ul>
349 <li><p>
350 Performance measurements are done with a single compiler (gcc 5.4.0),
351 optimization setting (-Os), and
352 on a single platform (Ubuntu 16.04 LTS on x64). The performance of
353 other compilers and processors may vary.
354
355 </p></li><li><p>
356 The speedtest1.c workload that is being measured tries to be representative
357 of a wide range of typical uses of SQLite. But every application is
358 different. The speedtest1.c workload might not be a good proxy for the
359 kinds of activities performed by some applications. The SQLite developers
360 are constantly working to improve the speedtest1.c program, to make it
361 a better proxy for actual SQLite usage. Community feedback is welcomed.
362
363 </p></li><li><p>
364 The cycle counts provided by cachegrind are a good proxy for actual
365 performance, but they are not 100% accurate.
366
367 </p></li><li><p>
368 Only CPU cycle counts are being measured here.
369 CPU cycle counts are a good proxy for energy consumption,
370 but do not necessary correlate well with real-world timings.
371 Time spent doing I/O is not reflected in the CPU cycle counts,
372 and I/O time predominates in many SQLite usage scenarios.
373 </p></li></ul>
374
375 <h1 id="why_does_the_graph_end_in_2025_"><span>5. </span>Why Does The Graph End In 2025?</h1>
376
377 <p>
378 The CPU cycle counts depend a lot on the particular compiler
379 used, and also to some extent on the operating system. All of
380 the measurements in the graph above were made using GCC 5.4.0
381 on Ubuntu 16.04. That machine was powered down in early 2025,
382 and so it is no longer available to do additional measurements.
383
384 </p><p>
385 We could redo all 61 measurements shown in the graph using
386 a more recent compiler. (This update is being entered in early
387 2026 using Linux Mint 2.22 that hosts GCC 13.3.0.) But that
388 would be a lot of work for no noticable gain. Most of the
389 performance gains occurred in years 2013 through 2017, when
390 the microoptimization techniques described above were
391 first being applied to SQLite. You can clearly see in the
392 graph that the performance curve leveled out in about 2018.
393 Since then, there has been a slow increase in performance, but
394 nothing as dramatic as in prior years. We expect this trend
395 to continue.
396
397 </p><p>
398 The developers continue measure performance regularly,
399 certainly at every release, but also after every significant
400 change. We continue to work toward optimizing SQLite to use
401 as few CPU cycles as possible. However, no dramatic
402 performance increases are expected. Note that SQLite
403 is already <a href="fasterthanfs.html">35% Faster Than The Filesystem</a>. How much faster
404 can it get?
405 </p><p align="center"><small><i>This page was last updated on 2026-01-12 12:33:24Z </small></i></p>
406