Hidden Copies and Allocations

Part I · Module 25 · Chapter 25.9 · Hidden Copies and Allocations

1. Count, Do Not Time

Two instruments, both of which produce exact integers:

// 1. a global allocation counter
static std::size_t g_new = 0, g_bytes = 0;
void* operator new(std::size_t n) { ++g_new; g_bytes += n; return std::malloc(n); }
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }

// 2. a type that counts its own copies
struct Tracked {
    static long ctor, copy, move, dtor;
    std::vector<int> payload;
    Tracked() : payload(64) { ++ctor; }
    Tracked(const Tracked& o) : payload(o.payload) { ++copy; }
    Tracked(Tracked&& o) noexcept : payload(std::move(o.payload)) { ++move; }
    ~Tracked() { ++dtor; }
};

Both are worth having in a scratch file permanently. Two notes on using them correctly, both of which this curriculum learned by getting them wrong.

Override the global operator new, not a per-container allocator. A std::function, a std::any, a std::variant and a std::string all allocate through the global operator, and a Counting<T> allocator attached to one container never sees any of it — which produced allocs=0 for every row of a table on two separate occasions in this curriculum before the cause was found. Chapter 20.9 §3 is where that is measured.

Count unconditionally. A counter that is gated on the condition you are testing reports zero for both arms and measures nothing. Chapter 22.5's safety experiment hit exactly that.

The reason to prefer counting over timing is not only accuracy. It is that a count answers why: "1,978 allocations" names the mechanism, where "4.3 ms" only names the symptom. Chapter 25.8 §7 is the general version of that argument.

2. The By-Value Parameter

void byValue(Tracked t)          { use(t); }
void byConstRef(const Tracked& t){ use(t); }

A. a by-value parameter against a const reference
  byValue(Tracked)                   ctor=0 copy=1 move=0 dtor=1
  byConstRef(const Tracked&)         ctor=0 copy=0 move=0 dtor=0

One copy and one destruction, against none. The call site is identical in both cases — byValue(t) and byConstRef(t) — which is the whole problem: nothing at the point of the call indicates that one of them copies a 64-element vector.

The rule is the familiar one, and it is worth stating with its exceptions rather than as an absolute:

The "by value then move" row is the one people get wrong in the other direction. If a setter stores its argument, taking const std::string& forces a copy even when the caller passed a temporary; taking std::string by value lets the caller's temporary move in, and costs one move when it does not. Chapter 13.9 is the general treatment.

3. The Missing Ampersand, Which Is a Threshold

for (auto p : m)        total += p.second;    // copies every element
for (const auto& p : m) total += p.second;    // does not

The obvious prediction is that the first form copies each std::pair<const std::string, int> and therefore allocates once per element. Measured across four key lengths:

  libc++ small-string capacity: a std::string holds 22 chars inline
  key length  8 : for(auto p)    0 allocations | for(const auto& p)    0
  key length 22 : for(auto p)    0 allocations | for(const auto& p)    0
  key length 23 : for(auto p)  200 allocations | for(const auto& p)    0
  key length 40 : for(auto p)  200 allocations | for(const auto& p)    0

Nothing up to 22 characters. One allocation per element at 23. libc++ stores up to 22 characters inside the std::string object itself — the small-string optimisation — so copying a short-keyed pair touches no allocator at all. At 23 the buffer moves to the heap and every copy allocates.

So the cost of the missing & is zero or one allocation per element depending on a data value, and the threshold is a library implementation detail rather than anything in the standard. On libstdc++ the inline capacity is 15, and on MSVC it differs again.

That is precisely why this defect ships. A test fixture uses unit_0 through unit_199; production uses axi_master_port_3_write_channel. The code is identical, the test is clean, and the loop allocates two hundred times per pass in the field.

And I had to correct this experiment. My first version used unit_0-style keys, measured 0 allocations both ways, and would have supported the conclusion that the missing & is free. It is free only below the threshold. Chapter 24.2 §5's callout makes the general point: an experiment must be able to tell its two arms apart, and checking that the arms actually differ is cheaper than interpreting the result.

A related case with the same shape and no threshold:

