(how-to)-benchmark-your-software.md (18669B)
1 # (How to) Benchmark Your Software 2 3 I recently started working on a browser for the [Gemini protocol](https://geminiprotocol.net/) called [foreseen](https://git.laack.co/foreseen/file/README.html) because I was really annoyed with how slow most fully featured Gemini browsers are. This is absolutely not a request for you to use the browser; it's pretty usable and stable right now, but that's not the point of this post. The point of this post is to explain the absolute bare minimum performance benchmarking that you should do for any program you are releasing, and yes I mean any program you are releasing, there is no excuse for wasting CPU cycles, and there is often a lot left on the table, as we will see. 4 5 ## Tools 6 7 [Perf](https://en.wikipedia.org/wiki/Perf_%28Linux%29) is your friend. Unfortunately, only one of the three main operating systems (linux, openbsd, freebsd) supports perf, but there are sufficient analogs on freebsd, and if you're on openbsd this is probably a post you don't really need to read. 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. 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 file:///home/andrew/gitRepos/blog/perf/ex1.svg 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 118 ## What to optimize 119 120 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: 121 122 1. Would it be possible to call this function less often 123 2. Would it be possible to make each call of this function perform less work 124 125 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. 126 127 ## Amfora 128 129 This is where it all started for me; I was working on my Gemini protocol browser and I wanted to benchmark 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. 130 131 (* 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) 132 133 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. 134 135 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. 136 137 ```python 138 with open("lf.txt", "w") as f: 139 for i in range(0,200000): 140 f.write(str(i) + "\n") 141 ``` 142 143 That should be good enough, the resulting file is ~1.3MB in size. 144 145 I then ran following command: 146 147 ``` 148 perf stat amfora lf.txt 149 150 Performance counter stats for 'amfora lf.txt': 151 152 0 context-switches:u # 0.0 cs/sec cs_per_second 153 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 154 2,742 page-faults:u # 9306.7 faults/sec page_faults_per_second 155 294.63 msec task-clock:u # nan CPUs CPUs_utilized 156 1,052,499 branch-misses:u # 0.2 % branch_miss_rate (90.02%) 157 575,712,764 branches:u # 1954.1 M/sec branch_frequency (89.14%) 158 955,922,330 cpu-cycles:u # 3.2 GHz cycles_frequency (87.42%) 159 2,669,651,845 instructions:u # 2.8 instructions insn_per_cycle (88.36%) 160 TopdownL1 # 6.7 % tma_backend_bound 161 # 24.9 % tma_bad_speculation (90.11%) 162 # 16.4 % tma_frontend_bound (79.92%) 163 # 52.0 % tma_retiring (90.37%) 164 165 0.473990805 seconds time elapsed 166 167 0.272938000 seconds user 168 0.021266000 seconds sys 169 170 ``` 171 172 This is quite unscientific because I simply Ctrl-C'd out once the first characters had rendered. Here's the same for foreseen: 173 174 ``` 175 perf stat foreseen lf.txt 176 177 Performance counter stats for 'foreseen lf.txt': 178 179 0 context-switches:u # 0.0 cs/sec cs_per_second 180 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 181 8,936 page-faults:u # 104842.2 faults/sec page_faults_per_second 182 85.23 msec task-clock:u # nan CPUs CPUs_utilized 183 209,148 branch-misses:u # 0.1 % branch_miss_rate (88.30%) 184 176,970,330 branches:u # 2076.3 M/sec branch_frequency (88.29%) 185 248,919,966 cpu-cycles:u # 2.9 GHz cycles_frequency (88.29%) 186 736,194,375 instructions:u # 3.0 instructions insn_per_cycle (88.99%) 187 TopdownL1 # 3.9 % tma_backend_bound 188 # 29.7 % tma_bad_speculation (89.50%) 189 # 21.2 % tma_frontend_bound (77.84%) 190 # 45.2 % tma_retiring (88.33%) 191 192 0.354029324 seconds time elapsed 193 194 0.066861000 seconds user 195 0.021186000 seconds sys 196 ``` 197 198 Of these metrics, the most comporable 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. 199 200 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: 201 202 ``` 203 perf stat amfora lf.gmi 204 205 Performance counter stats for 'amfora lf.gmi': 206 207 0 context-switches:u # 0.0 cs/sec cs_per_second 208 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 209 900,174 page-faults:u # 12090.4 faults/sec page_faults_per_second 210 74,453.35 msec task-clock:u # nan CPUs CPUs_utilized 211 229,042,926 branch-misses:u # 0.4 % branch_miss_rate (88.94%) 212 62,713,218,442 branches:u # 842.3 M/sec branch_frequency (88.85%) 213 153,193,058,619 cpu-cycles:u # 2.1 GHz cycles_frequency (88.97%) 214 306,159,421,078 instructions:u # 2.0 instructions insn_per_cycle (88.90%) 215 TopdownL1 # 0.6 % tma_backend_bound 216 # 97.8 % tma_bad_speculation (88.83%) 217 # -0.1 % tma_frontend_bound (77.86%) 218 # 1.7 % tma_retiring (88.91%) 219 220 28.983517177 seconds time elapsed 221 222 63.894262000 seconds user 223 8.207151000 seconds sys 224 ``` 225 226 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. 227 228 file:///home/andrew/gitRepos/blog/perf/amfora-before.svg 229 230 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. 231 232 Here's where that'd be used in the function: 233 234 ``` 235 rendered += fmt.Sprintf("[%s]", config.GetColorString("preformatted_text")) + 236 buf + fmt.Sprintf("[%s:%s:-]\r\n", config.GetColorString("regular_text"), config.GetColorString("bg")) 237 238 ... 239 240 rendered += buf + "\r\n" 241 242 ... 243 244 rendered += ren 245 246 ... 247 248 buf += strings.TrimSuffix(lines[i], "\r") + "\r\n" 249 ``` 250 251 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. 252 253 254 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: 255 256 (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) 257 258 ``` 259 perf stat amfora lf.gmi 260 261 Performance counter stats for 'amfora lf.gmi': 262 263 0 context-switches:u # 0.0 cs/sec cs_per_second 264 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second 265 6,039 page-faults:u # 4871.9 faults/sec page_faults_per_second 266 1,239.55 msec task-clock:u # nan CPUs CPUs_utilized 267 3,631,996 branch-misses:u # 0.1 % branch_miss_rate (89.02%) 268 3,017,891,055 branches:u # 2434.7 M/sec branch_frequency (88.96%) 269 4,654,531,574 cpu-cycles:u # 3.8 GHz cycles_frequency (88.93%) 270 14,168,541,807 instructions:u # 3.1 instructions insn_per_cycle (88.81%) 271 TopdownL1 # 2.2 % tma_backend_bound 272 # 36.9 % tma_bad_speculation (88.80%) 273 # 18.5 % tma_frontend_bound (77.83%) 274 # 42.5 % tma_retiring (88.90%) 275 276 1.185772969 seconds time elapsed 277 278 1.193871000 seconds user 279 0.039062000 seconds sys 280 ``` 281 282 Much better, that's now using 32x less cycles, and is far faster than before. 283 284 file:///home/andrew/gitRepos/blog/perf/amfora-after.svg 285 286 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. 287 288 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. 289 290 ## Refutations 291 292 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. 293 294 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. 295 296 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.