Performance Optimisation

This repository is a working notebook for studying real software the way a performance engineer studies it: by building it, running it, measuring it, tracing it, and slowly learning how its behavior emerges from code, data, and the operating system around it.

The goal is not only to make programs faster. The deeper goal is to learn how to look at a piece of software and answer a harder question: why does it behave the way it does? Once that question becomes clear, optimization stops feeling like guesswork and starts feeling like disciplined engineering.

Table Of Contents

• Current First Target: LevelDB
• Why Build From Source First
• Recommended Workflow
• Tools Summary
• Key Jargon
• What This Project Should Document
• Suggested First Targets
• Recommended First Project
• Short Practical Answer

If you are just beginning, the path through this repository is intentionally simple:

1. Pick a small and well-known C++ project.
2. Fork it and build it locally from source.
3. Benchmark the original upstream code first.
4. Profile it to find the real hotspots.
5. Make one optimization at a time.
6. Re-run tests and benchmarks after every change.

Current First Target: LevelDB

This repository now uses leveldb as the first real analysis target.

LevelDB is a good first companion for this kind of work. It is small enough to understand, serious enough to teach useful lessons, and rich enough to expose real questions about memory, storage, lookup paths, and benchmarking.

It is added as a Git submodule at external/leveldb, not copied into this repository as ordinary source files.

That choice matters for a practical reason:

• Git submodule: a Git feature that stores a pointer to another repository commit instead of storing that repository's full contents in your own Git history.
• Smaller GitHub repository: GitHub will show external/leveldb as a linked submodule entry, so your repository does not need to store LevelDB's full source history.
• Pinned version: your repository records the exact LevelDB commit being analyzed, which makes experiments reproducible.

Why This Is Better Than Copying the Source

If you copy the full LevelDB source into your own repository and commit it directly:

• your repository becomes heavier,
• Git history becomes noisier,
• syncing with upstream becomes harder,
• GitHub shows it as your own tracked files instead of a linked external project.

With a submodule, the relationship is cleaner:

• you still work on the code locally,
• you can commit your own analysis notes and scripts separately,
• GitHub shows a link to the original project,
• and you only track the exact upstream commit you are studying.

LevelDB Setup In This Repository

The current LevelDB source lives here:

• external/leveldb

The local build output should live here:

• build/leveldb

Build output means compiled files such as object files, static libraries, test binaries, and benchmark executables. These are working artifacts, not source material, so they should stay local and out of version control.

This repository ignores those generated files through .gitignore so they do not take space in Git history.

Which Executable Should Be Profiled

There are now two useful executables in this repository:

• build/leveldb/db_bench
• build/app/leveldb_workload

They are related, but they serve different roles.

db_bench is LevelDB's own built-in benchmark program. It is maintained by the LevelDB project and is designed to stress common database workloads such as sequential fill, random fill, and random reads. It is useful when you want to measure LevelDB the way the upstream project already measures itself.

leveldb_workload is our own small app in this repository. It uses the public LevelDB API directly and runs a simpler workload that is easier to understand, modify, and profile.

In practice, it helps to think of them this way:

• Use db_bench when you want LevelDB's official-style benchmark driver.
• Use leveldb_workload when you want a smaller "main app" that you control completely.

If the goal is to learn profiling tools such as perf, valgrind, or AMD uProf, leveldb_workload is the gentler first executable to study because the workload shape is easier to reason about.

Clone And Build Instructions For LevelDB

If someone clones this repository later, this is the setup flow they should follow:

1. Clone this repository with submodules.
2. Fetch LevelDB's own nested submodules for benchmarks and tests.
3. Configure an out-of-tree build.
4. Build only the targets needed for analysis.
5. Run tests and a small benchmark smoke check.
6. Build the small local profiling app.

Example commands:

