In C++, why does updating a std::vector<Particle> usually run much faster than updating a std::vector<std::unique_ptr<Particle>>?
answer
- one block versus many blocks
- vector is a contiguous container
- a dependent load per element
- what reserve does and does not lay out
- N + 1 allocations
basics
~20 sstd::vector<Particle> stores the particles back to back in one block, so the loop streams through memory the prefetcher can predict. A vector of std::unique_ptr holds only pointers to separately allocated particles: an extra dependent load, and often a cache miss, per element.
solid answer
~50 sThe standard makes `std::vector<T>` a **contiguous container** (for every `T` except `bool`): `&v[i] + 1 == &v[i + 1]`. A loop over `std::vector<Particle>` therefore walks one block front to back, every byte of each 64-byte cache line it pulls in belongs to a particle, and the hardware prefetcher fetches the next lines before the loop asks. `std::vector<std::unique_ptr<Particle>>` is contiguous too, but only the pointers are: each `Particle` came from its own `new`, so the loop loads a pointer, then waits for a dependent load wherever the allocator put that object. After objects are created and destroyed for a while those addresses scatter, so the prefetcher has no pattern and many iterations miss the cache. People reach for pointers for polymorphism or stable addresses; one vector per concrete type, or indices instead of pointers, keeps the data contiguous.
code
cpp · 27 lines#include <cstdio>
#include <memory>
#include <vector>
struct Particle {
float x, y, z;
float vx, vy, vz;
};
int main() {
// One allocation; the Particles sit back to back in one block.
std::vector<Particle> values(4);
// Five allocations: the vector holds pointers, each Particle lives elsewhere.
std::vector<std::unique_ptr<Particle>> pointers;
for (int i = 0; i < 4; ++i) pointers.push_back(std::make_unique<Particle>());
auto gap = [](const void* a, const void* b) {
return static_cast<const char*>(b) - static_cast<const char*>(a);
};
std::printf("sizeof(Particle) = %zu\n", sizeof(Particle));
std::printf("values: &[1] - &[0] = %td bytes\n", gap(&values[0], &values[1]));
std::printf("pointers: [1] - [0] = %td bytes\n",
gap(pointers[0].get(), pointers[1].get()));
for (Particle& p : values) p.x += p.vx; // walks one contiguous block
for (auto& p : pointers) p->x += p->vx; // one dereference per element
}go deeper
Say that std::vector stores its elements contiguously and that a vector of pointers stores only the pointers, with every object allocated elsewhere.
Explain the dependent load, cache-line use and the prefetcher, and name the standard's contiguous-container guarantee and its vector<bool> exception.
Name why the pointer layout was chosen (polymorphism, stable addresses) and replace it: per-type vectors, variants by value, indices or handles, and measure on churned memory.
Frame it as a data-ownership decision for an engine: systems own arrays of plain data and pass indices, and hot loops never chase pointers by design.
## What the standard promises about the layout `std::vector` is specified as a **contiguous container**: its elements live in one array, so `&v[i] + 1 == &v[i + 1]` for every valid `i + 1`. The one exception is `std::vector<bool>`, which packs bits and is not contiguous in that sense. `std::array` and `std::basic_string` carry the same guarantee. A built-in array gives the same promise: an object of type "array of N T" is a contiguously allocated set of N elements. So `std::vector<Particle>` with a 24-byte `Particle {float x, y, z, vx, vy, vz;}` is one heap block of `24 * capacity()` bytes, filled from the front. ## What the update loop does in each case | | `std::vector<Particle>` | `std::vector<std::unique_ptr<Particle>>` | |---|---|---| | Allocations for N particles | 1 (plus regrowth) | N + 1 | | Loads per element | the particle itself | the pointer, then the particle it points at | | Address of element i + 1 | always `sizeof(Particle)` bytes later | wherever the allocator put it | | Bytes per fetched cache line that belong to particles | all 64 | only the particle's own, plus whatever unrelated data shares its line | | Prefetcher | sees a constant stride | sees no pattern once addresses scatter | Three costs stack up in the pointer version: - **A dependent load.** The CPU cannot start reading particle i until the pointer to it has arrived, so a cache miss on the pointer array and a miss on the particle serialise. - **Scattered addresses.** Fresh allocations from a quiet heap may sit next to each other, but in a game that spawns and kills particles every frame they end up spread across the heap, each in a cache line shared with unrelated data. - **Allocation itself.** Creating a particle costs a call to `operator new` and destroying it a call to `operator delete`; the vector of values pays one allocation for many particles. One measured run on this author's machine (a million particles, pointers shuffled to imitate churn) took more than ten times longer for the pointer version. The ratio depends on the CPU, the allocator and the access history; the direction does not. ## Why the pointer version exists, and what to use instead Nobody writes `std::vector<std::unique_ptr<Particle>>` for fun. The usual reasons and their contiguous replacements: 1. **Polymorphism.** A `std::vector<std::unique_ptr<Emitter>>` can hold several derived types. Keep **one `std::vector` per concrete type** and run one loop each, or store a `std::variant` of the types by value. 2. **Stable addresses.** Growing a vector reallocates and invalidates pointers and references to its elements. Hand out **indices or handles** instead of raw pointers, or `reserve` the final size up front. 3. **Cheap moves of big objects.** Moving a pointer is cheap; moving a 2 KB object is not. That argues for keeping the big object's rarely used parts elsewhere, which is hot/cold splitting, not for a pointer per element. ## What reserve does and does not fix `v.reserve(n)` sizes the vector's **own** array. For `std::vector<Particle>` that means the particles: one allocation up front, no reallocation while the population stays under `n`, and stable element addresses until then. For `std::vector<std::unique_ptr<Particle>>` it reserves room for `n` **pointers** only; every `std::make_unique<Particle>()` still calls `operator new` for its own object, wherever the allocator decides. `reserve` therefore removes regrowth cost from both versions but makes only the value version contiguous in the sense that matters to the update loop. ## Node-based containers pay the same price `std::list`, `std::map`, `std::set` and the node storage of `std::unordered_map` allocate **one node per element** and link them with pointers. Iterating them is a pointer chase of exactly the kind shown above, which is why a sorted `std::vector` with `std::lower_bound` often beats `std::map` for a small read-mostly table, and why C++23 added `std::flat_map` as a contiguous alternative. Choosing a container in general belongs to the material on containers; the point here is the memory traffic of iterating one. ## How to check it yourself - Print `&v[1]` minus `&v[0]` for the value vector: it is always `sizeof(Particle)`. - Time both loops on a realistic population that has been allocated and freed in mixed order, not on a freshly built one, where the allocator may still hand out neighbouring addresses. - Read the hardware counters for cache misses with a sampling profiler rather than guessing; measurement technique is covered with benchmarks and profiling.
- Particles come in three types with different update code. How do you keep them contiguous without a vector of base-class pointers?Keep one `std::vector` per concrete type and run one loop per vector, so each loop walks contiguous memory and its update call is a direct call the compiler can inline. If one sequence must hold all types, a `std::vector<std::variant<Spark, Smoke, Debris>>` stores them by value, each slot as large as the biggest alternative, and `std::visit` dispatches without an extra pointer load.
- Systems hold Particle* pointers into the vector, and particles keep spawning. What goes wrong, and what do you hand out instead?When `push_back` exceeds the capacity, the vector reallocates and every pointer, reference and iterator into it dangles. Hand out an index, or a handle of index plus generation counter, and look the particle up when needed. `reserve` with the known maximum also prevents reallocation, and `std::deque` keeps references valid on insertion at either end, at the cost of block-wise rather than fully contiguous storage.
A vector of values is a shelf of books in order; a vector of pointers is a shelf of index cards, each telling you which room the book is in. Reading every book is far quicker from the shelf.
- Both loops are O(n), so the container cannot change the running time much.
- A unique_ptr updates a reference count on every access, and that is the slowdown.
- Calling reserve on the vector of unique_ptr makes the particles themselves contiguous.
- unique_ptr::operator-> stays an out-of-line function call even with optimisation on.
- std::vector may keep its elements in separate chunks the way std::deque does.