Container Performance and the Cost of the Wrong Choice

Part I · Module 19 · Chapter 19.8 · Container Performance and the Cost of the Wrong Choice

1. The Headline Measurement

A million ints, summed. Three containers, identical arithmetic, identical operation count.

std::vector<int> v(N); std::iota(v.begin(), v.end(), 1);
std::deque<int>  d(v.begin(), v.end());
std::list<int>   l(v.begin(), v.end());

double tv = bench([&]{ s = 0; for (int x : v) s += x; sink(s); }, 7);

vector   0.09 ns/el [ 0.08- 0.17]   (1.00x)
deque    0.61 ns/el [ 0.59- 0.85]   (7.81x vector)
list     2.50 ns/el [ 2.37- 3.07]   (28.9x vector)

Roughly twenty-nine times. Same million additions, same long long accumulator, same compiler, same flags. The only difference is where the next element is.

Two notes on the figures before any of them are used. Every number in this chapter is a median of nine timed repetitions, with the bracketed range from the same nine. And they were taken on a working development machine under ordinary load, which is why §10 insists on the distinction that matters here: the absolute per-element times move with load — the vector figure ranged from 0.07 to 0.20 ns/element across runs on different days — while the ratios reproduce. Across sixteen whole-process runs the list-to-vector ratio stayed between 27× and 37×. So the ratios are the findings; treat the absolutes as the scale, not as constants.

Note sink(s) in the harness. Without a barrier the optimiser deletes the entire loop, since nothing observes the result, and the measurement becomes a measurement of nothing:

template <typename T>
static inline void sink(const T& x) { asm volatile("" :: "r,m"(x) : "memory"); }

Now: a 35× figure invites exactly one reaction, which is to repeat it as "linked lists are thirty-five times slower than vectors." That claim is not supported by this measurement, and §3 is why.

2. Why Contiguity Is Fast

Three mechanisms, and they compound.

Cache lines. Memory moves between RAM and the CPU in fixed-size blocks — 64 bytes on most hardware, 128 on Apple silicon. Reading one int from a std::vector brings in the next fifteen or thirty-one for free. The subsequent iterations hit cache. A std::list node is 24 bytes (Chapter 19.4 §3) and separately allocated, so one cache line may hold one useful node and some of a neighbour's bookkeeping.

Prefetching. The hardware detects sequential access and begins fetching ahead of the program. A contiguous traversal is the pattern prefetchers are designed for and they predict it perfectly. A pointer chase cannot be predicted, because the address of the next element is not known until the current one has arrived — a dependent load, where the latency cannot be hidden by overlapping it with anything.

Vectorisation. A contiguous loop over a trivially copyable type can be rewritten by the compiler to use SIMD instructions that process four or eight elements at once. This requires knowing the elements are adjacent, so it is available to vector and array and to nothing else.

That third mechanism is the one that makes §1's number misleading, because it is not a memory effect at all.

3. Decomposing the Thirty-Fold Gap

If a measurement is reported as one number, it should be one effect. §1's is not, and the way to find out is to remove one mechanism and re-measure.

The sum in §1 is vectorisable. Replacing it with a loop carrying a serial dependence — each step needs the previous result — denies SIMD to every container equally, while leaving the memory access pattern completely unchanged:

// A: vectorisable
for (int x : v) s += x;
// B: not vectorisable - each step depends on the last
long long a = 1; for (int x : v) { a = (a*31 + x) & 0xFFFFFFF; }

A. a VECTORISABLE sum
     vector  0.06 [0.04-0.06]  deque  0.43  list  1.66 [1.32-1.83]  ns/el
     list/vector = 29x        (range across runs: 28x - 33x)

B. the SAME traversal made non-vectorisable (a serial dependence per element)
     vector  1.53 [1.25-1.65]  deque  1.62  list  1.62 [1.42-1.87]  ns/el
     list/vector = 1.2x       (range across runs: 1.0x - 1.4x)

The gap collapses from about 29× to about 1.2×, and the ranges do not come close to overlapping, so this is a real effect rather than noise.