for (auto s : strings)        // copies each string
for (const auto& s : strings) // does not
for (auto&& s : strings)      // binds without copying, and allows mutation if non-const

const auto& is the default to reach for. auto&& is the forwarding form, correct for generic code and for proxy references — which is the case where const auto& is wrong, because std::vector<bool>'s operator[] returns a proxy, not a bool&.

4. Returning a Container Is Not a Copy

std::vector<int> returnByValue(int n) { std::vector<int> v(n); return v; }
auto v = returnByValue(1000);

C. returning a container by value
  auto v = returnByValue(1000)   1 allocation(s), size 1000

One allocation — the vector's buffer — and no copy. The local is constructed directly into the caller's storage; since C++17 this is mandatory for a returned temporary, and for a named local like this one the compiler elides it in practice and must otherwise move.

This matters because the fear of it produces worse code. The two "optimisations" people reach for are both mistakes:

void fill(std::vector<int>& out);            // output parameter: an uninitialised local
                                              // at the call site, no composition, and
                                              // Chapter 23.3 §4's ignorable contract
std::vector<int>* makeHeap(int n);           // and now ownership is a question

Chapter 21.5 §3 measured the output parameter's four costs. Return by value. The exceptions are narrow: reusing a caller-provided buffer across many calls to avoid repeated allocation, which is a measured decision rather than a default, and filling a buffer the caller already owns.

One real trap in this area, worth knowing because it silently defeats the elision:

std::vector<int> f(bool a) { std::vector<int> x, y; return a ? x : y; }   // no NRVO
std::vector<int> g(int n)  { return std::move(std::vector<int>(n)); }     // pessimising

Two named candidates block the named return value optimisation, and std::move on a returned local turns a copy elision into a move — strictly worse, and -Wpessimizing-move warns about the second.

5. The String Built in a Loop

The largest measured effect in the chapter, and the most common in real code:

std::string buildPlus(int n)     { std::string s; for (…) s = s + piece; return s; }
std::string buildAppend(int n)   { std::string s; for (…) s += piece;    return s; }
std::string buildReserved(int n) { std::string s; s.reserve(n); for (…) s += piece; return s; }

D. building a 2000-character string three ways
  s = s + piece       1978 allocations  2009864 bytes (len 2000)
  s += piece             7 allocations     6096 bytes (len 2000)
  reserve, then +=       1 allocations     2008 bytes (len 2000)

1,978 allocations and two megabytes requested, to produce two thousand characters.

The mechanism is in the difference between the two operators. s = s + piece evaluates s + piece into a new temporary string — which allocates, and copies everything s already held — then assigns it back. Doing that two thousand times copies the whole accumulated string two thousand times, which is the quadratic behaviour the byte figure exposes: 2,009,864 bytes requested is roughly n²/2 characters for n = 2000.

s += piece appends in place, allocating only when the capacity is exhausted — seven times for two thousand characters, because the growth is geometric. And reserve makes it one.

Three things to take from the byte column rather than the allocation column. The 2 MB is traffic through the allocator, so it is also 2 MB of memcpy; the += version's 6,096 bytes is the sum of seven geometrically growing buffers, which is why it is three times the final length rather than equal to it; and reserve's 2,008 is the final length plus the terminator and rounding — the minimum possible.

The same shape appears wherever a container grows in a loop. Chapter 19.3 §3 measured vector::push_back's reallocation behaviour, Chapter 25.10 §3 measures what reserve is worth in time rather than allocations, and Chapter 23.5 §3 measured the related case where a plausible optimisation — hoisting an ostringstream out of the loop — changed the allocation count not at all.

6. The Catalogue

The copies the source does not mention, with the fix for each:

Two rows deserve a note. map[key] to read a missing key inserts a default-constructed value, so the container grows during a read loop — a bug as well as a cost. And std::function's inline buffer is 16 bytes on libc++, which Chapter 20.9 §3 measured; a lambda capturing more than that allocates on every construction.

7. Finding Them in Your Own Code

Four techniques, in increasing cost.