git clone --recurse-submodules <your-repo-url>
cd perfprojects
git -C external/leveldb submodule update --init --recursive --depth 1
cmake -S external/leveldb -B build/leveldb -DCMAKE_BUILD_TYPE=RelWithDebInfo -DLEVELDB_BUILD_TESTS=ON -DLEVELDB_BUILD_BENCHMARKS=ON -DLEVELDB_INSTALL=OFF
cmake --build build/leveldb --target db_bench leveldb_tests c_test env_posix_test -j4
ctest --test-dir build/leveldb --output-on-failure
build/leveldb/db_bench --benchmarks=fillseq,readrandom --num=10000 --threads=1 --value_size=100 --db=/tmp/leveldb-bench-smoke
cmake -S . -B build/app -DCMAKE_BUILD_TYPE=RelWithDebInfo
cmake --build build/app --target leveldb_workload -j4
./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode fillseq --entries 5000 --value-size 64 --reset-db
./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode readrandom --entries 5000 --reads 10000 --value-size 64

A few of the choices above are worth explaining, because they come up again and again in performance work:

• --recurse-submodules: tells Git to fetch submodules during clone.
• submodule update --init --recursive: fetches submodules that belong to LevelDB itself, such as Google Benchmark and GoogleTest.
• --depth 1: fetches a shallow history for those nested dependencies to save local disk space and download time.
• -S external/leveldb -B build/leveldb: tells CMake to use LevelDB source from external/leveldb and write generated build files into build/leveldb. This is called an out-of-tree build.
• Out-of-tree build: a build where generated files are written outside the source tree. This keeps the source directory clean.
• RelWithDebInfo: a CMake build type that keeps optimization enabled while also including debug information, which is useful for profiling.
• db_bench: LevelDB's built-in benchmark executable for measuring database operations.
• leveldb_tests: LevelDB's unit test binary for correctness checks.
• c_test and env_posix_test: extra LevelDB test executables that ctest expects during a full test pass.
• leveldb_workload: a small app in this repository that opens LevelDB and runs one chosen workload mode such as sequential writes or random reads.

Current Baseline Build Choice

For LevelDB in this repository, the preferred starting build is:

• RelWithDebInfo for profiling and hotspot analysis
• benchmark target enabled
• tests enabled
• install step disabled

Install step disabled means CMake will not prepare packaging or install outputs for system-wide installation. That keeps the setup focused on local analysis work.

What We Have Verified

The current LevelDB submodule has already been checked out and built locally in this repository, so the groundwork is done.

Verified locally:

• db_bench builds successfully
• leveldb_tests builds successfully
• c_test and env_posix_test build successfully
• ctest --test-dir build/leveldb --output-on-failure passes
• a small db_bench smoke run completes successfully
• leveldb_workload builds successfully
• leveldb_workload completes a small sequential write run successfully
• leveldb_workload completes a small random read run successfully

A smoke run is simply a cheap first pass: just enough execution to prove that the tool, the binary, and the workload all work before investing time in deeper profiling.

LevelDB Workload App

The small local app lives here:

• apps/leveldb_workload.cpp

The built executable lives here:

• build/app/leveldb_workload

This app exists because LevelDB is mostly a library, not a standalone server process. In other words, there is no single obvious "main database executable" waiting to be profiled. To study LevelDB, you typically need a runnable program that drives the library. In this repository, you can choose either:

• db_bench, which comes from LevelDB itself
• leveldb_workload, which comes from this repository

Supported workload modes:

• fillseq: write keys in sequential order
• fillrandom: write keys in random order
• readrandom: perform random key lookups
• readseq: scan the whole database in key order
• mixed: mostly reads with some writes

Example profiling commands:

perf stat ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode fillseq --entries 100000 --value-size 100 --reset-db
perf record ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode readrandom --entries 100000 --reads 200000 --value-size 100
valgrind --tool=callgrind ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode mixed --entries 100000 --reads 200000 --value-size 100

Profiling Tools On This Machine

One of the most important lessons in this subject is that no single profiler tells the whole story. Good performance work almost always comes from combining tools, because different tools illuminate different layers of the system.

Tools we use or should be ready to use in this project:

• perf
• AMD uProf
• valgrind
• heaptrack
• massif
• hyperfine
• FlameGraph tools
• strace
• ltrace
• gdb
• bpftrace
• DynamoRIO

On this machine, the following AMD uProf tools are installed:

• /opt/AMDuProf_5.2-606/bin/AMDuProf
• /opt/AMDuProf_5.2-606/bin/AMDuProfCLI
• /opt/AMDuProf_5.2-606/bin/AMDuProfPcm
• /opt/AMDuProf_5.2-606/bin/AMDuProfSys

What Each Tool Actually Profiles

Different profiling tools answer different questions. That is why they are best treated as companions rather than competitors.

Use this quick map:

• perf stat: hardware counter totals Good for cycles, instructions, IPC, cache misses, branch misses, and task-level counts.
• perf record and perf report: sampled CPU hotspots Good for finding where CPU time or sampled events are being spent.
• perf script plus FlameGraph: visualization of sampled stacks Good for turning perf samples into flame graphs that are easier to read.
• AMDuProfCLI: sampled CPU profiling on AMD systems Good for hotspots, call stacks, time-based sampling, CPI-style investigation, branch investigation, and AMD event-based analysis.
• AMDuProfPcm: counter and metric monitoring Good for IPC, memory bandwidth, pipeline metrics, top-down style metrics, and roofline-style analysis.
• AMDuProfSys: system-level metric collection and reporting Good for broader system observation and report workflows.
• hyperfine: command-level benchmark runner Good for repeated timing of whole commands and for comparing before and after runs.
• valgrind --tool=callgrind: software instruction-cost and call graph analysis Good for function-by-function cost analysis, inclusive cost, self cost, and call relationships.
• valgrind --tool=massif: heap memory profiling Good for peak heap usage and memory growth over time.
• heaptrack: allocation profiling Good for finding where heap allocations come from and which code paths allocate too much.
• strace: system call tracing Good for file I/O, process, memory mapping, futex, and kernel interaction debugging.
• ltrace: library call tracing Good for tracing calls into shared libraries, though it is usually less central than strace for systems work.
• bpftrace: eBPF-based tracing Good for dynamic kernel and userspace tracing, latency histograms, syscall timing, and live observability.
• gdb: debugger Good for correctness debugging, crash analysis, thread inspection, and targeted inspection during performance investigations.
• DynamoRIO: dynamic binary instrumentation framework Good for building or running binary instrumentation clients that analyze instruction behavior, memory references, code coverage, and execution traces without recompiling the target.

Short version:

• if you want CPU hotspots, use perf record or AMDuProfCLI
• if you want CPU counters and IPC, use perf stat or AMDuProfPcm
• if you want memory allocation behavior, use heaptrack or massif
• if you want detailed call cost and call graph information, use callgrind
• if you want syscalls and kernel interaction, use strace
• if you want live tracing and latency analysis, use bpftrace
• if you want binary instrumentation, use DynamoRIO

Profiling, Tracing, And Optimization Toolbox

This project treats optimization as a toolbox problem, not a single-tool problem.

Good default toolbox by purpose:

• Whole-program timing: hyperfine
• CPU hotspot discovery: perf record, perf report, FlameGraph, AMDuProfCLI
• CPU counters and architecture behavior: perf stat, AMDuProfPcm
• Heap and allocation behavior: heaptrack, massif
• Syscall and OS interaction tracing: strace
• Dynamic observability and latency tracing: bpftrace
• Deep function-cost analysis: callgrind
• Binary instrumentation: DynamoRIO
• Correctness debugging during optimization: gdb

That matters because system software can become slow for very different reasons:

• too many instructions,
• poor cache behavior,
• branch misprediction,
• lock contention,
• excessive syscalls,
• too many allocations,
• bad memory layout,
• expensive library calls,
• or workload-driver overhead outside the real target.

No one tool can explain all of that alone. The craft lies in knowing which question to ask first, and then choosing the tool that can answer it honestly.

What AMD uProf Is

