Performance Optimization in C++

Algorithmic complexity is only part of performance. On real hardware, memory access patterns, branch predictability and what the compiler is allowed to do often matter as much. Every number on this page was measured on this lesson’s build machine — a 4-core Intel Xeon (AVX-512 capable) running GCC 13 — and timings vary from run to run; each block shows one representative run. Your numbers will differ; the ratios are the point.

All the benchmarks share this helper, which keeps each result so the optimizer can’t delete the work being timed:

// bench.h — a tiny timing helper shared by the examples
#pragma once
#include <chrono>
#include <iostream>

template <typename F>
auto bench(const char* name, F f) {
    auto t0 = std::chrono::steady_clock::now();
    auto result = f();                                      // keep the result so the
    auto t1 = std::chrono::steady_clock::now();             // optimizer can't drop the work
    std::cout << name << std::chrono::duration<double, std::milli>(t1 - t0).count()
              << " ms (result " << result << ")\n";
    return result;
}

Cache Locality: Array of Structs vs Struct of Arrays

Summing one field of ten million particles, stored two ways:

#include <vector>
#include "bench.h"

struct ParticleAoS { int x, y, z, vx, vy, vz, mass; };        // 28 bytes each
struct ParticlesSoA { std::vector<int> x, y, z, vx, vy, vz, mass; };

