basic-software-profiling-cpu-usage.html (33299B)
1 <!DOCTYPE html> 2 <html xmlns="http://www.w3.org/1999/xhtml"> 3 <head> 4 <meta charset="utf-8" /> 5 <meta name="generator" content="pandoc 3.11" /> 6 <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" /> 7 <title>basic-software-profiling-cpu-usage</title> 8 <style> 9 /* Default styles provided by pandoc. 10 ** See https://pandoc.org/MANUAL.html#variables-for-html for config info. 11 */ 12 span.smallcaps{font-variant: small-caps;} 13 div.columns{display: flex; gap: 1.5em;} 14 div.column{flex: auto;} 15 @media screen { 16 div.columns{gap: min(4vw, 1.5em);} 17 div.column{overflow-x: auto;} 18 } 19 div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;} 20 /* The extra [class] is a hack that increases specificity enough to 21 override a similar rule in reveal.js */ 22 ul.task-list[class]{list-style: none;} 23 ul.task-list li input[type="checkbox"] { 24 font-size: inherit; 25 width: 0.8em; 26 margin: 0 0.8em 0.2em -1.6em; 27 vertical-align: middle; 28 } 29 /* CSS for syntax highlighting */ 30 html { -webkit-text-size-adjust: 100%; } 31 pre > code.sourceCode { white-space: pre; position: relative; } 32 pre > code.sourceCode > span { display: inline-block; line-height: 1.25; } 33 pre > code.sourceCode > span:empty { height: 1.2em; } 34 .sourceCode { overflow: visible; } 35 code.sourceCode > span { color: inherit; text-decoration: inherit; } 36 div.sourceCode { margin: 1em 0; } 37 pre.sourceCode { margin: 0; } 38 @media screen { 39 div.sourceCode { overflow: auto; } 40 } 41 @media print { 42 pre > code.sourceCode { white-space: pre-wrap; } 43 pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; } 44 } 45 pre.numberSource code 46 { counter-reset: source-line 0; } 47 pre.numberSource code > span 48 { position: relative; left: -4em; counter-increment: source-line; } 49 pre.numberSource code > span > a:first-child::before 50 { content: counter(source-line); 51 position: relative; left: -1em; text-align: right; vertical-align: baseline; 52 border: none; display: inline-block; 53 -webkit-touch-callout: none; -webkit-user-select: none; 54 -khtml-user-select: none; -moz-user-select: none; 55 -ms-user-select: none; user-select: none; 56 padding: 0 4px; width: 4em; 57 background-color: #ffffff; 58 color: #a0a0a0; 59 } 60 pre.numberSource { margin-left: 3em; border-left: 1px solid #a0a0a0; padding-left: 4px; } 61 div.sourceCode 62 { color: #1f1c1b; background-color: #ffffff; } 63 @media screen { 64 pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; } 65 } 66 code span { color: #1f1c1b; } /* Normal */ 67 code span.al { color: #bf0303; background-color: #f7e6e6; font-weight: bold; } /* Alert */ 68 code span.an { color: #ca60ca; } /* Annotation */ 69 code span.at { color: #0057ae; } /* Attribute */ 70 code span.bn { color: #b08000; } /* BaseN */ 71 code span.bu { color: #644a9b; font-weight: bold; } /* BuiltIn */ 72 code span.cf { color: #1f1c1b; font-weight: bold; } /* ControlFlow */ 73 code span.ch { color: #924c9d; } /* Char */ 74 code span.cn { color: #aa5500; } /* Constant */ 75 code span.co { color: #898887; } /* Comment */ 76 code span.cv { color: #0095ff; } /* CommentVar */ 77 code span.do { color: #607880; } /* Documentation */ 78 code span.dt { color: #0057ae; } /* DataType */ 79 code span.dv { color: #b08000; } /* DecVal */ 80 code span.er { color: #bf0303; text-decoration: underline; } /* Error */ 81 code span.ex { color: #0095ff; font-weight: bold; } /* Extension */ 82 code span.fl { color: #b08000; } /* Float */ 83 code span.fu { color: #644a9b; } /* Function */ 84 code span.im { color: #ff5500; } /* Import */ 85 code span.in { color: #b08000; } /* Information */ 86 code span.kw { color: #1f1c1b; font-weight: bold; } /* Keyword */ 87 code span.op { color: #1f1c1b; } /* Operator */ 88 code span.ot { color: #006e28; } /* Other */ 89 code span.pp { color: #006e28; } /* Preprocessor */ 90 code span.re { color: #0057ae; background-color: #e0e9f8; } /* RegionMarker */ 91 code span.sc { color: #3daee9; } /* SpecialChar */ 92 code span.ss { color: #ff5500; } /* SpecialString */ 93 code span.st { color: #bf0303; } /* String */ 94 code span.va { color: #0057ae; } /* Variable */ 95 code span.vs { color: #bf0303; } /* VerbatimString */ 96 code span.wa { color: #bf0303; } /* Warning */ 97 </style> 98 <link rel="stylesheet" href="style.css" /> 99 </head> 100 <body> 101 <h1 id="basic-software-profiling-cpu-usage">Basic Software Profiling: CPU Usage</h1> 102 <p>Tens of millions of human hours are wasted every day because software is slow. The most addressable contributing factor to this state of affairs is education. A specific educational problem is a lack of awareness for how to profile software.</p> 103 <p>To this end, this post will explain how you can find the parts of programs hogging the most CPU time. This post will focus on compiled programs, but the core ideas may be applied to interpreted programs.</p> 104 <h2 id="tools">Tools</h2> 105 <p><a href="https://en.wikipedia.org/wiki/Perf_%28Linux%29">Perf</a> is a suite of tools for program profiling on Linux. We will mainly use it to collect aggregate performance metrics and call stack information. Analogous tools exist for other Free operating systems, and dedicated tools exist for many interpreted languages to collect call stack information.</p> 106 <p><a href="https://github.com/brendangregg/FlameGraph">Flamegraph</a> is a suite of tools for generating flamegraphs, a type of graph designed for the visualization of performance data. I use my <a href="https://git.laack.co/flamegraph">fork of flamegraph</a> which doesn’t add j<strong><em>s</em></strong>** to generated SVGs, but apart from this they function identically.</p> 107 <h2 id="reading-a-flamegraph">Reading a Flamegraph</h2> 108 <p>Take a look at the flamegraph below and try to understand the performance characteristics of the program:</p> 109 <object data="/images/ex1-fg.svg" type="image/svg+xml" width="100%"> 110 </object> 111 <details> 112 <summary> 113 Source code for the program that generated this flamegraph 114 </summary> 115 <div class="sourceCode" id="cb1"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="dt">uint32_t</span> square<span class="op">(</span><span class="dt">uint32_t</span> input<span class="op">)</span> <span class="op">{</span></span> 116 <span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> input <span class="op">*</span> input<span class="op">;</span></span> 117 <span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span> 118 <span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a></span> 119 <span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a><span class="co">// to show stack depths</span></span> 120 <span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a><span class="dt">uint32_t</span> squareHelper<span class="op">(</span><span class="dt">uint32_t</span> input<span class="op">)</span> <span class="op">{</span></span> 121 <span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a> <span class="dt">uint32_t</span> x <span class="op">=</span> <span class="dv">100</span> <span class="op">*</span> <span class="dv">100</span><span class="op">;</span></span> 122 <span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> square<span class="op">(</span>input<span class="op">);</span></span> 123 <span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span> 124 <span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a></span> 125 <span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a><span class="dt">uint32_t</span> factorial<span class="op">(</span><span class="dt">uint32_t</span> input<span class="op">)</span> <span class="op">{</span></span> 126 <span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a> <span class="dt">uint32_t</span> acc <span class="op">=</span> <span class="dv">1</span><span class="op">;</span></span> 127 <span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span><span class="op">(</span>input <span class="op">></span> <span class="dv">1</span><span class="op">)</span> <span class="op">{</span></span> 128 <span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a> acc <span class="op">*=</span> input<span class="op">;</span></span> 129 <span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a> input <span class="op">-=</span> <span class="dv">1</span><span class="op">;</span></span> 130 <span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span> 131 <span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> acc<span class="op">;</span></span> 132 <span id="cb1-18"><a href="#cb1-18" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span> 133 <span id="cb1-19"><a href="#cb1-19" aria-hidden="true" tabindex="-1"></a></span> 134 <span id="cb1-20"><a href="#cb1-20" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> main<span class="op">()</span> <span class="op">{</span></span> 135 <span id="cb1-21"><a href="#cb1-21" aria-hidden="true" tabindex="-1"></a></span> 136 <span id="cb1-22"><a href="#cb1-22" aria-hidden="true" tabindex="-1"></a> <span class="dt">uint32_t</span> ub <span class="op">=</span> <span class="bu">std::</span>sqrt<span class="op">(</span>UINT32_MAX<span class="op">);</span></span> 137 <span id="cb1-23"><a href="#cb1-23" aria-hidden="true" tabindex="-1"></a></span> 138 <span id="cb1-24"><a href="#cb1-24" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span><span class="op">(</span><span class="dt">uint32_t</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> ub<span class="op">;</span> <span class="op">++</span>i<span class="op">)</span> <span class="op">{</span></span> 139 <span id="cb1-25"><a href="#cb1-25" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span><span class="op">(</span><span class="dt">uint32_t</span> x <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> x <span class="op"><</span> <span class="dv">100000</span><span class="op">;</span> <span class="op">++</span>x<span class="op">)</span> <span class="op">{</span></span> 140 <span id="cb1-26"><a href="#cb1-26" aria-hidden="true" tabindex="-1"></a> square<span class="op">(</span>i<span class="op">);</span></span> 141 <span id="cb1-27"><a href="#cb1-27" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span> 142 <span id="cb1-28"><a href="#cb1-28" aria-hidden="true" tabindex="-1"></a></span> 143 <span id="cb1-29"><a href="#cb1-29" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span><span class="op">(</span><span class="dt">uint32_t</span> x <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> x <span class="op"><</span> <span class="dv">100000</span><span class="op">;</span> <span class="op">++</span>x<span class="op">)</span> <span class="op">{</span></span> 144 <span id="cb1-30"><a href="#cb1-30" aria-hidden="true" tabindex="-1"></a> squareHelper<span class="op">(</span>i<span class="op">);</span></span> 145 <span id="cb1-31"><a href="#cb1-31" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span> 146 <span id="cb1-32"><a href="#cb1-32" aria-hidden="true" tabindex="-1"></a></span> 147 <span id="cb1-33"><a href="#cb1-33" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span><span class="op">(</span><span class="dt">uint32_t</span> x <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> x <span class="op"><</span> <span class="dv">20000</span><span class="op">;</span> <span class="op">++</span>x<span class="op">)</span> <span class="op">{</span></span> 148 <span id="cb1-34"><a href="#cb1-34" aria-hidden="true" tabindex="-1"></a> factorial<span class="op">(</span>x <span class="op">%</span> <span class="dv">10</span><span class="op">);</span></span> 149 <span id="cb1-35"><a href="#cb1-35" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span> 150 <span id="cb1-36"><a href="#cb1-36" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span> 151 <span id="cb1-37"><a href="#cb1-37" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div> 152 </details> 153 <p>The amount of time spent with the <code>main</code> function on the call stack is represented by the width of its bar.</p> 154 <p>Notice how there are multiple bars that say <code>square</code>. This is because we execute <code>square</code> at different call stack depths, and the width of each bar is dictated by the amount of time we spent with <code>square</code> on the call stack at a given stack depth.</p> 155 <p>Given how the widths are calculated, we can deduce the top-down width of a bar is how much time the program spent executing a specific function. In the case of <code>squareHelper</code> and <code>square</code>, we see we spent more time executing <code>squareHelper</code> than <code>square</code>, evidenced by the fact that from a top-down view, <code>squareHelper</code> is wider.</p> 156 <p>The astute among you might’ve noticed <code>square</code> and <code>squareHelper</code> seem to have been executed a few times outside of the main loop. This is due to how <code>perf</code> calculates the stack depth. The specifics of this are more in the weeds than we’ll discuss here, but it shouldn’t meaningfully impact the high level information that can be obtained from a flamegraph.</p> 157 <h2 id="perf">Perf</h2> 158 <p>I’ve been loose with my words in terms of the specific data being displayed by the flamegraph. The command I used to generate the data for the flamegraph doesn’t track the amount of time spent with a function on the stack at a given depth, we are instead tracking the number of on-CPU samples taken with the function on the top of the call stack. This distinction is important because things like blocking I/O will not be reflected in our timings.</p> 159 <p>This is the command I ran to generate the data:</p> 160 <div class="sourceCode" id="cb2"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a><span class="ex">perf</span> record <span class="at">-g</span> ./ex1</span></code></pre></div> 161 <p>The <code>record</code> command is used to run a command and record its performance profile. These are written to the <code>perf.data</code> file. By default, <code>perf record</code> will sample at 1000Hz while the program is on-CPU. The final option, <code>-g</code>, is used to specify we are interested in having the call stack included in our data.</p> 162 <p>To view aggregate information about the data in the <code>perf.data</code> file we can run:</p> 163 <div class="sourceCode" id="cb3"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="ex">perf</span> report <span class="at">-g</span></span></code></pre></div> 164 <pre><code>+ 100.00% 0.00% ex1 ex1 [.] _start 165 + 100.00% 0.00% ex1 libc.so.6 [.] __libc_start_main 166 + 100.00% 0.00% ex1 libc.so.6 [.] call_init (inlined) 167 + 100.00% 0.00% ex1 libc.so.6 [.] 0x00007f6302a27781 168 + 99.79% 39.46% ex1 ex1 [.] main 169 + 34.97% 19.94% ex1 ex1 [.] squareHelper(unsigned int) 170 + 29.99% 19.90% ex1 ex1 [.] square(unsigned int) 171 + 21.61% 20.69% ex1 ex1 [.] factorial(unsigned int) 172 ...</code></pre> 173 <p>If you are interested in information about which functions are calling each other, and the resulting on-CPU times therein, you can run this command:</p> 174 <div class="sourceCode" id="cb5"><pre class="sourceCode bash"><code class="sourceCode bash"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a><span class="ex">perf</span> report <span class="at">-g</span> <span class="at">--stdio</span></span></code></pre></div> 175 <pre><code>... 176 |--88.87%--main 177 | | 178 | |--19.84%--squareHelper(unsigned int) 179 | | | 180 | | --4.99%--square(unsigned int) 181 | | 182 | |--19.55%--factorial(unsigned int) 183 | | 184 | --10.07%--square(unsigned int) 185 | 186 |--5.02%--squareHelper(unsigned int) 187 | 188 |--4.98%--square(unsigned int) 189 | 190 --1.13%--factorial(unsigned int) 191 ...</code></pre> 192 <p>In many cases, I find the <code>--stdio</code> command a bit difficult to read because the report can get wide for non-trivial programs (there are additional CLI options that can help with this), and horizontal navigation in the terminal is unergonomic.</p> 193 <p>The final command worth mentioning is:</p> 194 <pre><code>perf stat ./ex1</code></pre> 195 <pre><code> Performance counter stats for './ex1': 196 197 0 context-switches:u # 0.0 cs/sec cs_per_second 198 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 199 132 page-faults:u # 4.1 faults/sec page_faults_per_second 200 32,436.48 msec task-clock:u # nan CPUs CPUs_utilized 201 356,775 branch-misses:u # 0.0 % branch_miss_rate (88.89%) 202 63,706,083,988 branches:u # 1964.0 M/sec branch_frequency (88.89%) 203 134,126,037,336 cpu-cycles:u # 4.1 GHz cycles_frequency (88.89%) 204 300,951,617,557 instructions:u # 2.2 instructions insn_per_cycle (88.89%) 205 TopdownL1 # 4.4 % tma_backend_bound 206 # 61.4 % tma_bad_speculation (88.89%) 207 # 0.0 % tma_frontend_bound (77.78%) 208 # 34.2 % tma_retiring (88.89%) 209 210 32.440411262 seconds time elapsed 211 212 32.234190000 seconds user 213 0.002939000 seconds sys</code></pre> 214 <p>Which provides high level information about the program’s entire execution.</p> 215 <p>This is the command I run most frequently when validating optimizations when the optimization is aimed at improving the performance of a function that contributes a lot to the total program runtime. If the program is more uniformly expensive across many functions, <code>perf stat</code> is less useful than a full report / flamegraph.</p> 216 <h2 id="what-to-optimize">What to Optimize</h2> 217 <p>Start with functions using lots of CPU time that you wouldn’t expect to. Often a small number of functions do the majority of computation, and these are the ones worth optimizing in the average case. To make these functions run faster, you should consider the following:</p> 218 <ol type="1"> 219 <li>Can we call this function less often</li> 220 <li>Can each call perform less work</li> 221 </ol> 222 <p>Both of these questions are about decreasing work, not making the work faster. Making work faster can be complex, so it’s often easier to improve performance by removing wasted work or making algorithmic improvements.</p> 223 <h2 id="case-study">Case Study</h2> 224 <h3 id="amfora">Amfora</h3> 225 <p><a href="https://github.com/makew0rld/amfora">Amfora</a> is a fancy terminal-based Gemini protocol browser with syntax highlighting. Gemini is a text-based protocol which primarily distributes <a href="https://geminiprotocol.net/docs/gemtext.gmi">gemtext</a> documents. These documents use a similar syntax to markdown, but its slightly simpler. I chose to profile this program because software in the Gemini ecosystem is often simple to understand, making it great for educational use cases.</p> 226 <p>When I start profiling software I often find it useful to use an oracle to understand what’s possible. An oracle in this context is a program that performs comparable tasks with decent performance characteristics. I chose <a href="https://git.laack.co/foreseen/">Foreseen</a>, a Gemini protocol browser I developed, as the oracle because it fulfils both criteria.</p> 227 <p>I like to start by searching for worst case performance scenarios. Worst cases are often an amplification of an average case, so by improving worst case performance you can often improve average case performance.</p> 228 <p>Let’s look for the worst case for the task of rendering a textual document. We’ll load a large text file from disk using both browsers, killing the program once the first lines of text are drawn. Since neither browser supports text streaming, they will both have to load and parse the document, and then draw some text to the terminal. To generate the document I executed the following Python code:</p> 229 <div class="sourceCode" id="cb9"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true" tabindex="-1"></a><span class="cf">with</span> <span class="bu">open</span>(<span class="st">"lf.txt"</span>, <span class="st">"w"</span>) <span class="im">as</span> f:</span> 230 <span id="cb9-2"><a href="#cb9-2" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> i <span class="kw">in</span> <span class="bu">range</span>(<span class="dv">0</span>,<span class="dv">200000</span>):</span> 231 <span id="cb9-3"><a href="#cb9-3" aria-hidden="true" tabindex="-1"></a> f.write(<span class="bu">str</span>(i) <span class="op">+</span> <span class="st">"</span><span class="ch">\n</span><span class="st">"</span>)</span></code></pre></div> 232 <p>The resulting file was ~1.3MB in size. I then ran both programs killing each program with Ctrl-C at first draw of the text from the file:</p> 233 <pre><code>perf stat amfora lf.txt 234 235 Performance counter stats for 'amfora lf.txt': 236 237 0 context-switches:u # 0.0 cs/sec cs_per_second 238 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 239 2,742 page-faults:u # 9306.7 faults/sec page_faults_per_second 240 294.63 msec task-clock:u # nan CPUs CPUs_utilized 241 1,052,499 branch-misses:u # 0.2 % branch_miss_rate (90.02%) 242 575,712,764 branches:u # 1954.1 M/sec branch_frequency (89.14%) 243 955,922,330 cpu-cycles:u # 3.2 GHz cycles_frequency (87.42%) 244 2,669,651,845 instructions:u # 2.8 instructions insn_per_cycle (88.36%) 245 TopdownL1 # 6.7 % tma_backend_bound 246 # 24.9 % tma_bad_speculation (90.11%) 247 # 16.4 % tma_frontend_bound (79.92%) 248 # 52.0 % tma_retiring (90.37%) 249 250 0.473990805 seconds time elapsed 251 252 0.272938000 seconds user 253 0.021266000 seconds sys 254 </code></pre> 255 <pre><code>perf stat foreseen lf.txt 256 257 Performance counter stats for 'foreseen lf.txt': 258 259 0 context-switches:u # 0.0 cs/sec cs_per_second 260 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 261 8,936 page-faults:u # 104842.2 faults/sec page_faults_per_second 262 85.23 msec task-clock:u # nan CPUs CPUs_utilized 263 209,148 branch-misses:u # 0.1 % branch_miss_rate (88.30%) 264 176,970,330 branches:u # 2076.3 M/sec branch_frequency (88.29%) 265 248,919,966 cpu-cycles:u # 2.9 GHz cycles_frequency (88.29%) 266 736,194,375 instructions:u # 3.0 instructions insn_per_cycle (88.99%) 267 TopdownL1 # 3.9 % tma_backend_bound 268 # 29.7 % tma_bad_speculation (89.50%) 269 # 21.2 % tma_frontend_bound (77.84%) 270 # 45.2 % tma_retiring (88.33%) 271 272 0.354029324 seconds time elapsed 273 274 0.066861000 seconds user 275 0.021186000 seconds sys</code></pre> 276 <p>This is very unscientific, especially given I was eyeballing when to kill the programs, but that’s how I normally start profiling. We can’t conclude anything from these results yet as the timings are within margin of error.</p> 277 <p>Since Amfora can highlight code, let’s see how that impacts performance. I pasted the Python code block above at the top of the text file and then renamed the file to <code>lf.gmi</code>. We then find:</p> 278 <pre><code>perf stat foreseen lf.gmi 279 280 Performance counter stats for 'foreseen lf.gmi': 281 282 0 context-switches:u # 0.0 cs/sec cs_per_second 283 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 284 6,551 page-faults:u # 90396.7 faults/sec page_faults_per_second 285 72.47 msec task-clock:u # nan CPUs CPUs_utilized 286 154,134 branch-misses:u # 0.1 % branch_miss_rate (88.98%) 287 166,258,529 branches:u # 2294.2 M/sec branch_frequency (88.99%) 288 232,523,911 cpu-cycles:u # 3.2 GHz cycles_frequency (88.96%) 289 705,288,446 instructions:u # 3.0 instructions insn_per_cycle (88.93%) 290 TopdownL1 # 7.6 % tma_backend_bound 291 # 23.2 % tma_bad_speculation (88.96%) 292 # 18.8 % tma_frontend_bound (77.41%) 293 # 50.4 % tma_retiring (88.45%) 294 295 0.381682961 seconds time elapsed 296 297 0.058132000 seconds user 298 0.015949000 seconds sys</code></pre> 299 <pre><code>perf stat amfora lf.gmi 300 301 Performance counter stats for 'amfora lf.gmi': 302 303 0 context-switches:u # 0.0 cs/sec cs_per_second 304 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 305 900,174 page-faults:u # 12090.4 faults/sec page_faults_per_second 306 74,453.35 msec task-clock:u # nan CPUs CPUs_utilized 307 229,042,926 branch-misses:u # 0.4 % branch_miss_rate (88.94%) 308 62,713,218,442 branches:u # 842.3 M/sec branch_frequency (88.85%) 309 153,193,058,619 cpu-cycles:u # 2.1 GHz cycles_frequency (88.97%) 310 306,159,421,078 instructions:u # 2.0 instructions insn_per_cycle (88.90%) 311 TopdownL1 # 0.6 % tma_backend_bound 312 # 97.8 % tma_bad_speculation (88.83%) 313 # -0.1 % tma_frontend_bound (77.86%) 314 # 1.7 % tma_retiring (88.91%) 315 316 28.983517177 seconds time elapsed 317 318 63.894262000 seconds user 319 8.207151000 seconds sys</code></pre> 320 <p>That’s a lot slower for Amfora, ~76x slower than Foreseen, and ~61x slower than it was with the normal text file. Let’s look at a flamegraph for this.</p> 321 <object data="/images/amfora-before.svg" type="image/svg+xml" width="100%"> 322 </object> 323 <p>So 68.34% samples occurred while executing the GC, that’s a bit surprising, even given how awful garbage collectors are. We also see that 25.47% of the time, most of the remaining time, is spent in the RenderGemini function. Of this, most of it is spent on concatstring3, a function under the hood that’s used to concatenate strings.</p> 324 <p>Here’s where that’d be used in the function:</p> 325 <pre><code>rendered += fmt.Sprintf("[%s]", config.GetColorString("preformatted_text")) + 326 buf + fmt.Sprintf("[%s:%s:-]\r\n", config.GetColorString("regular_text"), config.GetColorString("bg")) 327 328 ... 329 330 rendered += buf + "\r\n" 331 332 ... 333 334 rendered += ren 335 336 ... 337 338 buf += strings.TrimSuffix(lines[i], "\r") + "\r\n"</code></pre> 339 <p>Well, there’s our problem; each of these seemingly innocuous appends is very costly. Go strings are immutable so each append creates an entirely new string, and since we accumulate into <code>buf</code> until reaching a preformatted text switch line (“```” lines), the file we were trying to open has to re-create the full string 200,000 times, since the tail 200,000 lines in the file don’t have any format switch lines.</p> 340 <p>This is relatively trivial to solve by using a strings.Builder which doesn’t have this issue, and that’s <a href="https://github.com/makew0rld/amfora/pull/370/changes">what I did</a>*. After this change, we can perform our profiling again to find:</p> 341 <p>(NOTE: The numbers I referenced in the PR differ from what’s shown here, but they’re similar)</p> 342 <pre><code>perf stat amfora lf.gmi 343 344 Performance counter stats for 'amfora lf.gmi': 345 346 0 context-switches:u # 0.0 cs/sec cs_per_second 347 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 348 6,039 page-faults:u # 4871.9 faults/sec page_faults_per_second 349 1,239.55 msec task-clock:u # nan CPUs CPUs_utilized 350 3,631,996 branch-misses:u # 0.1 % branch_miss_rate (89.02%) 351 3,017,891,055 branches:u # 2434.7 M/sec branch_frequency (88.96%) 352 4,654,531,574 cpu-cycles:u # 3.8 GHz cycles_frequency (88.93%) 353 14,168,541,807 instructions:u # 3.1 instructions insn_per_cycle (88.81%) 354 TopdownL1 # 2.2 % tma_backend_bound 355 # 36.9 % tma_bad_speculation (88.80%) 356 # 18.5 % tma_frontend_bound (77.83%) 357 # 42.5 % tma_retiring (88.90%) 358 359 1.185772969 seconds time elapsed 360 361 1.193871000 seconds user 362 0.039062000 seconds sys</code></pre> 363 <p>Much better, that’s now using 32x less cycles, and is far faster than before. It’s also only 3x slower than foreseen on this specific task. This tells me there are further optimizations that can be performed, but I believe we’ve fixed the most obvious issue.</p> 364 <object data="/images/amfora-after.svg" type="image/svg+xml" width="100%"> 365 </object> 366 <p>Looking again at the flamegraph, we see the RenderGemini function is now mostly performing word wrapping, and the GC is only utilizing the CPU during 16.48% of our samples, much better.</p> 367 <p>We can go deeper still on this, but there are now 3 ~equally costly groupings, and as performance becomes more diffuse, optimizations will generally have a smaller amount of impact on performance, so we can leave this where it is. Additional optimizations would also require more investment in instrumentation to support profiling, but I believe most people don’t have to go that far since we’ve seen there are often low hanging fruit that are so obviously incorrect that we don’t have to get very scientific to show tangible improvements.</p> 368 <p>(Relevant <a href="https://xkcd.com/2400/">XKCD</a>)</p> 369 <h2 id="whats-next">What’s Next</h2> 370 <p>This post only discussed on-CPU time profiling for program execution. There are a few additional metrics worth profiling that I’ll discuss in the future:</p> 371 <ol type="1"> 372 <li>Off CPU profiling</li> 373 <li>Memory profiling</li> 374 <li>Build profiling</li> 375 </ol> 376 </body> 377 </html>