skip to content

Allocation-Free Hot Paths

Heap allocation in a frame or a tick costs latency, so code reserves, pools and uses pmr memory resources. Interviewers ask how to stop a hot loop from allocating.

on this pageshow

explore

questions

4

In a C++ tick handler, why does reusing a reserved std::vector with clear() avoid the heap allocations a fresh vector per tick makes?

level: juniorimportance: must knowfreq 68%

answer

  1. size is not capacity
  2. a fresh vector starts with no buffer
  3. growth means allocate, move, free
  4. clear destroys elements, not the buffer

basics

~20 s

A vector declared inside the tick starts with no buffer, reallocates as it grows and frees its buffer at scope exit, every tick. A vector reserved once and cleared each tick keeps its buffer, so push_back within capacity never allocates.

solid answer

~50 s

`std::vector` tracks `size()` and `capacity()` separately. A `std::vector<Quote>` declared inside the tick loop starts with no buffer, so filling it with 100 quotes walks through a chain of reallocations — allocate a bigger block, move the elements, free the old block — and its destructor frees the last block when the tick ends. libc++ and libstdc++ both double the capacity, so that is eight allocations per tick for 100 quotes. Hoisting the vector out of the loop, calling `reserve(100)` once before the first tick and `clear()` at the start of each tick brings it to zero: `clear()` destroys the elements but, in libc++ and libstdc++, leaves the buffer in place, and the standard says an insertion reallocates only when the new size would exceed `capacity()`. Elements that own memory, such as `std::string`, still allocate on their own.

code

cpp · 27 lines
cpp
#include <cstdio>
#include <cstdlib>
#include <new>
#include <vector>

static long g_allocs = 0;  // test-only: count every call to the global operator new
void* operator new(std::size_t n) { ++g_allocs; if (void* p = std::malloc(n)) return p; throw std::bad_alloc{}; }
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }
struct Quote { double bid, ask; };

int main() {
    long before = g_allocs;
    for (int tick = 0; tick < 1000; ++tick) {
        std::vector<Quote> fresh;                       // capacity 0 at the start of every tick
        for (int i = 0; i < 100; ++i) fresh.push_back({1.0, 1.1});
    }                                                   // buffer freed at the end of every tick
    std::printf("fresh vector per tick: %ld allocations\n", g_allocs - before);
    std::vector<Quote> reused;
    reused.reserve(100);                                // paid once, before the first tick
    before = g_allocs;
    for (int tick = 0; tick < 1000; ++tick) {
        reused.clear();                                 // destroys the elements, keeps the buffer
        for (int i = 0; i < 100; ++i) reused.push_back({1.0, 1.1});
    }
    std::printf("reserved and reused:   %ld allocations\n", g_allocs - before);
}

go deeper

for a junior

Recall that size and capacity differ, that growth reallocates, and that clear keeps the buffer while a new vector starts empty. Reserve once, reuse the object.

for a middle

Explain the reallocation rule and count the allocations a doubling growth policy costs for a given element count, and why reserve on a short-lived vector still allocates once per tick.

for a senior

Show you size reservations from measured peaks and notice what reuse misses: elements owning memory, copies handed to other owners, and shrink calls inside the loop.

for a principal

Frame vector reuse as one piece of a hot-path allocation policy, balancing reserved memory per handler against tail latency across many symbols or instances.

