Performance Engineering Approaches

In a codebase:

1. Take commit-by-commit benchmark measurements
2. Profile and look at hotspots
3. Use Marker APIs to binary search your code and optimise away poor performance.
   3b. Tail performance can be studied and resolved using instrumentation

Glossary:

CPU/Hardware: cache misses, branch mispredictions, CPU-related events
OS/Software: Time, number of context switches, page faults

Linux perf can aggregate data from both
Another example is Tracy which combines Code Instrumentation, Tracing and Characterisation from multiple different sources.

Instrumentation

The most basic version of this is adding a print statement to a program

Best insights for big pieces of cdde, you can use a top-down approach to better understand the behaviour of an application. But you lose out on OS/CPU level insights.

Also as you can probably tell from adding print statements to leetcode solutions, instrumented code is often slower. This is because your instrumentation code usually ends up in the hot path which causes it to take more cycles.

Automatic Instrumentation: Done automatically to perform code coverage analysis or Profile-Guided Optimization.

See also binary instrumentation (static or dynamic). Its either static (ahead of time) or dynamic (insert binaries after compilation).

Intel Pin:

1. instruction count, function calls
2. instruction mix analysis
3. intercepting function calls and execution of any instruction in an application (?)
4. memory intensity and footprint

Overhead

All instrumentations have overhead. Most distributed systems can tolerate up to 5%. So if you need your measurements, you need to whittle the overhead down.

1. Collecting info
2. Storing info
3. Reporting info

To reduce each

1. Reduce collection
2. Make use of online algorithms for mean, variance (e.g. Alon–Matias–Szegedy. Thanks SC2300)

Theres also Knuth's Online variance algo which apparently only takes 50 bytes of memory.

Tracing

blog for more: (strace Wow Much Syscall)

strace: instruments linux kernel

Intel Processor Traces: instruments CPU

Tracing is kind of like leveraging preinstalled instruments

strace runtime increases when the function you're tracing is system call heavy

Performance Monitor Counters

PMC multiplexing: when i have more events than physical counters, then i can reutilise the same counter to count for two different events, swapping between when i count for each event during distinct time samples. Then scale up. Issue occurs if trying to scale this up and hotspots exist.

Marker APIs

e.g. __itt_task_begin for Intel VTune, and amdProfileResume in AMG uProf
You can mark RFCs (remote function calls) for MarkerAPIs to preserve the granularity of instrumentation/tracing, but the CPU/OS level optimisations of PMCs.

read() system call will ensure atomic grouping, to prevent biases of certain metrics to certain phases, and to correlate groups of reads together.

Sampling

SIGPROF: A performance monitoring interrupt

Hotspots fall under here. Sometimes the concept here is poorly named as Sampling.
Sampling is basically...

User-mode sampling sets up threads and expiring timers than upon expiration the application receives a SIGPROF signal.

But EBS uses the PMC to trigger interrupts, and because it has the PMC then its allowed to do cool stuff like sample on L3 cache misses rather than cycles.

(its using the counter overflow feature, you ++ during the event and capture a sample when an overflow occurs and triggers an interrupt)

Use this to get a performance report

$ time -p perf record -F 1000 -- ./x264 -o /dev/null --slow --threads 1
../Bosphorus_1920x1080_120fps_420_8bit_YUV.y4m
[ perf record: Captured and wrote 1.625 MB perf.data (35035 samples) ]
real 36.20 sec
$ perf report -n --stdio
# Samples: 35K of event 'cpu_core/cycles/'
# Event count (approx.): 156756064947

Use this to go one level down and get a line-in-function report

# snippet of annotating source code of 'x264_8_me_search_ref' function
$ perf annotate x264_8_me_search_ref --stdio
Percent | Source code & Disassembly of x264 for cycles:ppp
----------------------------------------------------------
...
:
bmx += square1[bcost&15][0];
<== source code
1.43 : 4eb10d: movsx ecx,BYTE PTR [r8+rdx*2]
<== corresponding machine
code
:
bmy += square1[bcost&15][1];
0.36 : 4eb112: movsx r12d,BYTE PTR [r8+rdx*2+0x1]
:
bmx += square1[bcost&15][0];
0.63 : 4eb118: add
DWORD PTR [rsp+0x38],ecx
:
bmy += square1[bcost&15][1];

To unwind the Function Call Graph (knowing which function that called sqrt())

1. Use frame pointer
2. DWARF
3. LBR (Last Branch Record, see next article)

uops Info Code Analyser — with a static analyser

(see UICA and llvm-mva as static tool analysers)

clang optimises the code into assembly like this. Then you get...vfmadd231ps. Thats...vector fuse multiply add operand2 * operand3 + operand1

so basically clang is trying to batch the sum operation, and leverage triple OOO to parallelise it

"Latest processors have 10+ execution units; how do I write my code to keep them busy all the time" this specifically can tell you how.

Use a Static Analyzer (Note: assumes L1 cache always hits, assumes no misprediction. Solves superscalarity problem)

Latency is E - D + 1
D is Dispatch, E is Executed

As a rule of thumb, in such situations, the loop must be unrolled by a factor of T L, where T is the throughput of an instruction, and L is its latency. In our case, we should have unrolled it by 2 4 = 8 to achieve maximum FMA port utilization since the throughput of FMA on Alder Lake is 2 and the latency of FMA is 4 cycles. This creates 8 separate data flow chains that can be executed independently.

Other Stuff

Roofline model

It's always either compute bound or bandwidth bound.

This model is more in the HPC world, less so in general purpose applications.

General rule: If high arithmetic intensity -> compute bound, vectorise with SIMD and pass work between threads.
If low arithmeitc intensity -> memory bound, improve memory access speed

Instrumentation Might Affect Performance

sometimes instrumentation is a core part of the code. E.g. if IPC dips too low, then defer low priority work.

$ clang-O3-Rpass-analysis=.*-Rpass=.*-Rpass-missed=.* a.c-c
a.c:5:3: remark: loop not vectorized [-Rpass-missed=loop-vectorize]
for (unsigned i = 1; i < N; i++) {
^
a.c:5:3: remark: unrolled loop by a factor of 8 with run-time trip count
[-Rpass=loop-unroll]
for (unsigned i = 1; i < N; i++) {

Compiler Hints

Compilers often decide whether a certain transformation will be beneficial based on their cost model analysis. But compilers don’t always make the optimal choice. Once you detect a key missing optimization in the report, you can attempt to rectify it by changing the source code or by providing hints to the compiler in the form of a #pragma, an attribute, a compiler built-in, etc. As always, verify your hypothesis by measuring it in a practical environment.