AMD uProf is AMD's profiling and performance-analysis suite for AMD processors.

It belongs inside the broader toolbox; it is valuable, but it is not the whole story.

Different AMD uProf tools cover different kinds of profiling:

• AMDuProfCLI: sampled CPU profiling, hotspots, call stacks, preset CPU profile modes
• AMDuProfPcm: hardware counter metrics such as IPC, memory behavior, pipeline metrics, and roofline-style analysis
• AMDuProfSys: broader system-oriented collection and reporting

So AMD uProf is not only about CPU time. It also covers hardware-counter and system-observation workflows. What it does not replace especially well is:

• detailed heap allocation tracing like heaptrack
• detailed heap growth tracking like massif
• syscall tracing like strace
• very detailed instrumentation-based function cost views like callgrind
• custom dynamic binary instrumentation like DynamoRIO

Recommended First Use Of AMD uProf

For this repository, the easiest starting points are:

1. AMDuProfCLI with hotspots
2. AMDuProfCLI with overview
3. AMDuProfPcm with ipc
4. AMDuProfPcm with memory

Useful discovery commands:

/opt/AMDuProf_5.2-606/bin/AMDuProfCLI info --system
/opt/AMDuProf_5.2-606/bin/AMDuProfCLI info --list collect-configs
/opt/AMDuProf_5.2-606/bin/AMDuProfCLI info --list pmu-events
/opt/AMDuProf_5.2-606/bin/AMDuProfPcm --help

On this machine, AMDuProfCLI info --list collect-configs shows useful preset configurations such as:

• tbp: time-based sampling
• hotspots: hotspot view with call stacks
• overview: overall performance overview
• cpi: basic CPI and IPC analysis
• ibs: instruction-based sampling
• data_access: data locality and DTLB related analysis
• branch: branch prediction related analysis

Recommended Non-uProf Tools For This Project

Before going deep into vendor-specific tooling, these are the most generally useful tools for this repo:

1. hyperfine
2. perf stat
3. perf record plus perf report
4. callgrind
5. heaptrack
6. strace

Good starter commands:

hyperfine './build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode readrandom --entries 100000 --reads 200000 --value-size 100'
perf stat ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode readrandom --entries 100000 --reads 200000 --value-size 100
perf record ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode mixed --entries 100000 --reads 200000 --value-size 100
perf report
strace -c ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode mixed --entries 100000 --reads 200000 --value-size 100
valgrind --tool=callgrind ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode mixed --entries 100000 --reads 200000 --value-size 100

Why these six:

• they cover timing,
• CPU hotspots,
• CPU counters,
• syscall behavior,
• and detailed software-side cost,

which is already enough to investigate many real system-software bottlenecks.

AMD uProf Examples For This Project

Run a hotspot profile of the local LevelDB app:

/opt/AMDuProf_5.2-606/bin/AMDuProfCLI profile \
  --config hotspots \
  -o /tmp/amduprof-hotspots \
  ./build/app/leveldb_workload \
  --db /tmp/perfprojects-leveldb-app \
  --mode mixed \
  --entries 100000 \
  --reads 200000 \
  --value-size 100

Run an overview profile:

/opt/AMDuProf_5.2-606/bin/AMDuProfCLI profile \
  --config overview \
  -o /tmp/amduprof-overview \
  ./build/app/leveldb_workload \
  --db /tmp/perfprojects-leveldb-app \
  --mode readrandom \
  --entries 100000 \
  --reads 200000 \
  --value-size 100

Collect IPC metrics with AMD uProf PCM:

/opt/AMDuProf_5.2-606/bin/AMDuProfPcm -m ipc -C -A system -o /tmp/leveldb-ipc.csv -- \
  ./build/app/leveldb_workload \
  --db /tmp/perfprojects-leveldb-app \
  --mode readrandom \
  --entries 100000 \
  --reads 200000 \
  --value-size 100

Collect memory metrics with AMD uProf PCM:

/opt/AMDuProf_5.2-606/bin/AMDuProfPcm -m memory -C -A system -o /tmp/leveldb-memory.csv -- \
  ./build/app/leveldb_workload \
  --db /tmp/perfprojects-leveldb-app \
  --mode mixed \
  --entries 100000 \
  --reads 200000 \
  --value-size 100

Important note:

• AMDuProfPcm on this machine prints unsupported processor model for some built-in config handling.
• That means some presets may be limited on this exact system.
• Even so, its help still exposes usable commands such as -m ipc, -m memory, profile, top, and roofline.
• If a built-in metric group fails, fall back to AMDuProfCLI or to custom metric/config input for PCM.

DynamoRIO

DynamoRIO is a dynamic binary instrumentation framework.

That means it can run a program under an instrumentation engine and inspect or modify execution behavior at runtime without requiring the program to be recompiled.

Why it is useful in optimization work:

• it can analyze instruction execution at the binary level,
• it can trace memory references,
• it can measure code coverage and control flow,
• it can support custom instrumentation clients,
• it is useful when you want information that normal profilers do not expose directly.

Practical way to think about it:

• perf and AMD uProf are usually the first tools,
• callgrind is the detailed software-cost tool,
• DynamoRIO is the "build or use a binary instrumentation client" tool when you need deeper runtime inspection.

Common DynamoRIO-related uses:

• instruction tracing
• memory access tracing
• code coverage
• custom runtime analysis
• dynamic instrumentation experiments

Examples of well-known DynamoRIO clients and related tooling people often use with it:

• drcachesim: cache and memory hierarchy simulation
• drmemtrace: memory tracing workflows

Use DynamoRIO when:

• you need binary instrumentation rather than simple sampling,
• you want to inspect instruction or memory behavior in a custom way,
• or you want to build an analysis client for a target executable.

Do not make it the first tool by default. It is more specialized than perf, callgrind, or strace.

Why perf stat Failed On This Machine

You saw this error:

• perf_event_paranoid setting is 4

This means the Linux kernel is configured to heavily restrict access to performance counters for normal users.

In plain language:

• perf is installed,
• your command syntax is fine,
• but the kernel is refusing access to the performance monitoring features you tried to use.

The error text itself explains the important thresholds:

• -1: very open access
• >= 0: blocks raw and ftrace function tracepoint access
• >= 1: blocks CPU event access
• >= 2: blocks kernel profiling

Because your value is 4, it is stricter than the thresholds listed above. That means unprivileged perf stat is blocked on this machine.

Temporary fix for the current boot:

sudo sysctl -w kernel.perf_event_paranoid=1

More permissive temporary fix:

sudo sysctl -w kernel.perf_event_paranoid=-1

Persistent fix:

echo 'kernel.perf_event_paranoid = 1' | sudo tee -a /etc/sysctl.conf
sudo sysctl -p

If you want the least privilege while still enabling more profiling access, start with 1 and only go lower if needed.

Two practical notes:

• some perf features may still require root or extra capabilities,
• AMD uProf tools that rely on Linux perf access may be affected by similar kernel restrictions.

How To Read Callgrind Output

Your command:

valgrind --tool=callgrind ./build/app/leveldb_workload --db /tmp/perfprojects-leveldb-app --mode mixed --entries 100000 --reads 200000 --value-size 100

produced:

• Events: Ir
• Collected: 1750182859

Meaning:

• Ir means instruction references, which is basically the number of machine instructions executed in the simulated run.
• 1,750,182,859 means Callgrind counted about 1.75 billion instruction references for that workload.
• This is not wall-clock time.
• Lower Ir often suggests less work, but you should compare it only between similar runs with the same workload.

Best ways to read Callgrind output:

1. Use callgrind_annotate for a text report.
2. Use KCachegrind or QCachegrind for interactive browsing.

Text report examples:

callgrind_annotate callgrind.out.20261 | less
callgrind_annotate --inclusive=yes --threshold=95 callgrind.out.20261 | less
callgrind_annotate --tree=calling callgrind.out.20261 | less