## Size and capacity are two different numbers A `std::vector<T>` owns one contiguous heap buffer. `size()` is how many elements are alive in it; `capacity()` is how many fit before the vector needs a bigger buffer. The standard ties every reallocation to that second number: an insertion **causes reallocation if the new size is greater than the old capacity**, and after `reserve(n)` no insertion reallocates until the size would pass `capacity()`. Everything about keeping a hot loop allocation-free with a vector follows from that rule. ## What a fresh vector per tick costs Consider a market-data handler that collects the quotes of one tick into a local `std::vector<Quote>` declared inside the loop body. Every tick then does the same work again: 1. The vector is constructed empty, with no buffer at all. 2. The first `push_back` allocates a small buffer. 3. Each time the size passes the capacity, the vector allocates a larger block, moves (or copies) the elements across and frees the old block. 4. At the closing brace the destructor destroys the elements and frees the final block. The growth factor is an **implementation choice**, not the standard's: libc++ and libstdc++ both double the capacity (libc++ computes `max(2 * capacity, new_size)`, libstdc++ `size + max(size, n)`). With doubling, 100 quotes cost eight allocations per tick — capacities 1, 2, 4, up to 128 — plus the matching frees. On a feed that delivers tens of thousands of ticks a second, that is hundreds of thousands of calls into the allocator, each of which can take a lock, touch cold memory or occasionally ask the operating system for pages: exactly the latency spikes a tick path must not have. ## Reserve once, clear every tick The fix is to give the vector a longer life than the tick: - **Hoist it**: make it a member of the handler, or a variable declared before the loop. - **Reserve at startup**: `reserve(expected_peak)` pays for the buffer once, before trading starts. - **Clear at the start of each tick**: `clear()` destroys the elements and leaves `size()` at zero; libc++ and libstdc++ keep the buffer, so `capacity()` is unchanged. - **Fill as before**: every `push_back` or `emplace_back` that stays within `capacity()` constructs in place and never calls the allocator. The example below counts calls to the global `operator new`: the fresh-vector loop makes 8,000 allocations over 1,000 ticks, the reserved-and-reused loop makes none. | Pattern | Allocations per tick (100 quotes, doubling growth) | |---|---| | Local vector, no reserve | 8 | | Local vector with `reserve(100)` | 1 | | Reused vector, `clear()` each tick, no reserve | 0 after the first tick | | Reused vector, `reserve(100)` at startup, `clear()` each tick | 0 from the first tick | Note the second row: calling `reserve` on a vector that dies every tick still allocates once per tick, because the destructor gives the buffer back. Reserve only removes allocations when the buffer outlives the loop. ## What reuse does not fix Reusing the vector removes the vector's own allocations. It does not make everything in it free: - **Elements that own memory** still allocate. A `std::vector<std::string>` cleared each tick destroys its strings, so each new string longer than its small-string buffer allocates its characters again. - **A burst past the reserved size** reallocates once; the vector then keeps the larger buffer, which is usually what a tick path wants. - **`shrink_to_fit()`** is, in the standard's words, a non-binding request to reduce `capacity()` to `size()`; calling it in the loop invites a reallocation on the next tick. - **Copying or returning the vector by value** to another owner allocates a new buffer for the copy. - **`emplace_back` versus `push_back`** makes no difference to the buffer: both obey the same reallocation rule. ## Choosing the reserved size Pick the reservation from measurement, not from a guess: 1. Record the largest per-tick element count over a busy recorded session, such as a market open. 2. Add headroom for bursts the recording did not contain. 3. Reserve that once, before the first tick, and log `capacity()` after a session to see whether a burst ever grew it. A too-small reservation costs one growth on the first burst and is then absorbed, because the vector keeps the larger buffer. A far too large one wastes memory per handler, which matters when there is one handler per symbol or per feed.

  • How do you give back a reused vector's buffer after a rare burst made it huge?
    Do it outside the tick path. `shrink_to_fit()` is only a non-binding request, so the reliable way is to replace the buffer: `std::vector<Quote>().swap(v);` or `v = std::vector<Quote>{};` then `v.reserve(normal_peak);`. Both free the large block and allocate a normal-sized one, so schedule them at a quiet moment, such as between trading sessions.
  • Does switching from push_back to emplace_back reduce the allocations of a fresh vector per tick?
    No. Both append one element and both reallocate under the same rule, when the new size would exceed `capacity()`. `emplace_back` can save constructing and moving a temporary element, which matters for expensive element types, but the buffer growth, and therefore the allocation count, is identical.

  • clear() frees the vector's buffer, so reusing the vector saves nothing
  • reserve() fixes the capacity, so the vector can never reallocate again
  • A local vector's elements live on the stack, so it never allocates
  • Calling reserve(n) inside the tick loop removes every allocation
  • emplace_back avoids the reallocations that push_back causes
open as a page

Which ordinary C++ operations in a market-data tick path allocate on the heap with no visible new, and how do you catch them?

level: middleimportance: must knowfreq 58%

basics

~20 s

Long std::string values, std::function holding a large callable, vector growth, make_shared, new-key inserts into std::map or std::unordered_map, and string formatting all allocate. Catch them by counting global operator new in a test or with a heap profiler.

open as a page

How does C++17's std::pmr::monotonic_buffer_resource over a fixed buffer make a tick's temporary containers allocation-free, and where can that setup still reach the heap?

level: seniorimportance: should knowfreq 32%

basics

~20 s

Build std::pmr containers on a monotonic_buffer_resource placed over a preallocated buffer: allocation bumps a pointer, deallocation does nothing, and everything is released at once. Overflow goes upstream, by default to new and delete, and copies and non-pmr elements escape too.

open as a page

As lead of a C++ market-data handler, how would you set an allocation budget and allocator policy for the tick path, and how would you enforce them?

level: principalimportance: should knowfreq 22%

basics

~20 s

Set the budget at zero heap allocations per tick after warm-up, give each data lifetime its allocator (startup reserves, pools, a per-tick arena), choose throw or counted fallback on overflow, and enforce it with an allocation-counting test and production counters.

open as a page