basic-software-profiling-part-1-cpu-usage.md (19944B)
1 # Basic Software Profiling, Part 1: CPU Usage 2 3 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. 4 5 ## Tools 6 7 [Perf](https://en.wikipedia.org/wiki/Perf_%28Linux%29) 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. 8 9 You might also want a visualization tool. I'll be showing [flamegraph](https://github.com/brendangregg/FlameGraph). Normally I just use perf because [it is very powerful](https://www.brendangregg.com/perf.html), but having pleasing visuals is useful for demonstrations (newer versions of `perf` can also generate flamegraphs directly, but they aren't as aesthetic). 10 11 ## Reading a flamegraph 12 13 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: 14 15 <object data="https://blog.laack.co/images/ex1-fg.svg" type="image/svg+xml" width="100%"></object> 16 17 The amount of time spent with the `main` function on the stack is represented by the width of its bar. 18 19 Notice how there are multiple bars that say `square`. This is because we execute `square` at different stack depths, and the width of each bar is dictated by the amount of time we spent with `square` on the call stack at a given stack depth. 20 21 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 `squareHelper` and `square`, we see we spent more time executing `squareHelper` than `square`, evidenced by the fact that from a top-down view, `squareHelper` is wider. 22 23 The astute among you might've noticed that `square` and `squareHelper` 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. 24 25 ## Perf 26 27 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. 28 29 ``` 30 perf record -g ./ex1 31 ``` 32 33 This is the command I ran to generate the data for the flamegraph. The `record` command is used to record events that will be written to the `perf.data` file. By default, `perf record` will sample at 1000Hz. The final option, `-g`, is used to specify we are interested in having the call stack included in our data. 34 35 If you want to generate a flamegraph right away, you can run the following command: 36 37 ``` 38 perf script report flamegraph 39 ``` 40 41 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, `perf script report flamegraph` will work. A command I use more often to view performance is: 42 43 ``` 44 perf report -g 45 ``` 46 47 ``` 48 + 100.00% 0.00% ex1 ex1 [.] _start 49 + 100.00% 0.00% ex1 libc.so.6 [.] __libc_start_main 50 + 100.00% 0.00% ex1 libc.so.6 [.] call_init (inlined) 51 + 100.00% 0.00% ex1 libc.so.6 [.] 0x00007f6302a27781 52 + 99.79% 39.46% ex1 ex1 [.] main 53 + 34.97% 19.94% ex1 ex1 [.] squareHelper(unsigned int) 54 + 29.99% 19.90% ex1 ex1 [.] square(unsigned int) 55 + 21.61% 20.69% ex1 ex1 [.] factorial(unsigned int) 56 ... 57 ``` 58 59 or if I'm curious to see function calling information: 60 61 ``` 62 perf report -g --stdio 63 ``` 64 65 ``` 66 ... 67 |--88.87%--main 68 | | 69 | |--19.84%--squareHelper(unsigned int) 70 | | | 71 | | --4.99%--square(unsigned int) 72 | | 73 | |--19.55%--factorial(unsigned int) 74 | | 75 | --10.07%--square(unsigned int) 76 | 77 |--5.02%--squareHelper(unsigned int) 78 | 79 |--4.98%--square(unsigned int) 80 | 81 --1.13%--factorial(unsigned int) 82 ... 83 ``` 84 85 In many cases, I find the `--stdio` 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. 86 87 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: 88 89 ``` 90 perf stat ./ex1 91 ``` 92 93 ``` 94 Performance counter stats for './ex1': 95 96 0 context-switches:u # 0.0 cs/sec cs_per_second 97 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 98 132 page-faults:u # 4.1 faults/sec page_faults_per_second 99 32,436.48 msec task-clock:u # nan CPUs CPUs_utilized 100 356,775 branch-misses:u # 0.0 % branch_miss_rate (88.89%) 101 63,706,083,988 branches:u # 1964.0 M/sec branch_frequency (88.89%) 102 134,126,037,336 cpu-cycles:u # 4.1 GHz cycles_frequency (88.89%) 103 300,951,617,557 instructions:u # 2.2 instructions insn_per_cycle (88.89%) 104 TopdownL1 # 4.4 % tma_backend_bound 105 # 61.4 % tma_bad_speculation (88.89%) 106 # 0.0 % tma_frontend_bound (77.78%) 107 # 34.2 % tma_retiring (88.89%) 108 109 32.440411262 seconds time elapsed 110 111 32.234190000 seconds user 112 0.002939000 seconds sys 113 ``` 114 115 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, `perf stat` is likely less useful than a full report / flamegraph. 116 117 ## What to optimize 118 119 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: 120 121 1. Would it be possible to call this function less often 122 2. Would it be possible to make each call of this function perform less work 123 124 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. 125 126 ## Amfora 127 128 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. 129 130 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. 131 132 (* 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) 133 134 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. 135 136 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. 137 138 ```python 139 with open("lf.txt", "w") as f: 140 for i in range(0,200000): 141 f.write(str(i) + "\n") 142 ``` 143 144 That should be good enough, the resulting file is ~1.3MB in size. 145 146 I then ran following command: 147 148 ``` 149 perf stat amfora lf.txt 150 151 Performance counter stats for 'amfora lf.txt': 152 153 0 context-switches:u # 0.0 cs/sec cs_per_second 154 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 155 2,742 page-faults:u # 9306.7 faults/sec page_faults_per_second 156 294.63 msec task-clock:u # nan CPUs CPUs_utilized 157 1,052,499 branch-misses:u # 0.2 % branch_miss_rate (90.02%) 158 575,712,764 branches:u # 1954.1 M/sec branch_frequency (89.14%) 159 955,922,330 cpu-cycles:u # 3.2 GHz cycles_frequency (87.42%) 160 2,669,651,845 instructions:u # 2.8 instructions insn_per_cycle (88.36%) 161 TopdownL1 # 6.7 % tma_backend_bound 162 # 24.9 % tma_bad_speculation (90.11%) 163 # 16.4 % tma_frontend_bound (79.92%) 164 # 52.0 % tma_retiring (90.37%) 165 166 0.473990805 seconds time elapsed 167 168 0.272938000 seconds user 169 0.021266000 seconds sys 170 171 ``` 172 173 This is quite unscientific because I simply Ctrl-C'd out once the first characters had rendered. Here's the same for foreseen: 174 175 ``` 176 perf stat foreseen lf.txt 177 178 Performance counter stats for 'foreseen lf.txt': 179 180 0 context-switches:u # 0.0 cs/sec cs_per_second 181 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 182 8,936 page-faults:u # 104842.2 faults/sec page_faults_per_second 183 85.23 msec task-clock:u # nan CPUs CPUs_utilized 184 209,148 branch-misses:u # 0.1 % branch_miss_rate (88.30%) 185 176,970,330 branches:u # 2076.3 M/sec branch_frequency (88.29%) 186 248,919,966 cpu-cycles:u # 2.9 GHz cycles_frequency (88.29%) 187 736,194,375 instructions:u # 3.0 instructions insn_per_cycle (88.99%) 188 TopdownL1 # 3.9 % tma_backend_bound 189 # 29.7 % tma_bad_speculation (89.50%) 190 # 21.2 % tma_frontend_bound (77.84%) 191 # 45.2 % tma_retiring (88.33%) 192 193 0.354029324 seconds time elapsed 194 195 0.066861000 seconds user 196 0.021186000 seconds sys 197 ``` 198 199 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. 200 201 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: 202 203 ``` 204 perf stat amfora lf.gmi 205 206 Performance counter stats for 'amfora lf.gmi': 207 208 0 context-switches:u # 0.0 cs/sec cs_per_second 209 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 210 900,174 page-faults:u # 12090.4 faults/sec page_faults_per_second 211 74,453.35 msec task-clock:u # nan CPUs CPUs_utilized 212 229,042,926 branch-misses:u # 0.4 % branch_miss_rate (88.94%) 213 62,713,218,442 branches:u # 842.3 M/sec branch_frequency (88.85%) 214 153,193,058,619 cpu-cycles:u # 2.1 GHz cycles_frequency (88.97%) 215 306,159,421,078 instructions:u # 2.0 instructions insn_per_cycle (88.90%) 216 TopdownL1 # 0.6 % tma_backend_bound 217 # 97.8 % tma_bad_speculation (88.83%) 218 # -0.1 % tma_frontend_bound (77.86%) 219 # 1.7 % tma_retiring (88.91%) 220 221 28.983517177 seconds time elapsed 222 223 63.894262000 seconds user 224 8.207151000 seconds sys 225 ``` 226 227 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. 228 229 <object data="https://blog.laack.co/images/amfora-before.svg" type="image/svg+xml" width="100%"></object> 230 231 232 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. 233 234 Here's where that'd be used in the function: 235 236 ``` 237 rendered += fmt.Sprintf("[%s]", config.GetColorString("preformatted_text")) + 238 buf + fmt.Sprintf("[%s:%s:-]\r\n", config.GetColorString("regular_text"), config.GetColorString("bg")) 239 240 ... 241 242 rendered += buf + "\r\n" 243 244 ... 245 246 rendered += ren 247 248 ... 249 250 buf += strings.TrimSuffix(lines[i], "\r") + "\r\n" 251 ``` 252 253 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 `buf` 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. 254 255 256 This is relatively trivial to solve by using a strings.Builder which doesn't have this issue, and that's [what I did](https://github.com/makew0rld/amfora/pull/370/changes)*. After this change, we can perform our profiling again to find: 257 258 (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) 259 260 ``` 261 perf stat amfora lf.gmi 262 263 Performance counter stats for 'amfora lf.gmi': 264 265 0 context-switches:u # 0.0 cs/sec cs_per_second 266 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 267 6,039 page-faults:u # 4871.9 faults/sec page_faults_per_second 268 1,239.55 msec task-clock:u # nan CPUs CPUs_utilized 269 3,631,996 branch-misses:u # 0.1 % branch_miss_rate (89.02%) 270 3,017,891,055 branches:u # 2434.7 M/sec branch_frequency (88.96%) 271 4,654,531,574 cpu-cycles:u # 3.8 GHz cycles_frequency (88.93%) 272 14,168,541,807 instructions:u # 3.1 instructions insn_per_cycle (88.81%) 273 TopdownL1 # 2.2 % tma_backend_bound 274 # 36.9 % tma_bad_speculation (88.80%) 275 # 18.5 % tma_frontend_bound (77.83%) 276 # 42.5 % tma_retiring (88.90%) 277 278 1.185772969 seconds time elapsed 279 280 1.193871000 seconds user 281 0.039062000 seconds sys 282 ``` 283 284 Much better, that's now using 32x less cycles, and is far faster than before. 285 286 <object data="https://blog.laack.co/images/amfora-after.svg" type="image/svg+xml" width="100%"></object> 287 288 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. 289 290 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. 291 292 ## Refutations 293 294 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. 295 296 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. 297 298 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. 299 300 ## What's Next 301 302 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. 303 304 Memory stuff is also more complex across languages, where they do weird stuff like go not using malloc.