int main() {
    constexpr int N = 10'000'000;
    std::vector<ParticleAoS> aos(N, ParticleAoS{1, 2, 3, 4, 5, 6, 7});
    ParticlesSoA soa;
    for (auto* v : {&soa.x, &soa.y, &soa.z, &soa.vx, &soa.vy, &soa.vz, &soa.mass}) v->assign(N, 1);

    for (int rep = 0; rep < 2; ++rep) {                         // second round: warm
        bench("AoS sum of x: ", [&] { long long s = 0; for (const auto& p : aos) s += p.x; return s; });
        bench("SoA sum of x: ", [&] { long long s = 0; for (int x : soa.x) s += x; return s; });
    }
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o aos_soa aos_soa.cpp
$ ./aos_soa
AoS sum of x: 24.8125 ms (result 10000000)
SoA sum of x: 8.73628 ms (result 10000000)
AoS sum of x: 24.8812 ms (result 10000000)
SoA sum of x: 9.59187 ms (result 10000000)

Same data, same sum, roughly three times faster with the struct-of-arrays layout. Each ParticleAoS is 28 bytes, so the AoS loop pulls 28 bytes through the cache to use 4 of them, and its loads are strided. The SoA loop reads a dense array of ints: every byte of every cache line is used. GCC 13 does not vectorize this -O2 loop (the long long accumulator is an unsupported type for its cheap cost model), so the gain here is cache and memory bandwidth alone. Each variant runs twice; the second round is not faster here because the 280 MB of data doesn’t fit in any cache anyway.

Access Order

The same 64 MB grid summed row by row and column by column:

#include <vector>
#include "bench.h"

int main() {
    constexpr int N = 4096;                                  // 4096 x 4096 ints = 64 MB
    std::vector<int> grid(N * N, 1);
    for (int rep = 0; rep < 2; ++rep) {
        bench("row by row:       ", [&] {                    // consecutive addresses
            long long s = 0;
            for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) s += grid[r * N + c];
            return s;
        });
        bench("column by column: ", [&] {                    // jumps 16 KB every step
            long long s = 0;
            for (int c = 0; c < N; ++c) for (int r = 0; r < N; ++r) s += grid[r * N + c];
            return s;
        });
    }
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o traversal traversal.cpp
$ ./traversal
row by row:       13.0584 ms (result 16777216)
column by column: 189.76 ms (result 16777216)
row by row:       12.5287 ms (result 16777216)
column by column: 159.87 ms (result 16777216)

Identical arithmetic, but column order was more than ten times slower. Row order walks consecutive addresses, so each 64-byte cache line serves 16 ints and the hardware prefetcher streams ahead. Column order jumps 16 KB (4096 ints) per step, touching a new cache line — and often a new page — for every single element. Put the index that varies fastest in the inner loop.

Branch Prediction

The classic demonstration: sum the elements ≥ 128 of random data, then of the same data sorted.

#include <algorithm>
#include <random>
#include <vector>
#include "bench.h"

long long sum_big(const std::vector<int>& v) {
    long long s = 0;
    for (int x : v)
        if (x >= 128) s += x;                               // data-dependent branch
    return s;
}

int main() {
    std::mt19937 rng(1);
    std::vector<int> data(20'000'000);
    for (int& x : data) x = rng() % 256;
    std::vector<int> sorted = data;
    std::sort(sorted.begin(), sorted.end());
    for (int rep = 0; rep < 2; ++rep) {
        bench("random order: ", [&] { return sum_big(data); });
        bench("sorted:       ", [&] { return sum_big(sorted); });
    }
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o branch branch.cpp
$ ./branch
random order: 17.9188 ms (result 1915766795)
sorted:       18.8377 ms (result 1915766795)
random order: 18.3073 ms (result 1915766795)
sorted:       17.8684 ms (result 1915766795)

No difference — the famous effect doesn’t appear. GCC compiled if (x >= 128) s += x into a branchless conditional move (cmov), so there’s no branch to mispredict. To see what the CPU would otherwise pay, turn off that if-conversion:

$ g++ -std=c++20 -Wall -Wextra -O2 -fno-if-conversion -fno-if-conversion2 -fno-tree-vectorize -o branch branch.cpp
$ ./branch
random order: 100.006 ms (result 1915766795)
sorted:       19.7783 ms (result 1915766795)
random order: 99.8651 ms (result 1915766795)
sorted:       20.4916 ms (result 1915766795)

Now there’s a real branch, and on random data it goes the wrong way about half the time; each misprediction flushes the pipeline. Sorted, the branch is predictable (false for the first half, true for the second) and the loop runs several times faster. The lesson cuts both ways: unpredictable branches in hot loops are expensive, and the compiler often removes them for you — so measure before hand-writing “branchless” tricks. C++20’s [[likely]]/[[unlikely]] only influence code layout; they can’t make random data predictable.

Optimization Levels and -Ofast

One dot product of ten million floats, compiled five ways:

#include <vector>
#include "bench.h"

float dot(const std::vector<float>& a, const std::vector<float>& b) {
    float s = 0;
    for (std::size_t i = 0; i < a.size(); ++i) s += a[i] * b[i];
    return s;
}

int main() {
    std::vector<float> a(10'000'000, 0.1f), b(10'000'000, 2.0f);   // true answer: about 2,000,000
    bench("dot product: ", [&] { return dot(a, b); });
    bench("dot product: ", [&] { return dot(a, b); });
}

$ g++ -std=c++20 -O0 -o dot dot.cpp
$ ./dot
dot product: 49.3095 ms (result 2.17587e+06)
dot product: 53.3725 ms (result 2.17587e+06)
$ g++ -std=c++20 -O2 -o dot dot.cpp && ./dot
dot product: 12.4347 ms (result 2.17587e+06)
dot product: 14.0873 ms (result 2.17587e+06)
$ g++ -std=c++20 -O3 -march=native -o dot dot.cpp && ./dot
dot product: 15.7745 ms (result 2.17587e+06)
dot product: 15.224 ms (result 2.17587e+06)
$ g++ -std=c++20 -Ofast -o dot dot.cpp && ./dot
dot product: 8.72753 ms (result 1.9512e+06)
dot product: 9.17487 ms (result 1.9512e+06)
$ g++ -std=c++20 -Ofast -march=native -o dot dot.cpp && ./dot
dot product: 6.70778 ms (result 2.02158e+06)
dot product: 6.23026 ms (result 2.02158e+06)

Two surprises. First, -O3 -march=native was no faster than -O2: a floating-point sum must be computed in source order, because float addition isn’t associative, so the compiler can’t split it across SIMD lanes. -Ofast enables -ffast-math, which permits that reordering — and the loop got faster, roughly twice as fast once -march=native allowed wider vectors. Second, look at the results. The true answer is about 2,000,000; the in-order float sum drifted to 2,175,870 because once the running total is large, each added 0.2 is rounded; -Ofast produced different wrong answers because it sums in a different order. -Ofast is only safe when your code tolerates changed floating-point results — here, accumulating in double would fix the accuracy regardless of flags.

Two whole-program options go further: LTO (-flto) lets the optimizer inline across .cpp files, and PGO (-fprofile-generate, run with representative input, then rebuild with -fprofile-use) feeds real branch frequencies back into the compiler.

Profiling: Find the Hot Spot First

Guessing where time goes is usually wrong. gprof is the simplest profiler — compile with -pg, run, then read the report:

#include <cmath>
#include <iostream>
#include <vector>

__attribute__((noinline)) bool is_prime(int n) {           // the deliberate hot spot
    if (n < 2) return false;
    for (int d = 2; d * d <= n; ++d)
        if (n % d == 0) return false;
    return true;
}

__attribute__((noinline)) std::vector<int> make_inputs(int n) {
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i;
    return v;
}

__attribute__((noinline)) long long sum_sqrt(const std::vector<int>& v) {
    double s = 0;
    for (int x : v) s += std::sqrt(x);
    return static_cast<long long>(s);
}

int main() {
    auto inputs = make_inputs(3'000'000);
    int primes = 0;
    for (int x : inputs) primes += is_prime(x);
    std::cout << primes << " primes, sqrt sum " << sum_sqrt(inputs) << "\n";
}

$ g++ -std=c++20 -O2 -pg -o hotspot hotspot.cpp
$ ./hotspot
216816 primes, sqrt sum 3464100748
$ gprof -b -p hotspot gmon.out | head -8
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 98.39      0.61     0.61  3000000     0.00     0.00  is_prime(int)
  1.61      0.62     0.01        1    10.00    10.00  sum_sqrt(std::vector<int, std::allocator<int> > const&)
  0.00      0.62     0.00        1     0.00     0.00  make_inputs(int)

The flat profile answers the only question that matters: 98% of the time is in is_prime, called three million times. sum_sqrt and make_inputs are noise; optimizing them would be wasted effort. (noinline keeps the functions visible as separate entries; with inlining, their time would be charged to main.) gprof’s sampling is coarse — 0.01 s per sample — so it suits programs that run for at least a second. On Linux, perf record -g ./app and perf report give lower-overhead sampling with call graphs, and valgrind --tool=callgrind counts instructions exactly at a large slowdown.

SIMD: Auto-Vectorization vs Intrinsics

SIMD instructions process several values at once — AVX2 adds eight floats per instruction. The same array addition written three ways:

#include <immintrin.h>
#include <vector>
#include "bench.h"

__attribute__((noinline, optimize("no-tree-vectorize")))
void add_scalar(const float* a, const float* b, float* out, int n) {     // one float at a time
    for (int i = 0; i < n; ++i) out[i] = a[i] + b[i];
}

__attribute__((noinline))
void add_auto(const float* a, const float* b, float* out, int n) {       // compiler's choice
    for (int i = 0; i < n; ++i) out[i] = a[i] + b[i];
}

__attribute__((noinline))
void add_avx2(const float* a, const float* b, float* out, int n) {       // 8 floats per add
    int i = 0;
    for (; i + 8 <= n; i += 8)
        _mm256_storeu_ps(out + i, _mm256_add_ps(_mm256_loadu_ps(a + i), _mm256_loadu_ps(b + i)));
    for (; i < n; ++i) out[i] = a[i] + b[i];                               // leftovers
}

int main() {
    const int n = 4096;                                                    // fits in L1/L2 cache
    std::vector<float> a(n, 1.5f), b(n, 2.5f), out(n);
    auto run = [&](auto fn) { return [&, fn] { for (int r = 0; r < 100'000; ++r) fn(a.data(), b.data(), out.data(), n); return out[n - 1]; }; };
    for (int rep = 0; rep < 2; ++rep) {
        bench("scalar:          ", run(add_scalar));
        bench("auto-vectorized: ", run(add_auto));
        bench("AVX2 intrinsics: ", run(add_avx2));
    }
}

$ g++ -std=c++20 -Wall -Wextra -O2 -mavx2 -o simd simd.cpp
$ ./simd
scalar:          144.385 ms (result 4)
auto-vectorized: 137.918 ms (result 4)
AVX2 intrinsics: 33.167 ms (result 4)
scalar:          145.603 ms (result 4)
auto-vectorized: 144.602 ms (result 4)
AVX2 intrinsics: 36.3173 ms (result 4)

The hand-written AVX2 version was four to five times faster, and the “auto-vectorized” function was no faster than the deliberately scalar one. The compiler can explain why:

$ g++ -std=c++20 -O3 -mavx2 -fopt-info-vec-optimized -o simd simd.cpp 2>&1 | grep 'simd.cpp:12'
simd.cpp:12:23: optimized: loop vectorized using 32 byte vectors
simd.cpp:12:23: optimized:  loop versioned for vectorization because of possible aliasing
simd.cpp:12:23: optimized: loop vectorized using 16 byte vectors
$ ./simd
scalar:          161.767 ms (result 4)
auto-vectorized: 48.7455 ms (result 4)
AVX2 intrinsics: 35.9435 ms (result 4)
scalar:          154.701 ms (result 4)
auto-vectorized: 38.4352 ms (result 4)
AVX2 intrinsics: 38.8945 ms (result 4)

At -O2, GCC 13 uses a “very cheap” vectorization cost model that won’t vectorize a loop needing extra code around it — here a runtime check that out doesn’t overlap a or b, and a scalar epilogue for an n that may not be a multiple of the vector width. At -O3 it versions the loop (vector path when the arrays don’t alias, scalar fallback when they do) and uses 32-byte AVX vectors — and now the plain C++ loop runs in the same range as the intrinsics (this machine’s timings are noisy between rounds, but both are several times faster than scalar). Ask the compiler with -fopt-info-vec before reaching for <immintrin.h>; intrinsics are non-portable and need -mavx2 (or a runtime CPU check) to run at all.

Avoiding Unnecessary Copies

Copies are the most common slowdown in code that looks fine:

#include <string>
#include <vector>
#include "bench.h"

__attribute__((noinline)) std::size_t by_value(std::string s)      { return s.size(); }
__attribute__((noinline)) std::size_t by_cref(const std::string& s) { return s.size(); }

int main() {
    const std::string text(1000, 'x');                         // too long for SSO: heap
    bench("string by value: ", [&] { std::size_t t = 0; for (int i = 0; i < 1'000'000; ++i) t += by_value(text); return t; });
    bench("string by const&:", [&] { std::size_t t = 0; for (int i = 0; i < 1'000'000; ++i) t += by_cref(text); return t; });

    auto fill = [](bool reserve) {
        std::vector<int> v;
        if (reserve) v.reserve(10'000'000);
        int reallocations = 0;
        auto cap = v.capacity();
        for (int i = 0; i < 10'000'000; ++i) {
            v.push_back(i);
            if (v.capacity() != cap) { ++reallocations; cap = v.capacity(); }
        }
        return reallocations;
    };
    bench("push_back, no reserve (reallocations): ", [&] { return fill(false); });
    bench("push_back, reserve    (reallocations): ", [&] { return fill(true); });
}

$ g++ -std=c++20 -Wall -Wextra -O2 -o copies copies.cpp
$ ./copies
string by value: 20.0991 ms (result 1000000000)
string by const&:4e-05 ms (result 1000000000)
push_back, no reserve (reallocations): 99.8091 ms (result 25)
push_back, reserve    (reallocations): 39.3997 ms (result 0)

Passing a 1000-character string by value a million times meant a million heap allocations and copies; by const&, the loop cost almost nothing (the compiler reduced it to arithmetic). Filling a vector without reserve reallocated 25 times — each time moving every element to a bigger buffer — and took well over twice as long as the single-allocation version. For false sharing between threads, see the concurrency lesson; for parallel algorithms, the STL algorithms lesson.

Practice

1. Change the accumulator in dot.cpp from float to double and rerun the five builds. What happens to the results and to the timings?

   Solution

   Every build now prints about 2e+06: a double has enough precision that adding 0.2 to a running total of two million loses nothing visible. -Ofast still reorders the sum, but the reordering no longer changes the printed result. The -O2 timing barely changes — the loop is still one dependent add per element.

2. In traversal.cpp, make the column-order loop faster without changing the loop order, by changing the data layout.

   Solution

   Store the grid transposed: index it as grid[c * N + r], filling it the same way. Now the inner loop over r walks consecutive addresses and runs as fast as the row-order version did. Layout and loop order must agree; either can be changed to match the other.

3. Profile hotspot.cpp again after changing is_prime to skip even divisors (d = 3; d += 2, with a separate check for 2). How much of the total does it still take?

   Solution

   It is still the hot spot — typically still over 90% of samples — but the total time roughly halves. The profile tells you where to work, not when to stop; stop when the whole program is fast enough.

4. Add __restrict to the pointer parameters of add_auto (const float* __restrict a, and so on) and rebuild at -O2 with -fopt-info-vec-optimized. What changes?

   Solution

   Nothing, on GCC 13: -fopt-info-vec-optimized still prints nothing for line 12 and the timing stays scalar. Removing the aliasing check wasn’t enough, because the -O2 cost model also refuses the scalar epilogue an unknown n requires. Adding -fvect-cost-model=dynamic (the model -O3 uses) vectorizes the __restrict version without any versioning. __restrict is a promise, and breaking it — passing overlapping arrays — is undefined behavior.

5. In copies.cpp, add a third variant that takes std::string_view and time it against const std::string&.

   Solution

   __attribute__((noinline)) std::size_t by_view(std::string_view s) { return s.size(); }

   It performs like const&: a string_view is a pointer and a length, built from text without allocating. Its advantage is accepting literals and substrings without creating a std::string first.