Grep the signatures. const T& versus T for class types, and for (auto without an &, are both mechanically findable and the second is a one-line search with a high hit rate.

Turn on the warnings that exist. -Wrange-loop-construct fires on exactly §3's defect, and is not in -Wall -Wextra. -Wpessimizing-move and -Wreturn-std-move cover §4's traps:

clang++ -std=c++20 -Wall -Wextra -Wrange-loop-construct -Wpessimizing-move …

Count, on a realistic workload. Drop in §1's two instruments and run the real input. This is the step that finds what the greps miss, and Chapter 25.8 §7's point applies — a counter is often a better first measurement than a profile.

Profile only after the counts. Chapter 25.8 §4 measured a flat profile attributing a function's cost to its callees; an allocation count points at the call site directly, and operator new showing up high in a profile is a symptom whose cause is the count.

One caution about the instruments themselves. Overriding the global operator new changes the program — it adds a counter increment to every allocation — so it belongs in a measurement build, not a shipped one. And a Tracked type measures that type; a copy of a std::string elsewhere in the same loop is invisible to it, which is why the two instruments are used together.

8. What Is Not Worth Avoiding

Symmetry with Chapter 25.10: some things that look like copies are not, and avoiding them costs clarity for nothing.

Returning a container by value. §4 — one allocation, no copy.

Passing and returning std::string_view and std::span by value. They are two words and are references already. Taking them by const& is an indirection for nothing.

Small types by value. int, double, an enum, a pointer, a std::chrono::duration. A reference is larger and adds a dereference.

A shared_ptr by const& when you do not store it — that avoids an atomic increment and is worth knowing; but passing one by value when you do store it is correct.

std::move on a variable you are finished with. It is not a copy and it is not a cost; std::move on a returned local is the mistake, not std::move in general.

The distinction to hold onto is that a copy is cheap exactly when the object owns nothing. Tracked in §2 owns a vector, so copying it allocates; a struct Point { double x, y; } owns nothing, and copying it is two register moves. Ask what the object owns, not how large it is.

9. The Table

10. What to Actually Do

• Count, do not time. Keep a global operator new counter and a Tracked type in a scratch file; both answers are exact and both name the mechanism.
• Override the global operator new, not a per-container allocator — string, function, any and variant all go through the global one.
• Take class-type parameters you only read by const&; take them by value and std::move when you store them.
• Write const auto& in every range-for over class types, and auto&& in generic code.
• Never build a string with s = s + piece in a loop. Measured: 1,978 allocations against 1.
• reserve when the final size is known, for strings and vectors alike.
• Return containers by value. Do not reach for an output parameter or a raw pointer, and never return std::move(local).
• Turn on -Wrange-loop-construct and -Wpessimizing-move, which -Wall -Wextra do not include.
• Measure the rule on your own data. The missing & was worth nothing at 22 characters and 200 allocations at 23.
• Check that an experiment can distinguish its arms before trusting its result — mine could not, the first time.
• Ask what an object owns, not how big it is, before deciding a copy is expensive.

11. Mistakes Worth Making Once

A by-value std::string parameter in a function that only reads it. One copy per call, invisible at the call site.

for (auto p : map). Free in the test, 200 allocations per pass in production.

Concluding from short keys that the missing & is free. My first experiment did exactly that.

s = s + piece in a loop. Quadratic, and 2 MB of allocator traffic for 2 KB of output.

Forgetting reserve when the count is known. Seven allocations instead of one, and the copies that go with them.

An output parameter to avoid a copy that does not exist. Chapter 21.5 §3's four costs, for nothing.

return std::move(local). Elision becomes a move; -Wpessimizing-move says so.

A per-container allocator to count allocations. It cannot see string, function, any or variant — measured as allocs=0 twice in this curriculum.

Gating the counter on the condition under test. Zero for both arms.

Avoiding a returned container. One allocation, no copy.

Taking std::string_view by const&. An indirection to a reference.

12. Interview Relevance

The frozen curriculum marks this chapter Critical, and it is the performance question most likely to come up in a C++ interview: "why is this slower than it should be?" over code with no obvious algorithmic problem.

The answer that lands names the class — copies the source does not mention — and then the specific four: a by-value parameter, a range-for missing its reference, a string built with + in a loop, and a container reallocating without reserve. The figure to quote is the string one, because it is dramatic and because the mechanism is in the number: 1,978 allocations and 2 MB requested to produce 2,000 characters, because s = s + piece builds a new string each iteration and copies everything accumulated so far.

The detail that distinguishes real experience is the threshold. The missing & in a range-for over a string-keyed map costs zero allocations for keys up to 22 characters and one per element at 23, because of libc++'s small-string buffer — so the defect is free in a test with short names and expensive in production, and a benchmark published without its key lengths is not a reusable number.

And the methodological point is worth volunteering: these are counts, which reproduce exactly, where timings on a loaded machine have repeatedly needed medians and ranges. A count also names the mechanism; a timing only names the symptom.

13. What You Should Be Able to Say Now

• That the common cause of a slow C++ model is a copy the source does not mention, and why: the syntax for copying is the syntax for using.
• Why a count is the right instrument — exact, reproducible, and it names the mechanism — and that the global operator new must be overridden rather than a per-container allocator.
• That a by-value class parameter costs 1 copy and 1 destruction per call, with an identical call site.
• That for (auto p : map) costs 0 allocations at 22-character keys and 200 at 23, because libc++ holds 22 characters inline — and that a short-key test therefore cannot detect it.
• That my first version of that experiment measured 0 both ways and would have concluded the missing & was free.
• That returning a container by value costs 1 allocation and no copy, so output parameters and return std::move(local) are both mistakes.
• That s = s + piece in a loop costs 1,978 allocations and 2,009,864 bytes for 2,000 characters, s += piece costs 7 and 6,096, and reserve plus += costs 1 and 2,008 — and why the byte column shows the quadratic copying.
• That -Wrange-loop-construct and -Wpessimizing-move are not in -Wall -Wextra.
• What is not worth avoiding, and that the question is what an object owns rather than how large it is.

14. Exercises

Exercise 1 — the instruments. Write §1's allocation counter and Tracked type. Reproduce §2's table. Then try to count the allocations with a per-container Counting<T> allocator instead, and confirm it reports zero for a std::string member.

Exercise 2 — the threshold. Reproduce §3's four key lengths. Then find the exact threshold on your standard library by sweeping the length one character at a time, and compare it with std::string().capacity().

Exercise 3 — the string. Reproduce §5's three figures. Then plot allocations and bytes against the final length for the + version and confirm the byte curve is quadratic.

Exercise 4 — the return. Count the allocations for returning a vector by value, through an output parameter, and through a unique_ptr. Then add return std::move(v) and compile with -Wpessimizing-move.

Exercise 5 — the warnings. Add -Wrange-loop-construct and -Wpessimizing-move to a real project and report how many instances exist. Fix none of them yet; count first.

Exercise 6 — your own data. Put the counters into a real workload and list the top three allocation sites. Then decide, before optimising anything, which of them the output actually depends on.

15. Summary

• The commonest reason a C++ model is slow is a copy the source does not mention, because copying an object and using it have the same syntax.
• Count rather than time. A global operator new counter and a self-counting type give exact, reproducible integers that also name the mechanism — unlike a timing, which names only the symptom and on this machine needs medians and ranges.
• A by-value class parameter costs 1 copy and 1 destruction per call; const& costs none, and the call sites are identical.
• for (auto p : map) is a threshold, not a constant. Measured: 0 allocations for keys of 8 and 22 characters, 200 — one per element — at 23 and 40, because libc++ stores 22 characters inline. So the defect is free in a short-key test and expensive in production, and my first version of this experiment measured 0 both ways and would have reported the missing & as free.
• Returning a container by value costs 1 allocation and no copy, so output parameters and return std::move(local) are both worse than the thing they avoid.
• Building a 2,000-character string: s = s + piece → 1,978 allocations, 2,009,864 bytes; s += piece → 7, 6,096; reserve then += → 1, 2,008. The byte column is the quadratic copying made visible.
• -Wrange-loop-construct and -Wpessimizing-move catch two of these and are not in -Wall -Wextra.
• Measure the rule on your data, check that your experiment can distinguish its arms, and ask what an object owns rather than how large it is before assuming a copy is expensive.

Chapter 25.10 closes the module with the discipline that makes any of this safe to act on: change one thing, measure it, and keep it only if the number moved.