Read the columns rather than the ratio, because the ratio alone misleads in the other direction now. The list barely moved: 1.66 to 1.62 ns, the same within its range. The vector went from 0.06 to 1.53 ns — roughly twenty-five times slower. What happened is that the serial dependence made the loop latency-bound on the arithmetic, at about 1.5 ns per element, and that per-element cost is now large enough to hide the memory difference entirely.

So §1's 29× was mostly SIMD. The honest decomposition: on a vectorisable traversal of a freshly-built container, almost all of the advantage is vectorisation, and the memory layout contributes a small remainder.

That is a real and useful result — most hot loops over numeric data are vectorisable, so the advantage is usually available — but it is a different claim from "pointer chasing is thirty-five times slower," and a chapter that reported the first number without the second would have established a plausible falsehood. Chapter 19.4 §6's find-then-insert measurement has the same structure: it is a genuine ~4.4× that would be wrong to attribute to a single cause.

Which leaves the question of what the memory layout is worth, measured on its own.

4. Isolating the Layout Effect

To measure layout alone, every other variable has to be held constant: the container type, the element type, the element count, the operation, the complexity, and the compiler's treatment of the loop. The way to do that is to compare a std::list against another std::list whose nodes are in different places.

std::list<int> seq(v.begin(), v.end());        // nodes allocated front to back

std::list<int> scat;
{
    std::vector<int> order(N); std::iota(order.begin(), order.end(), 1);
    std::mt19937 rng(7); std::shuffle(order.begin(), order.end(), rng);
    for (int x : order) scat.push_back(x);     // allocation order = shuffled
    scat.sort();                               // relink into value order
}

Both lists end up holding 1 to 1,000,000 in order and traverse with the same code. The difference is that seq's nodes were allocated in the order they are visited, and scat's were allocated in a shuffled order and then relinked into visiting order.

The construction depends entirely on list::sort relinking nodes rather than moving values between them, so that was verified three independent ways before the measurement was trusted:

5 of 5 addresses still hold their original value
allocs=0 frees=0
list::sort of 5 elements     ctor=0 copy=0 move=0 dtor=0

Every address kept its original value, nothing was allocated, and no element was copied or moved. The sort rearranged links; the nodes stayed where the allocator put them.

The measurement:

C. list nodes allocated in order vs SHUFFLED in memory
     nodes in allocation order   2.62 ns/el   range   2.04 -   3.01
     nodes scattered           150.36 ns/el   range 116.09 - 187.14
     scattered / sequential       ~60x        (range across runs: 51x - 68x)
     identical container, identical O(n): only the ADDRESSES differ

About sixty times. Same container type, same element type, same million elements, same traversal, same complexity, same instructions. The only variable is where the nodes sit, and it is worth a factor of roughly sixty — more than double the 29× that §1's cross-container comparison suggested, and attributable to nothing else. The two collections of runs behind that figure gave medians of 58× and 61×, with no run below 45×.

This is the chapter's real headline. And it explains why §3's freshly-built list did so well: its nodes had just been allocated consecutively, so it was effectively a contiguous traversal wearing a linked list's interface. A list in a long-lived program — inserted into, erased from, its nodes interleaved with other allocations — looks like the 150 ns row, not the 2.6 ns one.

5. Memory Is Bandwidth

1e6 ints in a vector    = 3906.2 KB payload, 1 allocation
1e6 ints in a list      = 3906.2 KB payload in 1000000 nodes of 24 B = 23437.5 KB
a list therefore touches 6.0x the memory to carry the same data

The payload is identical. The list occupies six times as much, because 20 of every 24 bytes are pointers and padding, and every one of those bytes has to travel through the same cache hierarchy as the data.

So a traversal of the list moves six times the bytes to do the same arithmetic, which is a cost on top of the latency in §4. At 3.8 MB the vector exceeds a typical L2 cache and streams from L3 or memory; at 22.9 MB the list exceeds most L3 caches as well.

The same arithmetic applies to the associative containers. Chapter 19.5 §8 measured a map<int,int> node at 40 bytes for an 8-byte pair — five times the payload — and the lookup consequence is §6.

6. Lookup: Three Containers, One Complexity Class Apart

100,000 keys, 200,000 random lookups, three strategies.

