basic-software-profiling-part-1-cpu-usage.html (26519B)
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.10.2" /> 6 <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" /> 7 <title>basic-software-profiling-part-1-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 .display.math{display: block; text-align: center; margin: 0.5rem auto;} 30 /* CSS for syntax highlighting */ 31 html { -webkit-text-size-adjust: 100%; } 32 pre > code.sourceCode { white-space: pre; position: relative; } 33 pre > code.sourceCode > span { display: inline-block; line-height: 1.25; } 34 pre > code.sourceCode > span:empty { height: 1.2em; } 35 .sourceCode { overflow: visible; } 36 code.sourceCode > span { color: inherit; text-decoration: inherit; } 37 div.sourceCode { margin: 1em 0; } 38 pre.sourceCode { margin: 0; } 39 @media screen { 40 div.sourceCode { overflow: auto; } 41 } 42 @media print { 43 pre > code.sourceCode { white-space: pre-wrap; } 44 pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; } 45 } 46 pre.numberSource code 47 { counter-reset: source-line 0; } 48 pre.numberSource code > span 49 { position: relative; left: -4em; counter-increment: source-line; } 50 pre.numberSource code > span > a:first-child::before 51 { content: counter(source-line); 52 position: relative; left: -1em; text-align: right; vertical-align: baseline; 53 border: none; display: inline-block; 54 -webkit-touch-callout: none; -webkit-user-select: none; 55 -khtml-user-select: none; -moz-user-select: none; 56 -ms-user-select: none; user-select: none; 57 padding: 0 4px; width: 4em; 58 background-color: #ffffff; 59 color: #a0a0a0; 60 } 61 pre.numberSource { margin-left: 3em; border-left: 1px solid #a0a0a0; padding-left: 4px; } 62 div.sourceCode 63 { color: #1f1c1b; background-color: #ffffff; } 64 @media screen { 65 pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; } 66 } 67 code span { color: #1f1c1b; } /* Normal */ 68 code span.al { color: #bf0303; background-color: #f7e6e6; font-weight: bold; } /* Alert */ 69 code span.an { color: #ca60ca; } /* Annotation */ 70 code span.at { color: #0057ae; } /* Attribute */ 71 code span.bn { color: #b08000; } /* BaseN */ 72 code span.bu { color: #644a9b; font-weight: bold; } /* BuiltIn */ 73 code span.cf { color: #1f1c1b; font-weight: bold; } /* ControlFlow */ 74 code span.ch { color: #924c9d; } /* Char */ 75 code span.cn { color: #aa5500; } /* Constant */ 76 code span.co { color: #898887; } /* Comment */ 77 code span.cv { color: #0095ff; } /* CommentVar */ 78 code span.do { color: #607880; } /* Documentation */ 79 code span.dt { color: #0057ae; } /* DataType */ 80 code span.dv { color: #b08000; } /* DecVal */ 81 code span.er { color: #bf0303; text-decoration: underline; } /* Error */ 82 code span.ex { color: #0095ff; font-weight: bold; } /* Extension */ 83 code span.fl { color: #b08000; } /* Float */ 84 code span.fu { color: #644a9b; } /* Function */ 85 code span.im { color: #ff5500; } /* Import */ 86 code span.in { color: #b08000; } /* Information */ 87 code span.kw { color: #1f1c1b; font-weight: bold; } /* Keyword */ 88 code span.op { color: #1f1c1b; } /* Operator */ 89 code span.ot { color: #006e28; } /* Other */ 90 code span.pp { color: #006e28; } /* Preprocessor */ 91 code span.re { color: #0057ae; background-color: #e0e9f8; } /* RegionMarker */ 92 code span.sc { color: #3daee9; } /* SpecialChar */ 93 code span.ss { color: #ff5500; } /* SpecialString */ 94 code span.st { color: #bf0303; } /* String */ 95 code span.va { color: #0057ae; } /* Variable */ 96 code span.vs { color: #bf0303; } /* VerbatimString */ 97 code span.wa { color: #bf0303; } /* Warning */ 98 </style> 99 <link rel="stylesheet" href="style.css" /> 100 </head> 101 <body> 102 <h1 id="basic-software-profiling-part-1-cpu-usage">Basic Software Profiling, Part 1: CPU Usage</h1> 103 <p>There aren’t many good resources that explain software profiling in an approachable and applicable way. I hope these posts can help readers understand basic software profiling techniques without getting too in the weeds, as I believe getting too into the nuances of performance tends to cause people to dismiss it as something too specialized to try reasoning about.</p> 104 <h2 id="tools">Tools</h2> 105 <p><a href="https://en.wikipedia.org/wiki/Perf_%28Linux%29">Perf</a> is your friend. Unfortunately, only one of the three most popular operating systems (Linux, OpenBSD, FreeBSD) supports perf, but there are sufficient analogs on FreeBSD, and if you’re on OpenBSD good luck.</p> 106 <p>You might also want a visualization tool. I’ll be showing <a href="https://github.com/brendangregg/FlameGraph">flamegraph</a>. Normally I just use perf because <a href="https://www.brendangregg.com/perf.html">it is very powerful</a>, but having pleasing visuals is useful for demonstrations (newer versions of <code>perf</code> can also generate flamegraphs directly, but they aren’t as aesthetic).</p> 107 <h2 id="reading-a-flamegraph">Reading a flamegraph</h2> 108 <p>Let’s start with something easy, how do you read a flamegraph? Take a look at the following flamegraph and, without my help, try to understand what’s being shown:</p> 109 <object data="https://blog.laack.co/images/ex1-fg.svg" type="image/svg+xml" width="100%"> 110 </object> 111 <p>The amount of time spent with the <code>main</code> function on the stack is represented by the width of its bar.</p> 112 <p>Notice how there are multiple bars that say <code>square</code>. This is because we execute <code>square</code> at different 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> 113 <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> 114 <p>The astute among you might’ve noticed that <code>square</code> and <code>squareHelper</code> appear to sometimes be executed outside of the main loop. This is due to how stack depth is calculated, and that’s a bit more technical than I’ll be able to discuss here.</p> 115 <h2 id="perf">Perf</h2> 116 <p>I’ve been a little loose with my words thus far in describing flamegraphs. The command I’ve been using with perf to generate the data for flamegraphs isn’t tracking 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. Additionally, since perf is interrupt based, it may miss some data, but it gives a good enough approximation of CPU utilization.</p> 117 <pre><code>perf record -g ./ex1</code></pre> 118 <p>This is the command I ran to generate the data for the flamegraph. The <code>record</code> command is used to record events that will be written to the <code>perf.data</code> file. By default, <code>perf record</code> will sample at 1000Hz. The final option, <code>-g</code>, is used to specify we are interested in having the call stack included in our data.</p> 119 <p>If you want to generate a flamegraph right away, you can run the following command:</p> 120 <pre><code>perf script report flamegraph</code></pre> 121 <p>This isn’t how the flamegraph above was generated because I prefer Brendan’s FlameGraph program, but both are fairly similar, and in a pinch, <code>perf script report flamegraph</code> will work. A command I use more often to view performance is:</p> 122 <pre><code>perf report -g</code></pre> 123 <pre><code>+ 100.00% 0.00% ex1 ex1 [.] _start 124 + 100.00% 0.00% ex1 libc.so.6 [.] __libc_start_main 125 + 100.00% 0.00% ex1 libc.so.6 [.] call_init (inlined) 126 + 100.00% 0.00% ex1 libc.so.6 [.] 0x00007f6302a27781 127 + 99.79% 39.46% ex1 ex1 [.] main 128 + 34.97% 19.94% ex1 ex1 [.] squareHelper(unsigned int) 129 + 29.99% 19.90% ex1 ex1 [.] square(unsigned int) 130 + 21.61% 20.69% ex1 ex1 [.] factorial(unsigned int) 131 ...</code></pre> 132 <p>or if I’m curious to see function calling information:</p> 133 <pre><code>perf report -g --stdio</code></pre> 134 <pre><code>... 135 |--88.87%--main 136 | | 137 | |--19.84%--squareHelper(unsigned int) 138 | | | 139 | | --4.99%--square(unsigned int) 140 | | 141 | |--19.55%--factorial(unsigned int) 142 | | 143 | --10.07%--square(unsigned int) 144 | 145 |--5.02%--squareHelper(unsigned int) 146 | 147 |--4.98%--square(unsigned int) 148 | 149 --1.13%--factorial(unsigned int) 150 ...</code></pre> 151 <p>In many cases, I find the <code>--stdio</code> command a bit difficult to read because the report can get exceptionally wide for any non-trivial program (there are additional CLI options that can help with this), and such navigation in the terminal is difficult.</p> 152 <p>The final thing I wanted to mention is if you just want high level information about your program’s performance, this is a useful command:</p> 153 <pre><code>perf stat ./ex1</code></pre> 154 <pre><code> Performance counter stats for './ex1': 155 156 0 context-switches:u # 0.0 cs/sec cs_per_second 157 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 158 132 page-faults:u # 4.1 faults/sec page_faults_per_second 159 32,436.48 msec task-clock:u # nan CPUs CPUs_utilized 160 356,775 branch-misses:u # 0.0 % branch_miss_rate (88.89%) 161 63,706,083,988 branches:u # 1964.0 M/sec branch_frequency (88.89%) 162 134,126,037,336 cpu-cycles:u # 4.1 GHz cycles_frequency (88.89%) 163 300,951,617,557 instructions:u # 2.2 instructions insn_per_cycle (88.89%) 164 TopdownL1 # 4.4 % tma_backend_bound 165 # 61.4 % tma_bad_speculation (88.89%) 166 # 0.0 % tma_frontend_bound (77.78%) 167 # 34.2 % tma_retiring (88.89%) 168 169 32.440411262 seconds time elapsed 170 171 32.234190000 seconds user 172 0.002939000 seconds sys</code></pre> 173 <p>This is the command I run most frequently when validating optimizations where the optimization is targeting a portion of the codebase with an outsized footprint. If the program is more uniformly expensive, <code>perf stat</code> is likely less useful than a full report / flamegraph.</p> 174 <h2 id="what-to-optimize">What to optimize</h2> 175 <p>Start with the functions that are costing the most CPU time. Often a very small number of functions take up the majority of the computation, and these are the ones worth optimizing. As it relates to optimization in this context, I don’t expect most people to be hand coding assembly, and if you are, you already know all of this anyways. This is for the people just building normal software, consider what’s costly and ask yourself two questions:</p> 176 <ol type="1"> 177 <li>Would it be possible to call this function less often</li> 178 <li>Would it be possible to make each call of this function perform less work</li> 179 </ol> 180 <p>Work is key for most optimization; cache friendliness is important, but what I really want from software I use is for it to not leave tons of performance on the table by using bad algorithms, performing unexpected / unnecessary copies, or calling functions (like draw functions) when they don’t have to.</p> 181 <h2 id="amfora">Amfora</h2> 182 <p>Something useful to understand when profiling is the ideal case. Without a conception of how long (roughly) reading a file should take, transferring data, or drawing text, it’s hard to understand if performance is to be expected or abnormal. This is very contextual, so I can’t answer every question that’s relevant for this, but something I’ve found useful is comparing what I have with something that’s similar in ways I’d anticipate that result in similar performance to see where each implementation is spending a disproportionate amount of cycles.</p> 183 <p>To this end, when I was working on my Gemini protocol browser I wanted to compare it against a well known browser. Amfora states in the readme that it “aims to be the best looking Gemini client with the most features”, and while I absotlutely detest the idea that more features means slower in all cases, they do have some features that make it slower*. Specifically, they have syntax highlighting and per character coloring, neither of which my browser has, instead opting for a simpler line based coloring approach which I believe still results in nice looking gemtext because it’s all line based at the end of the day.</p> 184 <p>(* They could’ve done coloring as a second pass perhaps to improve perceived performance, but I’d imagine that’d be more complex, and it would increase the time to having the finalized text displayed)</p> 185 <p>I decided the first benchmark I was going to perform was a comparison between their performances when opening large files on my filesystem. This was quickly stopped when I realized amfora has a max file size limit of 2097152 bytes or ~2MB. That’s curious, but alright then. Let’s just make a file that’s bigger than 1MB.</p> 186 <p>This is a first pass at a direct comparison so I’m not going to make it the max size, and I’m not going to use a representative text, just a bunch of numbers.</p> 187 <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> 188 <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> 189 <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> 190 <p>That should be good enough, the resulting file is ~1.3MB in size.</p> 191 <p>I then ran following command:</p> 192 <pre><code>perf stat amfora lf.txt 193 194 Performance counter stats for 'amfora lf.txt': 195 196 0 context-switches:u # 0.0 cs/sec cs_per_second 197 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 198 2,742 page-faults:u # 9306.7 faults/sec page_faults_per_second 199 294.63 msec task-clock:u # nan CPUs CPUs_utilized 200 1,052,499 branch-misses:u # 0.2 % branch_miss_rate (90.02%) 201 575,712,764 branches:u # 1954.1 M/sec branch_frequency (89.14%) 202 955,922,330 cpu-cycles:u # 3.2 GHz cycles_frequency (87.42%) 203 2,669,651,845 instructions:u # 2.8 instructions insn_per_cycle (88.36%) 204 TopdownL1 # 6.7 % tma_backend_bound 205 # 24.9 % tma_bad_speculation (90.11%) 206 # 16.4 % tma_frontend_bound (79.92%) 207 # 52.0 % tma_retiring (90.37%) 208 209 0.473990805 seconds time elapsed 210 211 0.272938000 seconds user 212 0.021266000 seconds sys 213 </code></pre> 214 <p>This is quite unscientific because I simply Ctrl-C’d out once the first characters had rendered. Here’s the same for foreseen:</p> 215 <pre><code>perf stat foreseen lf.txt 216 217 Performance counter stats for 'foreseen lf.txt': 218 219 0 context-switches:u # 0.0 cs/sec cs_per_second 220 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 221 8,936 page-faults:u # 104842.2 faults/sec page_faults_per_second 222 85.23 msec task-clock:u # nan CPUs CPUs_utilized 223 209,148 branch-misses:u # 0.1 % branch_miss_rate (88.30%) 224 176,970,330 branches:u # 2076.3 M/sec branch_frequency (88.29%) 225 248,919,966 cpu-cycles:u # 2.9 GHz cycles_frequency (88.29%) 226 736,194,375 instructions:u # 3.0 instructions insn_per_cycle (88.99%) 227 TopdownL1 # 3.9 % tma_backend_bound 228 # 29.7 % tma_bad_speculation (89.50%) 229 # 21.2 % tma_frontend_bound (77.84%) 230 # 45.2 % tma_retiring (88.33%) 231 232 0.354029324 seconds time elapsed 233 234 0.066861000 seconds user 235 0.021186000 seconds sys</code></pre> 236 <p>Of these metrics, the most comparable one is CPU cycles because they aren’t spinning during the time it took me to react to the text having been rendered, but even so, this isn’t a very good benchmark, and it’s not something I’d post about.</p> 237 <p>Since Amfora can highlight code, let’s see how the performance comparse if we just add our python code block to the top of that file, and rename it to lf.gmi:</p> 238 <pre><code>perf stat amfora lf.gmi 239 240 Performance counter stats for 'amfora lf.gmi': 241 242 0 context-switches:u # 0.0 cs/sec cs_per_second 243 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 244 900,174 page-faults:u # 12090.4 faults/sec page_faults_per_second 245 74,453.35 msec task-clock:u # nan CPUs CPUs_utilized 246 229,042,926 branch-misses:u # 0.4 % branch_miss_rate (88.94%) 247 62,713,218,442 branches:u # 842.3 M/sec branch_frequency (88.85%) 248 153,193,058,619 cpu-cycles:u # 2.1 GHz cycles_frequency (88.97%) 249 306,159,421,078 instructions:u # 2.0 instructions insn_per_cycle (88.90%) 250 TopdownL1 # 0.6 % tma_backend_bound 251 # 97.8 % tma_bad_speculation (88.83%) 252 # -0.1 % tma_frontend_bound (77.86%) 253 # 1.7 % tma_retiring (88.91%) 254 255 28.983517177 seconds time elapsed 256 257 63.894262000 seconds user 258 8.207151000 seconds sys</code></pre> 259 <p>Woah, that’s a lot slower. With foreseen there shouldn’t be any difference because each line is treated ~ the same, so something’s up here. Let’s look at a flamegraph for this.</p> 260 <object data="https://blog.laack.co/images/amfora-before.svg" type="image/svg+xml" width="100%"> 261 </object> 262 <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> 263 <p>Here’s where that’d be used in the function:</p> 264 <pre><code>rendered += fmt.Sprintf("[%s]", config.GetColorString("preformatted_text")) + 265 buf + fmt.Sprintf("[%s:%s:-]\r\n", config.GetColorString("regular_text"), config.GetColorString("bg")) 266 267 ... 268 269 rendered += buf + "\r\n" 270 271 ... 272 273 rendered += ren 274 275 ... 276 277 buf += strings.TrimSuffix(lines[i], "\r") + "\r\n"</code></pre> 278 <p>Well, there’s our problem; each of these seemingly innocuous appends is actually very costly. Unlike sensible OO / procedural programming languages, Go strings are immutable so each of these operations will create an entirely new string each time, 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 we only have the tail 200,000 lines in the file don’t have a format switcher.</p> 279 <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> 280 <p>(NOTE: The profiling I did to find this differed slightly from what’s shown here, hence the difference in numbers between what we see now, and what’s seen in the PR, but they’re similar enough)</p> 281 <pre><code>perf stat amfora lf.gmi 282 283 Performance counter stats for 'amfora lf.gmi': 284 285 0 context-switches:u # 0.0 cs/sec cs_per_second 286 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 287 6,039 page-faults:u # 4871.9 faults/sec page_faults_per_second 288 1,239.55 msec task-clock:u # nan CPUs CPUs_utilized 289 3,631,996 branch-misses:u # 0.1 % branch_miss_rate (89.02%) 290 3,017,891,055 branches:u # 2434.7 M/sec branch_frequency (88.96%) 291 4,654,531,574 cpu-cycles:u # 3.8 GHz cycles_frequency (88.93%) 292 14,168,541,807 instructions:u # 3.1 instructions insn_per_cycle (88.81%) 293 TopdownL1 # 2.2 % tma_backend_bound 294 # 36.9 % tma_bad_speculation (88.80%) 295 # 18.5 % tma_frontend_bound (77.83%) 296 # 42.5 % tma_retiring (88.90%) 297 298 1.185772969 seconds time elapsed 299 300 1.193871000 seconds user 301 0.039062000 seconds sys</code></pre> 302 <p>Much better, that’s now using 32x less cycles, and is far faster than before.</p> 303 <object data="https://blog.laack.co/images/amfora-after.svg" type="image/svg+xml" width="100%"> 304 </object> 305 <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> 306 <p>We can go deeper into this if we’d like, but there are now 3 ~equally costly groupings, and as performance becomes more diffuse, optimizations will generally have a smaller amount of impact on perf, so we can leave this where it is.</p> 307 <h2 id="refutations">Refutations</h2> 308 <p>I think everything above paints a picture that you don’t have to put in that much effort to, in many cases, make things a lot better, and you don’t have to be that well versed in optimization either.</p> 309 <p>I often hear arguments about how we should just let other people make software and we’ll just use it and be happy because they’re smarter / better than us at it, this is often the case with libraries, and I so vehemently disagree with this idea. Amfora is a piece of software with 1.4K Github stars, that’s existed for > 6 years with 54 contributors; it’s not tiny, and yet a glaring issue took this long to find and solve.</p> 310 <p>While I do think there is blame in this situation, I don’t think there should be any shame in writing bad software, but it’s all of our jobs to make our software a little less bad over time, hopefully you can do the same, and help others with that too.</p> 311 <h2 id="whats-next">What’s Next</h2> 312 <p>Consider learning memory profiling next. I didn’t directly discuss the topic because 1) it’s more complex and 2) memory related performance issues often manifest, like we saw in the go example, as CPU performance issues too. I also didn’t discuss anything related to instrumented profiling; everything I’ve shown with perf can be done without changing any code. When you can change the code, you have the ability to get more granular than just getting metrics on the basis of functions. Despite the upsides of instrumented profiling, I rarely do it because it often takes more time. The main context where I do it is to get shareable information with others, in a working context, and for intra-function profiling.</p> 313 <p>Memory stuff is also more complex across languages, where they do weird stuff like go not using malloc.</p> 314 </body> 315 </html>