Useful ideas:

• Self cost: cost spent inside a function body itself.
• Inclusive cost: cost spent in the function plus everything it calls.
• Threshold: hides tiny entries so the report is easier to read.

If you install a GUI viewer:

kcachegrind callgrind.out.20261

or:

qcachegrind callgrind.out.20261

What Your Current Callgrind Output Is Saying

I inspected callgrind.out.20261 with callgrind_annotate --inclusive=yes --threshold=95.

Main takeaways from this run:

• almost all measured work comes from main calling RunMixed
• the biggest cost is on the read side inside leveldb::DBImpl::Get
• a large amount of work happens in memtable and skiplist lookup
• key comparison is expensive in this workload
• your own MakeKey(long) function is also surprisingly expensive
• writes are present, but reads dominate this mixed workload

Important hotspots from this run:

• RunMixed(...): about 96.86% inclusive cost
• leveldb::DBImpl::Get(...): about 48.59% inclusive cost
• SkipList::FindGreaterOrEqual(...): about 33.35% inclusive cost
• MemTable::Get(...): about 28.07% inclusive cost
• InternalKeyComparator::Compare(...): about 26.63% inclusive cost
• MakeKey(long): about 25.21% inclusive cost
• Version::Get(...): about 19.09% inclusive cost
• TableCache::Get(...): about 15.65% inclusive cost
• Table::InternalGet(...): about 14.67% inclusive cost
• DBImpl::Put(...): about 13.38% inclusive cost

This is a useful result already because it suggests two different optimization directions:

1. Application-side overhead In this workload app, MakeKey(long) is using stream formatting and costs a lot. That means part of the measured cost comes from the benchmark driver itself, not only from LevelDB internals.

2. LevelDB read-path overhead Skiplist lookup, memtable lookup, comparator work, version lookup, and table lookup are all significant. That means the random-read path is where deeper LevelDB investigation should start.

Practical Interpretation Of The Current Callgrind Run

For learning:

• this Callgrind run is good enough to show where the workload spends effort,
• it already shows that mixed random workloads are read-heavy in this setup,
• and it also shows that the local app can distort results if it does expensive key generation on every operation.

For fairer profiling:

• pre-generate keys before the loop,
• avoid std::ostringstream in the hot path,
• then rerun Callgrind and compare the new Ir totals and hotspot list.

That is exactly the kind of issue this project is meant to uncover.

Why Build From Source First

Use source builds as the main workflow and released binaries only as a comparison baseline.

Source build means compiling the program yourself from its code. This is the best choice because it gives you:

• Debug symbols: extra information in the binary that helps profilers show function names and line numbers.
• Compiler flags: build options such as -O2, -O3, or -g that affect speed, size, and debugging visibility.
• Reproducibility: the ability to rebuild the same code in the same way and compare runs fairly.
• Freedom to optimize: you can change algorithms, memory layout, locking, allocations, and build settings.

Released binary means a prebuilt executable downloaded from a project release page or package manager. It is useful only to answer questions like:

• Does my local build perform roughly like what real users install?
• Did I accidentally build with unusual settings?

Do not start by optimizing a binary directly unless your project is specifically about binary rewriting, reverse engineering, or compiler-level post-link optimization. For most practical software optimization work, source-level analysis is the right path.

Recommended Workflow

1. Choose a Small, Well-Known C++ Project

Start with a project that is respected, buildable, and small enough to understand in a few days.

Good first options:

• leveldb: a small key-value store from Google. Good if you want database-like performance work without the size of PostgreSQL or MySQL.
• re2: a fast regular expression engine. Good for CPU profiling and algorithmic behavior.
• fmt: a widely used formatting library. Good for string handling and microbenchmarks.
• nlohmann/json: a very popular JSON library. Good for parsing, memory, and API-heavy workloads.
• tinyxml2: a small XML parser. Good for parser and allocation analysis.

Best first choice if you want "database and systems" flavor: leveldb.

2. Fork the Project and Build It Locally