map (RB tree)    153.7 ns/lookup [ 132.8- 198.5]  (~47x hash)
unordered_map      3.3 ns/lookup [   2.7-   6.1]  (1.00x)
sorted vector     80.0 ns/lookup [  66.7- 102.7]  (~23x hash)
map / sorted-vector = 1.9x at IDENTICAL O(log n)   (range 1.5x - 2.9x)

Two results, and the second is the one that indicts the complexity table.

The hash is roughly 47× the tree — 45× and 49× in the two collections of runs. That is expected in direction — O(1) against O(log n) — though the magnitude is larger than the notation suggests, because at n = 100,000 the tree does about 17 comparisons and the hash does one, and 47 is far more than 17. The extra factor is the tree's 17 dependent loads against the hash's single lookup.

The sorted std::vector beat the std::map by about 1.9×, and both are O(log n). Identical complexity, identical algorithm — a binary search over sorted keys — and the vector is nearly twice as fast. The difference is entirely layout: the vector's binary search touches log n positions in one contiguous block, and the last few probes fall within the same cache lines; the tree's descent follows log n pointers to nodes the allocator placed independently, each one a dependent load that cannot be prefetched because its address was not known until the previous load returned.

This is the measurement Chapter 19.1 §4 promised and the reason that chapter insisted complexity filters rather than ranks. The notation models the number of comparisons, and the number of comparisons is the same. What differs is the cost of each one, which the notation does not model at all.

7. Allocation Count Is a Cost in Itself

map:            allocs=100000  bytes= 4000000
unordered_map:  allocs=100001  bytes= 3200024
sorted vector:  allocs=1       bytes=  800000   (8 bytes/entry)

One allocation against a hundred thousand, and a fifth of the memory.

Allocation count matters for three reasons beyond the time spent in the allocator. It determines how scattered the elements end up, which §4 priced at about 60×. It fragments the heap, so later large allocations are harder to satisfy. And in a multi-threaded program it contends on the allocator, which is shared.

The 8 bytes per entry for the sorted vector is the payload with nothing added — a pair<int,int> and no bookkeeping, because a sorted array needs none. The tree needs 32 bytes of pointers and colour per 8 bytes of data.

8. When the Asymptotically Worse Container Wins

Three measured cases from this module, with the condition that produces each.

Find-then-insert: vector beats list despite O(n) insertion. Measured about 4.4× at n = 100,000 — Chapter 19.4 §6. The condition is that the position must be found, so both pay O(n) for the search and the vector's search is the one the hardware likes.

Lookup: a sorted vector beats map at equal complexity. Measured about 1.9× in §6. The condition is that the data has a build phase and a query phase that do not interleave — Chapter 19.7 §6.

Traversal: vector beats everything. Measured about 29× when vectorisable and about 1.2× when not — §3. The condition for the large figure is a vectorisable loop over a trivially copyable type.

And the case where the complexity table is right:

Insertion at a held position: list beats vector by roughly 36×. Measured in Chapter 19.4 §6. The condition is holding the iterator rather than searching for it.

The pattern across all four: the complexity table is accurate about the operation it names, and the question is whether that operation is the one your code performs.

9. The Numbers Table

10. Measuring Honestly

Every figure above is the product of a harness with four properties, and each one was necessary.

A barrier. sink() and clobber() with asm volatile and a "memory" clobber. Without them the optimiser removes loops whose results are unobserved, and the measurement reports the cost of nothing.

Warm-up. The first execution pays cold caches, lazy page faults and branch predictors with no history. Every benchmark here runs the subject once before timing.

Repetition with a summary that is not the mean. Every figure here is a median of nine with the range reported, as in Chapter 19.7 §3. Means are contaminated by scheduling interruptions, which are one-sided — they can only make a sample slower. And because this machine is a working one, the absolute times move between runs while the ratios hold: report the ratio as the finding and the absolute as the scale.

A scale where the effect exceeds the noise. A million elements, 200,000 lookups. Chapter 19.7 §3's measurement is the cautionary case: two containers 5% apart with ranges overlapping across most of their width, where the correct conclusion was that the measurement does not separate them.

And one property this chapter had to add: decomposition before attribution. A ratio between two things that differ in more than one respect is not evidence about any single respect. §3 exists because §1's number would otherwise have been attributed entirely to the cache, which the measurement does not support.

