# Part 2: Profiling, PGO & LTO Measuring PGO and LTO on a C++ SPH simulation with perf and flamegraphs, and why they barely helped. # Flashback In part 1, I showed how compiler flags could drastically affect speed: 40x. Everything that was optimized was done via static optimization, which is fine and sufficient for most cases. But before diving into the code, can we extract some more performance? # PGO: Profile Guided Optimization What PGO does is quite simple: it runs your code with (software) performance counters. Calls to functions will be counted, and by doing so, the program will output a "summary" of how your code ran. You should not push these builds to prod. Your compiler (I use clang) will use that data to inline functions, guide branch layout, and split your hot/cold paths. ## Generating a PGO build First things first, you need your build to be a PGO build. It's quite simple, actually: just compile it with `-fprofile-generate` and you're done. If you use meson, the option is wrapped in `-Db_pgo=generate` Build it first with meson: ``` meson setup build-pgo --buildtype=release -Dcpp_args="-march=native -ffast-math -funroll-loops -ffp-contract=fast -fno-stack-protector -DNDEBUG" -Db_pgo=generate meson compile -C build-pgo ``` Then run it: ``` optim episode-2 ? ❯ ./build-pgo/sph 500 --headless 1500 ``` Reconfigure, and build with: ``` meson configure build-pgo -Db_pgo=use meson compile -C build-pgo ``` It's as shrimple as that. ## Benchmarking Now that we have our binary with PGO, let's run it: PGO used: ``` headless: 500 particles, 1500 frames frame 0 | 3.40 ms/step | rho avg 900.2 [513.1..1433.4] | max speed 1.44 frame 30 | 3.02 ms/step | rho avg 804.8 [223.7..1008.6] | max speed 3.92 frame 60 | 3.04 ms/step | rho avg 777.1 [207.1..1042.8] | max speed 2.19 frame 90 | 3.16 ms/step | rho avg 798.6 [197.9..1052.3] | max speed 2.12 frame 120 | 3.21 ms/step | rho avg 844.2 [195.8..1147.9] | max speed 2.42 frame 150 | 3.26 ms/step | rho avg 857.0 [195.8..1118.9] | max speed 3.16 // ... frame 1320 | 3.43 ms/step | rho avg 882.2 [230.7..1087.6] | max speed 3.27 frame 1350 | 3.41 ms/step | rho avg 886.6 [223.8..1088.8] | max speed 2.28 frame 1380 | 3.43 ms/step | rho avg 890.8 [243.7..1082.2] | max speed 2.63 frame 1410 | 3.43 ms/step | rho avg 879.6 [350.5..1064.3] | max speed 3.62 frame 1440 | 3.41 ms/step | rho avg 892.3 [406.6..1082.1] | max speed 3.77 frame 1470 | 3.42 ms/step | rho avg 886.2 [368.0..1074.9] | max speed 2.37 frame 1499 | 3.43 ms/step | rho avg 883.8 [334.6..1088.3] | max speed 1.91 avg 3.45 ms/step over 1500 frames ``` And what about the non-PGO build? ``` headless: 500 particles, 1500 frames frame 0 | 3.10 ms/step | rho avg 900.2 [513.1..1433.4] | max speed 1.44 frame 30 | 3.07 ms/step | rho avg 804.8 [223.7..1008.6] | max speed 3.92 frame 60 | 3.07 ms/step | rho avg 777.1 [207.1..1042.8] | max speed 2.19 frame 90 | 3.14 ms/step | rho avg 798.6 [197.9..1052.3] | max speed 2.12 frame 120 | 3.27 ms/step | rho avg 844.2 [195.8..1147.9] | max speed 2.42 frame 150 | 3.34 ms/step | rho avg 857.0 [195.8..1118.9] | max speed 3.16 // ... frame 1320 | 3.44 ms/step | rho avg 887.1 [199.5..1122.8] | max speed 3.20 frame 1350 | 3.50 ms/step | rho avg 883.4 [233.8..1075.8] | max speed 2.16 frame 1380 | 3.57 ms/step | rho avg 889.9 [230.6..1078.1] | max speed 2.17 frame 1410 | 3.54 ms/step | rho avg 885.4 [197.7..1101.6] | max speed 3.95 frame 1440 | 3.42 ms/step | rho avg 890.3 [195.9..1092.9] | max speed 2.07 frame 1470 | 3.49 ms/step | rho avg 889.6 [203.3..1094.8] | max speed 1.92 frame 1499 | 3.50 ms/step | rho avg 898.0 [199.4..1098.1] | max speed 2.64 avg 3.46 ms/step over 1500 frames ``` Whoops. That's underwhelming, to say the least. Running it a few more times gives an average 3% performance boost, which is welcome, of course. But why? 🐧 # Profiling We are software engineers, and engineers at heart. Just "3% perf boost" doesn't cut it. We need to measure and understand why. And we have a tool for it: `perf`. Let's run it on the PGO-optimized build first: ``` perf stat -e branches,branch-misses ./sph 500 --headless 1000 avg 3.40 ms/step over 1000 frames Performance counter stats for './sph 500 --headless 1000': 3,313,498,538 branches:u 34,560,076 branch-misses:u 3.406098485 seconds time elapsed 3.393040000 seconds user 0.000980000 seconds sys ``` Then the non-PGO: ``` Performance counter stats for './sph 500 --headless 1000': 3,314,636,274 branches:u 34,849,095 branch-misses:u 3.454936810 seconds time elapsed 3.431571000 seconds user 0.001985000 seconds sys ``` So, as discussed earlier, it's kind of disappointing. The change is minimal. 0.8% fewer misses. --- But what does the flame graph say? Non-PGO: ![Flamegraph, non-PGO version](./flamegraph-non-pgo.png) PGO: ![Flamegraph, PGO version](./flamegraph-pgo.png) No changes, really. # What about LTO? LLVM's Link Time Optimization is an *optimization* integrated within LLVM, and thus the Clang compiler. > The LLVM Link Time Optimizer provides complete transparency, while doing intermodular optimization, in the compiler tool chain. Its main goal is to let the developer take advantage of intermodular optimizations without making any significant changes to the developer’s makefiles or build system. This is achieved through tight integration with the linker. In this model, the linker treats LLVM bitcode files like native object files and allows mixing and matching among them. The linker uses libLTO, a shared object, to handle LLVM bitcode files. This tight integration between the linker and LLVM optimizer helps to do optimizations that are not possible in other models. The linker input allows the optimizer to avoid relying on conservative escape analysis. Each symbol (let's say a function) is defined within a module: for instance, math.c, gui.c, or main.c. It'll analyze each module and perform a number of optimizations, e.g. discarding unused symbols. That's why it's a powerful beast when used with PGO: if the compiler knows a branch is never taken, it can discard the corresponding symbols and blocks, clearing the hot path. # Why it didn't work ## The software Looking into my code, there is something to notice. It's a simulation. Every bit that's computed will be computed in a loop. You can't optimize your branches if there are no branches to begin with. **It's as simple as that.** ## The hardware On the other hand, modern CPUs are pretty efficient and smart. First of all: I suggest you take a look at [Demystifying Intel Branch Predictors](https://alexmilenkovich.github.io/publications/files/milenkovic_WDDD02.pdf) by Milena Milenkovic, Aleksandar Milenkovic, and Jeffrey Kulick. While looking to optimize their CPUs, Intel, AMD, and other vendors figured out that shrinking silicon, adding instructions, and optimizing them wasn't enough. They needed to reduce the number of fetches. CPU instructions (your basic assembly building blocks) are fetched by the CPU and stored in the cache. Because the caches are not that large, CPUs will try to select only what's needed. That's where the branch predictor comes in. Through speculative analysis, the CPU will determine which branches are the most used (your hot paths) and cache them, keeping them ready for the next iteration. It works amazingly well in loops. In the end, PGO pre-optimizes something that the CPU already does (PGO build or not!) pretty well. That's why we don't squeeze out as much performance as we wished we would. There is also the case of inlining (function bodies are embedded into their callers, dropping the need for an expensive call). Finally, PGO will also help the compiler with hot/cold splitting. I suggest you have a look at [this talk](https://llvm.org/devmtg/2021-02-28/slides/Ruijie-hot-cold-split.pdf) by Ruijie Fang from Princeton. TL;DR: Some blocks of instructions are never used, some others are used frequently. By separating the most used blocks from the least used ones, your instruction cache will mostly be filled with instructions (blocks) from hot paths. # Where it could work Simply: branch-heavy code. Think about a virtual machine. The CPU can't really analyze programs at that scale. But by running it yourself, you can predict the most used instructions, and when that instruction lands in an `if`, the "pop" branch (most likely, I'm making this up) will be the one the control flow takes most often. # What comes next There are other compiler features that could be used to improve performance. A real benchmark/profiling methodology could also be beneficial. Also, I didn't explore this part, but you can inform the compiler of the branches most likely to be used with ``__builtin_expect``. But I want to dive into the code and optimize it myself: SIMD, Multithreading, SoA, AoS, and more.