C++ Interview Prep · Part 3
For optimization-focused roles: the memory hierarchy, data layout, branches, vectorization, allocation, compiler behavior, and — above all — measurement. Traps ⚠️, one-liners 💬.
Modern optimization is mostly about one fact: CPUs got fast; memory didn't keep up. A core can execute 4+ instructions per cycle at ~4–5 GHz, but a trip to main memory stalls it for hundreds of instruction slots. Approximate numbers to carry in your head (they anchor every argument you'll make in an interview):
| Operation | Latency | ≈ scaled to human time (1 cycle = 1 s) |
|---|---|---|
| Register / simple ALU op | ~0.25–1 ns | seconds |
| L1 cache hit | ~1 ns (4–5 cycles) | seconds |
| L2 cache hit | ~4 ns (~14 cycles) | ~15 s |
| L3 cache hit | ~15–40 ns | a minute or two |
| Main memory (RAM) | ~60–100 ns | minutes |
| Branch misprediction | ~15–20 cycles | ~20 s |
| Mutex lock/unlock, uncontended | ~20–50 ns | a minute |
| NVMe SSD read | ~20–100 µs | days |
| Same-datacenter network round trip | ~500 µs | a week |
Numbers vary by hardware — what matters is the ratios: RAM is ~100× L1; disk is ~1000× RAM. One cache miss costs the same as dozens of arithmetic operations, so an algorithm that does more work on resident data routinely beats one that does less work with scattered access. That single inversion of intuition explains most of this guide.
vector<unique_ptr<T>>) defeats it completely, because the next address isn't known until the current load finishes."List has O(1) insert, vector has O(n) — when is the vector still faster?" Almost always at realistic sizes: traversing to the insertion point costs a cache miss per node (~100 ns each), while the vector's shift is a sequential memmove streaming at GB/s with the prefetcher's help. Vectors also have no per-node allocation or 16-byte pointer overhead. Real answer interviewers want: "measured crossover points are surprisingly large; default to vector, use a list only when iterator stability or splicing is the requirement."
// C++ 2D arrays are row-major: m[i][j] and m[i][j+1] are adjacent bytes.
for (i...) for (j...) sum += m[i][j]; // sequential: ~1 miss per 16 ints
for (j...) for (i...) sum += m[i][j]; // stride = row length: miss per ACCESS
// Same operation count. 5–20x runtime difference at sizes past L2.The grown-up version of this answer is loop tiling/blocking: process the data in sub-blocks that fit in cache (the classic matrix-multiply optimization). Name it; deriving it live is rarely required.
Three ways to store N objects, ranked by cache behavior for field-wise processing (AoS = array of structures; SoA = structure of arrays):
// AoS — array of structures: whole objects contiguous
struct Particle { float x, y, z, mass; };
std::vector<Particle> ps;
// SoA — structure of arrays: one contiguous array per field
struct Particles { std::vector<float> x, y, z, mass; };
// pointer soup — contiguous pointers, scattered objects (worst)
std::vector<std::unique_ptr<Particle>> pps;mass: in AoS every 64-byte line carries 48 bytes of x/y/z you didn't ask for — 75% of memory bandwidth wasted. In SoA, mass values are packed: every byte fetched is useful, and the loop vectorizes trivially.std::variant, before pointers.struct Bad { char c; double d; char c2; }; // 24 bytes (7 + 6 bytes padding)
struct Good { double d; char c, c2; }; // 16 bytes — just reorderedalignas(64) pins an object to a cache-line boundary — the tool for false sharing (§8).Object size is the numerator of every cache argument: 64-byte lines ÷ sizeof(T) = objects per line, so shrinking a struct from 24 to 16 bytes is a 33% cut in memory traffic for every loop that touches it — without changing a single loop. Being able to compute sizeof by hand is table stakes for an optimization role.
alignof (fundamentals: alignment = size; a struct's alignment = its strictest member's). Gaps inserted to get there are padding.T arr[N], element 1 is also aligned. That's the whole reason tail padding exists.struct Order { // alignment 8 (double)
bool urgent; // offset 0
// 7 bytes padding (price needs offset % 8 == 0)
double price; // offset 8
int qty; // offset 16
bool flagged; // offset 20
}; // 21 -> tail-pad to 24. sizeof = 24
struct Order2 { // same members, descending alignment
double price; // 0
int qty; // 8
bool urgent; // 12
bool flagged; // 13
}; // pad to 16. sizeof = 16 — 33% smaller, freeEmpty arr[10] needs 10 addresses.struct D : Empty { int x; }; is 4 bytes, while struct C { Empty e; int x; }; is 8 (the member must get its own address; 1 byte + 3 padding). This is exactly how unique_ptr stores its stateless default deleter for free and why it's pointer-sized. C++20's [[no_unique_address]] gets the same effect for members (caveat: MSVC ignores the standard spelling for ABI reasons).uint32_t flags : 3;) pack multiple fields into one integer: big size wins for flag-heavy structs, paid for with read-modify-write access, no address-of, and ABI-varying layout. Fine within one codebase; avoid on wire formats you don't control both ends of.alignof is the placement constraint, sizeof the footprint. alignas(64) over-aligns (per-thread data on its own cache line — the false-sharing fix, §9); since C++17, new honors over-alignment.Packing removes padding by allowing misaligned members. Costs: slower (sometimes split) loads on x86, faults on some ARM configurations, broken atomics, and taking a pointer/reference to a misaligned member is a portability landmine. Legitimate use: matching an on-disk or on-wire format — and even then, prefer memcpy into a properly aligned struct at the boundary. If asked "how do I shrink this struct," the answer is reorder, split hot/cold, bitfield — not pack.
| Type | Typical size | Why |
|---|---|---|
T*, reference, unique_ptr<T> | 8 | one pointer; stateless deleter via EBO |
shared_ptr / weak_ptr | 16 | object pointer + control-block pointer |
std::vector | 24 | begin / end / capacity pointers |
std::string | 32 (libstdc++) / 24 (libc++) | SSO buffer folded into the object |
std::optional<double> | 16 | payload + bool, padded to payload's alignment |
std::variant<int, double> | 16 | largest alternative + discriminant + padding |
std::mutex | 40 (Linux/glibc) | wraps pthread_mutex_t — why per-object mutexes bloat |
std::function | 32–64 (varies) | type erasure + small-callable buffer |
Exact numbers vary by standard library and platform — quote them as "typical on 64-bit with the Itanium ABI (application binary interface)" and you're both useful and safe.
static_assert(sizeof(Order) == 16); in the codebase — layout regressions become compile errors. Same for alignof and offsetof when a layout is load-bearing.-Wpadded (noisy but reveals every hole), pahole (Linux, from dwarves: prints each struct with its holes and cache-line boundaries — the professional's tool), and Compiler Explorer for quick checks.// sum only elements >= 128, over random bytes:
for (int x : data) if (x >= 128) sum += x;
// SORTED data: ~5x faster than unsorted. Same elements, same total work —
// sorted input makes the branch predictable (all-false then all-true).sum += (x >= 128) ? x : 0; // often compiles to cmov / arithmetic — no branch
int mx = std::max(a, b); // compilers emit cmov for simple selects
mask = -(x >= 128); sum += x & mask; // manual mask trick, same idea[[likely]]/[[unlikely]] (C++20) hint code placement (hot path falls through, cold path jumps away) — modest effect, mostly about instruction-cache layout, not the predictor.// One accumulator: every add waits on the previous one (dependency chain)
for (i) sum += a[i];
// Four accumulators: four independent chains run in parallel on one core
for (i += 4) { s0 += a[i]; s1 += a[i+1]; s2 += a[i+2]; s3 += a[i+3]; }
sum = s0 + s1 + s2 + s3; // often 2–4x, no threads involvedA modern core is superscalar (executes several instructions per cycle) and out-of-order (runs whatever's ready). What limits it is dependency chains — each instruction waiting on the last one's result. Breaking a reduction into independent accumulators is the canonical fix. (Compilers do this for integer sums; for floats they need -ffast-math-style permission, because FP addition isn't associative.) ⚠️
-O2/-O3) works when the loop is: contiguous unit-stride access, known trip count shape, no cross-iteration dependencies, no unpredictable branches, no aliasing ambiguity. This is why SoA layout and simple loops matter — they're what the vectorizer can digest.dst and src don't overlap, it must assume they might, and won't vectorize. Fixes: __restrict, local copies, or std algorithms. Check what actually happened with -Rpass=loop-vectorize (Clang) / -fopt-info-vec (GCC), or read the assembly on Compiler Explorer (godbolt.org)._mm256_add_ps...) or libraries (std::experimental::simd, Highway, xsimd). In an interview, say you'd exhaust layout + auto-vectorization first — intrinsics are a maintenance tax you pay knowingly.reserve(): a vector growing to 1M elements without reserve does ~20 geometric reallocations, each copying/moving everything. One reserve(1'000'000) removes all of it. Cheapest optimization in the language.std::string stores short strings (≤15 chars in libstdc++/libc++) inside the string object itself, no heap at all. Consequences: short-string code is allocation-free; moving a string is not always "free pointer steal" (SSO strings copy their bytes); and keys under 16 chars in a map are cheaper than people think.std::pmr::monotonic_buffer_resource (pmr = polymorphic memory resources), custom bump allocators. The per-frame arena is the canonical game-engine pattern — allocate all frame-lifetime data in it, reset the pointer at frame end.emplace_back vs push_back (construct in place, skip a temporary), string_view to avoid copies, moving instead of copying containers.-O0 debug (nothing optimized — never benchmark this ⚠️), -O1, -O2 the production default (inlining, vectorization, unrolling...), -O3 more aggressive vectorization/unrolling, -Os optimize for size. -march=native unlocks the current CPU's instruction sets (AVX2 etc.) — without it, binaries target a lowest common denominator.std::sort (vs a function pointer to qsort), and templates optimize so well — the compiler sees through them.i+1 > i folds to true, loops vectorize), pointers of unrelated types don't alias (strict aliasing). UB is the license for a whole tier of optimization. Corollary: sanitizers (-fsanitize=address,undefined) in debug, because optimized UB does surprising things.alignas(64) per-thread data:struct Counters {
alignas(64) std::atomic<long> a; // each on its own cache line
alignas(64) std::atomic<long> b;
};
// std::hardware_destructive_interference_size = the portable "64"Everything above is hypothesis-generation. Measurement is the actual job, and interviewers for optimization roles probe it harder than any mechanism. The discipline:
perf (Linux — perf record/perf report, perf stat for counters like cache-misses, branch-misses, IPC), Intel VTune, Instruments (macOS), flame graphs for visualization.malloc → §6.// Google Benchmark skeleton — the standard tool
static void BM_Sum(benchmark::State& st) {
auto v = make_data();
for (auto _ : st) {
auto s = sum(v);
benchmark::DoNotOptimize(s); // stop the as-if rule deleting the loop
}
}DoNotOptimize); everything fit in cache during the benchmark but won't in production; the benchmark ran during CPU frequency ramp-up (warm up first, lock frequency); you benchmarked -O0; you measured wall time on a noisy machine once instead of distributions across runs.| Symptom / question | Answer sketch |
|---|---|
| Column-wise 2D loop slow | Row-major layout → stride = row length → miss per access. Swap loop order; tile if both orders are needed. |
| Same loop, sorted input 5× faster | Branch predictor. Sorted → predictable. Fix for random: branchless select. |
| vector<unique_ptr<Base>> hot loop | Pointer chase per element + indirect call. Per-type vectors, variant, or sort by type. |
| Threads made it slower | False sharing (pad/alignas), contention (shard), or tasks too small (batch). Check with perf counters. |
| Slower after "removing work" with a helper in another .cpp | Killed inlining across the translation unit boundary. Header/inline it or enable LTO. |
| map vs unordered_map vs sorted vector | unordered_map O(1) but hashing + a pointer chase per bucket; map = pointer chase per level; sorted vector + lower_bound is often fastest to iterate/search at moderate sizes — contiguity beats asymptotics. Measure. |
| Loop won't vectorize | Aliasing, non-unit stride, or a data-dependent branch. __restrict, SoA, hoist the branch; verify with -Rpass/-fopt-info. |
| String-heavy code slow | Allocations (reserve, SSO awareness, string_view), and hashing costs in unordered containers. |
Answer pattern for all of them: name the hardware mechanism → state the fix → say how you'd confirm with a measurement. Mechanism–fix–measurement is the three-beat answer that reads as "has done this professionally."