11. What to Actually Do

• Prefer contiguous storage unless a named guarantee requires otherwise. Chapter 19.7 §1's path.
• Call reserve when the count is known — it removes allocations and keeps elements together.
• Count allocations, not just time. One against a hundred thousand is a layout prediction as well as an allocator cost.
• Be suspicious of a container whose elements were allocated over a long period. The ~60× arrives with age.
• Consider a sorted std::vector instead of a std::map when the access pattern allows it: ~1.9× faster at equal complexity, a fifth of the memory, one allocation.
• Prefer vector<T> to vector<unique_ptr<T>> unless polymorphism or stable addresses require the indirection — a vector of pointers traverses like the scattered list.
• Use complexity as a filter, not a ranking. It identifies what degrades with growth; it does not predict which of two containers is faster.
• Use a barrier, two warm-ups, repetition and a median with its range in every benchmark.
• Decompose before attributing. Remove the suspected cause and check the ratio moves, or compare the subject against itself.
• Measure on your own data. Every figure here is one machine, one compiler, one element type.

12. Mistakes Worth Making Once

Timing a loop with no barrier. The optimiser deletes it and the container looks infinitely fast.

Reporting the first run. Cold caches and page faults; often several times the steady-state figure.

Attributing a cross-container ratio to the cache. My own §1 number was mostly SIMD and I would have published it as a cache result had I not removed the cause and re-measured.

Publishing a single run as a precise figure. My first draft of this chapter quoted 78.18 ns and 46.3× for §4 from one run. Nine further runs put the scattered figure between 116 and 187 ns and the ratio between 51× and 68× — so the published number was below the range it claimed to represent, and it understated the effect it was arguing for.

Benchmarking a freshly-built std::list. Its nodes are consecutive, so it measures as about 1.2× rather than about 60×. The benchmark is honest and the conclusion is wrong, because real lists are not fresh.

Using the mean across runs. Interruptions are one-sided; use a median or a minimum.

Trusting a 5% difference. Chapter 19.7 §3's ranges overlapped across most of their width.

Assuming vector<unique_ptr<T>> is contiguous. The pointers are; the objects are wherever the allocator put them.

Choosing std::map for lookup because O(log n) sounds close to O(1). Measured about 47×.

Optimising a container choice before profiling. Chapter 19.7 §4 showed the access pattern dominating the container.

13. Interview Relevance

The frozen curriculum marks this chapter High, and these questions separate candidates who have measured from those who have read.

"Why is std::vector faster than std::list for traversal?" Cache lines, prefetching and vectorisation, in that order of explanation. The answer that stands out decomposes it: most of a measured ~29× was SIMD, and the isolated layout effect — list against list, only addresses differing — was about 60×.

"Both std::map::find and std::lower_bound on a sorted vector are O(log n). Which is faster, and why?" The vector, measured about 1.9×. The comparison count is the same; the tree's are dependent pointer loads to independently-allocated nodes, the vector's are probes into one block.

"When is the asymptotically worse container faster?" Three measured cases in §8, each with its condition. Having the conditions is the answer, not the examples.

"How would you benchmark two containers?" Barrier, warm-up, repetition, a median with its range, a scale where the effect exceeds the noise — and decomposition before attributing a cause. The last point is the one most candidates omit.

"What is the cost of a std::list<int> element?" 24 bytes for 4 bytes of payload, one allocation, and six times the memory traffic for the same data.

"Your std::list-based code was fast in a benchmark and slow in production. Why?" The benchmark built the list in one go, so its nodes were consecutive. In production the list has been inserted into and erased from for hours and its nodes are scattered. This is an excellent answer because it is a real failure mode and it shows you understand why the benchmark lied — the 2.6 ns to 150 ns transition §4 measured.

14. What You Should Be Able to Say Now

• The three mechanisms behind contiguity's advantage, and that one of them is not a memory effect.
• That a measured ~29× fell to ~1.2× when SIMD was denied, and that it was the vector column that moved.
• That a std::list measured against itself with only node addresses differing was about 60× worse — the properly isolated figure.
• That the construction required proving list::sort relinks rather than moves, verified three ways.
• That a std::list<int> touches 6× the memory for the same payload.
• That a sorted std::vector beat std::map by about 1.9× at identical complexity, with one allocation against 100,000 and a fifth of the memory.
• That unordered_map was about 47× map at lookup.
• The four conditions under which the complexity table's preference inverts.
• Why a single ratio between two things differing in two respects is not evidence about either, and why one run is not a figure.

