TopolearnModern CPUs are limited by memory far more than arithmetic; data layout often decides performance more than algorithms do.
Rule one: measure. Build with optimisations (-O2, plus -march=native and link-time optimisation -flto where suitable), profile with perf, VTune or Instruments, and microbenchmark with a library like Google Benchmark that stops the optimiser deleting your test. Intuition about performance is wrong surprisingly often.
Rule two: memory dominates. A main-memory access costs on the order of 100 ns, versus about 1 ns for L1 cache. The CPU fetches 64-byte cache lines and prefetches sequential access patterns. So:
- Prefer contiguous containers. Iterating a
std::vectoris typically several times faster than astd::listorstd::mapof the same size, because every node hop can be a cache miss. Sorted vectors and flat maps often beat trees and hash tables for small and medium sizes. - Lay out data for how it's accessed. If a loop touches only positions, a structure of arrays (separate
x,y,zvectors) keeps the cache full of useful bytes, where an array of structures drags whole objects in. Keep hot fields together and cold ones elsewhere. - Avoid false sharing: two threads writing different variables on the same cache line ping-pong it between cores. Pad per-thread data with
alignas(std::hardware_destructive_interference_size)(or 64).
Rule three: don't do needless work. reserve() before filling vectors; pass by const& or string_view; move instead of copying; avoid std::function and virtual calls in the hottest loops when templates or std::variant will do; keep allocation out of inner loops (use arenas, see allocators).
Branch mispredictions cost about 15 cycles; branch-free code and sorted data help, and C++20's [[likely]] / [[unlikely]] are hints. Finally, check the generated assembly (Compiler Explorer) to confirm the optimiser did what you expect.
Example
#include <chrono>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>
template <typename F>
long long time_us(F f) {
auto t0 = std::chrono::steady_clock::now();
f();
auto dt = std::chrono::steady_clock::now() - t0;
return std::chrono::duration_cast<std::chrono::microseconds>(dt).count();
}
int main() {
const int n = 5'000'000;
std::vector<int> vec;
vec.reserve(n); // one allocation instead of ~30
for (int i = 0; i < n; ++i) vec.push_back(i % 7);
std::list<int> lst(vec.begin(), vec.end()); // same data, one node per element
long long sum = 0;
auto tv = time_us([&] { sum += std::accumulate(vec.begin(), vec.end(), 0LL); });
auto tl = time_us([&] { sum += std::accumulate(lst.begin(), lst.end(), 0LL); });
std::cout << "vector " << tv << " us, list " << tl << " us, sum " << sum << '\n';
// build with -O2: the list is typically several times slower (pointer chasing)
}Remember
- Measure optimised builds with a profiler before changing anything
- Contiguous, sequential data wins: cache misses cost ~100x a cache hit
- Avoid needless allocations and copies; pad per-thread data against false sharing
Watch out for
- Micro-optimising arithmetic while the real cost is cache misses from pointer-heavy data structures.