Fork means creating your own copy of a public repository so you can experiment safely without touching the original project.

Build locally means compiling the project on your own machine. This gives you control over the exact compiler and settings.

Recommended build style:

• Use a release build, because debug builds are often much slower and do not represent real performance.
• Keep debug symbols enabled if possible, because profilers become much more useful with symbols.

Typical idea:

• Release build: optimized for speed.
• Debug symbols: extra metadata for profiling and tracing.

In practice, many projects are best benchmarked with something close to:

-O3 -g

Meaning:

• -O3: asks the compiler to apply aggressive optimizations.
• -g: includes debug information so tools can map machine code back to source code.

If a project already documents its recommended release flags, follow the project docs first.

3. Create a Stable Benchmark Baseline

Baseline means the performance of the unmodified upstream version before you change anything.

This is important because optimization claims are weak unless you can compare:

• Before your change
• After your change
• Under the same conditions

Keep the benchmark setup stable:

• Use the same machine each time.
• Use the same input data each time.
• Use the same build settings each time.
• Run multiple iterations, not just one run.
• Avoid background noise from other heavy programs if possible.

4. Start With High-Level Benchmarking

High-level benchmarking measures the whole program or command, not just one small function.

Tool:

• hyperfine: a command-line benchmarking tool for measuring how long shell commands take.

Why it helps:

• It automates repeated runs.
• It reports timing statistics.
• It helps compare "before" and "after" commands cleanly.

Example:

hyperfine './my_program input.txt' './my_program_optimized input.txt'

Useful jargon:

• Wall-clock time: real elapsed time seen by a user.
• Mean time: average runtime across runs.
• Standard deviation: how much the runtimes vary. Lower variation usually means more reliable measurement.
• Warm-up: running a command before measurement so caches, files, and program startup effects are less misleading.

5. Measure Hardware Counters

After you know something is slow, measure lower-level CPU behavior.

Tool:

• perf stat: a Linux tool that reports hardware and kernel performance counters.

Example:

perf stat ./my_program input.txt

Common metrics:

• Cycles: rough measure of CPU work spent executing.
• Instructions: number of machine instructions executed.
• IPC: instructions per cycle. Higher is often better, but only in context.
• Cache misses: times the CPU could not find data in a fast cache and had to fetch it from slower memory.
• Branch misses: times the CPU predicted a branch incorrectly and had to recover.

Why this matters:

• If cache misses are high, memory access patterns may be the real problem.
• If instructions are high, the code may simply be doing too much work.
• If IPC is low, the CPU may be stalled waiting on memory or unpredictable branches.

6. Find Hotspots With a Profiler

Profiling means recording where the program spends time so you optimize the real bottlenecks instead of guessing.

Tools:

• perf record: records samples while the program runs.
• perf report: shows where time was spent.
• Flame graph tools: turn profiling data into an easy-to-read stacked graph of hot functions.
• valgrind --tool=callgrind: simulates execution and records function-level cost in great detail.

Examples:

perf record ./my_program input.txt
perf report

valgrind --tool=callgrind ./my_program input.txt

Useful jargon:

• Hotspot: a function or code path where a large amount of time is spent.
• Sampling profiler: a profiler that periodically checks where the program is executing. perf is an example.
• Instrumentation profiler: a profiler that records more explicit execution details, often with more overhead.
• Overhead: extra slowdown caused by the measurement tool itself.

General rule:

• Use perf first for realistic low-overhead profiling.
• Use callgrind when you want more detail and can tolerate slower runs.

7. Measure Memory Behavior

Many performance problems are memory problems, not raw CPU problems.

Tools:

• heaptrack: tracks heap allocations and shows where memory is allocated.
• valgrind --tool=massif: measures heap memory usage over time.

Why this matters:

• Too many allocations can slow down hot paths.
• High peak memory can reduce cache efficiency.
• Unfriendly memory layout can cause cache misses and poor locality.

Useful jargon:

