blog

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

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.