blog

Personal blog
git clone git://git.laack.co/blog.git
Log | Files | Refs

(how-to)-profile-your-software.md (20225B)


      1 # (How to) Profile Your Software, Part 1: CPU Go Brrr
      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 annoyed with how slow most Gemini browsers are on low end hardware. This is a rather sad state of affairs because the Gemini protocol is extremely simple, with no support for dynamic layouts or styling. Given this, I believe everyone should perform at the very least  some performance profiling before releasing it. Let's get into it.
      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 file:///home/andrew/gitRepos/blog/perf/ex1-fg.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 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.
    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.
    297 
    298 ## What's Next
    299 
    300 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.
    301 
    302 Memory stuff is also more complex across languages, where they do weird stuff like go not using malloc. 
    303 
    304 ---
    305 
    306 
    307 
    308 ---
    309 
    310 Memory utilization is missing from this; what's the recommendation? 
    311 
    312 - massif
    313     - heap analyzer w/ ability to analyze stack at great addl. cost
    314         - doesn't work with go binaries?
    315             - not directly, need --pages-as-heap=yes because it is just tracking malloc/free stuff
    316                 - LD_PRELOAD uses different malloc symbol ig
    317             - massif-visualizer
    318         - still gives unexpected results for go code.
    319     - can give view into  rss over time with  --pages-as-heap=yes
    320         - this makes it track mmap and such instead of just malloc
    321             - slower, but more accurate to usage
    322                 - this isn't rss because pages are overcounted
    323                 - still doesn't work with go code though
    324 - heaptrack
    325     - seems to just work
    326         - ehh, nope