• Allocation: requesting memory from the heap at runtime.
• Heap: dynamically allocated memory managed while the program runs.
• Stack: fast function-local memory managed automatically by function calls.
• Locality: how close related data is in memory. Better locality often improves cache behavior.

8. Use Project Benchmarks or Add Microbenchmarks

Microbenchmark means a small benchmark focused on one function or one narrow behavior rather than the whole program.

Tool:

• Google Benchmark: a C++ library for writing repeatable small-scale performance tests.

Why it helps:

• Good for measuring a specific parser, allocator path, loop, or data structure change.
• Useful after high-level profiling has already identified the area worth studying.

Be careful:

• Microbenchmarks are easy to misuse.
• A faster tiny benchmark does not always make the real application faster.

Best use:

• Use whole-program benchmarks first.
• Use microbenchmarks second, to zoom in on a known hotspot.

9. Change One Thing at a Time

When optimizing, avoid making many unrelated changes in one patch.

Why:

• You will not know which change actually helped.
• It becomes harder to explain results.
• It becomes harder to detect regressions.

A strong optimization experiment usually looks like this:

1. Measure upstream baseline.
2. Profile and identify one hotspot.
3. Make one targeted change.
4. Re-run tests.
5. Re-run benchmarks.
6. Write down the result and the tradeoff.

10. Validate Correctness After Every Optimization

A faster wrong answer is a bug, not an optimization.

Always run:

• Unit tests: small tests for individual parts.
• Integration tests: tests that check multiple parts working together.
• Existing project test suites.

If the project has no useful benchmarks, you may need to create your own workload and document it clearly.

Tools Summary

Benchmarking Tools

• hyperfine: measures command runtime repeatedly and compares variants.
• Google Benchmark: measures small focused C++ code paths.

Profiling Tools

• perf stat: reports counters such as cycles, instructions, cache misses, and branch misses.
• perf record: collects profiling samples while the program runs.
• perf report: displays the profile collected by perf record.
• Flame graph tools: visualize hot call stacks.
• callgrind: detailed function-level profiler through Valgrind.

Memory Tools

• heaptrack: shows where heap memory is allocated and how much is used.
• massif: shows memory growth and peak usage over time.

Key Jargon

• Benchmark: a repeatable performance test.
• Baseline: the original result before your changes.
• Throughput: how much work a system completes in a given time.
• Latency: how long one operation takes.
• Regression: a change that makes performance or correctness worse.
• Workload: the actual input, data, or request pattern used for testing.
• Release build: a build configured for optimization and realistic speed.
• Debug build: a build configured for easier debugging, usually slower.
• Symbol: metadata that lets tools map binary instructions to source functions and lines.
• Hot path: the code path executed most often or costing the most time.
• Contention: multiple threads competing for the same lock or resource.
• Vectorization: using CPU SIMD instructions to process multiple data elements at once.

What This Project Should Document

For each target project, record:

1. Project name and commit hash.
2. Build instructions and compiler version.
3. Benchmark workload and dataset.
4. Baseline numbers.
5. Profiling findings.
6. Optimization idea.
7. Result after change.
8. Tradeoffs, risks, and correctness checks.

Suggested First Targets

If the goal is to learn optimization work in a realistic but manageable way, start with one of these:

• leveldb: best first pick for storage-system style optimization.
• re2: best first pick for CPU and algorithm profiling.
• fmt: best first pick for focused library-level microbenchmarking.
• tinyxml2: best first pick for parser and allocation analysis.

Recommended First Project

Start with leveldb.

Why leveldb is a good first choice:

• It is well known.
• It is much smaller than a full database server.
• It has realistic performance questions around storage, caching, and data access.
• It is complex enough to be interesting but still possible to understand.

Short Practical Answer

For this project, the best workflow is:

1. Fork a small C++ project.
2. Build it locally from source.
3. Benchmark the original version.
4. Profile it using perf.
5. Optimize a single hotspot.
6. Re-test and compare against the baseline.

Use released binaries only as a secondary reference, not as the main thing you optimize.