15. Exercises

Exercise 1 — the barrier. Run §1's benchmark with and without sink(). Report both and explain the difference in the generated assembly.

Exercise 2 — reproduce the decomposition. Measure the vectorisable and serial-dependence loops on all three containers. Confirm which column moves, and state in one sentence what that implies about §1's number.

Exercise 3 — the isolated measurement. Reproduce §4's two lists. Before timing them, verify independently that list::sort relinked rather than moved. Then sweep N from 10,000 to 10,000,000 and find where the gap opens. Report a median and a range, and state whether your ranges overlap.

Exercise 4 — ageing a container. Build a std::list, then perform a million random insert/erase pairs, then measure traversal. Compare with the fresh list and with §4's deliberately scattered one.

Exercise 5 — the pointer vector. Benchmark vector<Widget> against vector<unique_ptr<Widget>> for a 64-byte Widget, traversal and random access. Relate the result to §4.

Exercise 6 — equal complexity. Implement binary search over a sorted vector and compare with std::map::find at n from 1,000 to 10,000,000. Plot both and explain the shape of the ratio.

Exercise 7 — cache sizes. Find your machine's L1, L2 and L3 sizes, then sweep a vector traversal across sizes spanning all three. Identify the knees and relate them to the figures.

Exercise 8 — allocation and scatter. Build a std::list of a million elements two ways: directly, and with an unrelated allocation between each node. Measure both traversals and report how much of §4's ~60× you reproduced.

16. Summary

• Complexity counts operations and assumes uniform memory cost, which hardware stopped providing decades ago. It filters; it does not rank.
• Measured: traversal of 1e6 ints — vector 0.09, deque 0.61 (~7.8×), list 2.50 ns/element (~29×) on identical arithmetic.
• Measured decomposition: that gap was mostly SIMD. With a serial dependence denying vectorisation the ratio fell to ~1.2× (range 1.0–1.4), and it was the vector that slowed — 0.06 to 1.53 ns/element.
• Measured, properly isolated: a std::list against itself, same type and contents and complexity, nodes sequential versus scattered — 2.6 against 150 ns/element, about 60× (range 51–68, no run below 45×). Node addresses were the only variable.
• That construction required verifying three ways that list::sort relinks rather than moving values: 5/5 addresses kept their values, 0 allocations, 0 copies and moves.
• Measured: a std::list<int> touches 6.0× the memory for the same payload.
• Measured lookup, 100k keys: map 153.7 ns, unordered_map 3.3 ns (~47×), sorted vector 80.0 ns — and the vector beat the map by ~1.9× at identical O(log n).
• Measured: 100,000 allocations and 4 MB for a map, against 1 allocation and 0.8 MB for the sorted vector.
• The table inverts under nameable conditions — search dominating an O(1) insert, a build/query split, a vectorisable traversal — and it is right when you hold the position (~36×).
• Never attribute a ratio without decomposing it. Remove the suspected cause and check the ratio moves, or compare the subject against itself — and report a median with a range, never one run.

That completes Module 19, and with it the storage half of the standard library. Eight chapters have established that a container is a set of promises rather than a collection of methods, measured what each promise costs, and ended on the reason the published costs are a poor guide to speed — which is the knowledge that makes the difference between choosing a container and defaulting to one.

Module 20 is Iterators, Algorithms, and Lambdas, and it is the half that makes all of this composable. Iterators generalise the position that this module's containers each express differently — Chapter 19.4 §7's point that std::list has no operator[] becomes a statement about iterator categories, and the algorithms are written against those categories rather than against containers, which is why std::sort requires random access and std::list needs its own member version. Lambdas supply the per-element decision that an algorithm cannot know. Between them they let the thousand hand-written loops in this module's exercises become a few named operations whose intent is readable, and the module ends on exactly the data this curriculum is aimed at: log entries, transactions, coverage records and measurement samples.