In a C++ 3D math library, summing virtual Shape::area() over std::vector<std::unique_ptr<Shape>> is much slower than a template loop over std::vector<Disc>; what does the template change, and what does it cost?
answer
- a known target can be inlined
- inlining unlocks vectorisation
- an indirect call per element
- a template over a virtual type
- one container per concrete type
basics
~20 sWith the template the element type is known at compile time, so Disc::area is a direct call the compiler inlines and then vectorises. The virtual loop chases a pointer per element and makes an indirect call the optimiser cannot see through.
solid answer
~50 sIn the virtual loop each element costs a load of the `unique_ptr`, a load of the object's vtable pointer, a load of the `area` slot and an **indirect call** to an unknown function, plus a pointer chase to wherever the object lives. Because the compiler cannot see the callee, the call is an optimisation barrier: nothing is inlined, nothing is vectorised, and values are spilled around each call. `template <class S> float totalArea(const std::vector<S>&)` instantiated for a plain `Disc` with a non-virtual `area()` turns the call into a direct one, inlines it, and the loop over contiguous `Disc` values can use SIMD multiplications. Two catches: if `S` is a class that still overrides a virtual `area` and is not `final`, the call through `const S&` stays virtual; and the template costs one container and one instantiated loop per concrete type, more code and no run-time extensibility.
code
cpp · 39 lines#include <cstdio>
#include <memory>
#include <vector>
struct Shape { // runtime polymorphism
virtual ~Shape() = default;
virtual float area() const = 0;
};
struct Circle : Shape {
float r = 1.0f;
float area() const override { return 3.14159265f * r * r; }
};
struct Disc { // no virtual functions: a plain value type
float r = 1.0f;
float area() const { return 3.14159265f * r * r; }
};
float totalArea(const std::vector<std::unique_ptr<Shape>>& shapes) {
float sum = 0.0f;
for (const auto& s : shapes) sum += s->area(); // indirect call per element
return sum;
}
template <class S>
float totalArea(const std::vector<S>& shapes) {
float sum = 0.0f;
for (const S& s : shapes) sum += s.area(); // S::area is known: inlined
return sum;
}
template float totalArea<Disc>(const std::vector<Disc>&);
template float totalArea<Circle>(const std::vector<Circle>&);
int main() {
std::vector<std::unique_ptr<Shape>> mixed;
for (int i = 0; i < 1000; ++i) mixed.push_back(std::make_unique<Circle>());
std::vector<Disc> discs(1000);
std::printf("%.1f %.1f\n", totalArea(mixed), totalArea(discs));
}go deeper
Know that a virtual call picks its target at run time while a template's call target is fixed at compile time.
Explain that the known target lets the compiler inline, and that inlining is what enables vectorisation and constant folding.
Spot the non-final virtual type inside a template, read the loop's assembly for indirect calls, and weigh bucketing or batching.
Decide where the library offers run-time extensibility and where it fixes types for speed, and keep that boundary out of hot loops.
## What each loop compiles to ```cpp float totalArea(const std::vector<std::unique_ptr<Shape>>& shapes); // runtime polymorphism template <class S> float totalArea(const std::vector<S>& shapes); // compile-time polymorphism ``` | Step per element | Virtual loop | Template loop over `std::vector<Disc>` | |---|---|---| | Find the object | load the `unique_ptr`, then follow it | next element of a contiguous array | | Find the code | load the vtable pointer, load the `area` slot | known at compile time | | Call | indirect call, cannot be inlined | inlined; no call remains | | What the optimiser sees | an opaque call that may read or write any memory | `3.14159265f * r * r` and an addition | The vtable mechanism itself belongs to the material on virtual dispatch; what matters here is its consequence for optimisation. ## Why inlining is the multiplier The indirect call's own cost, a few cycles when the branch predictor guesses the target, is rarely the main problem. The bigger loss is everything the optimiser cannot do across an unknown call: - **No vectorisation.** In the arm64 output below the `Disc` loop multiplies four radii per instruction; the virtual loop handles one element per call. - **No constant folding or hoisting.** `3.14159265f` and other invariants cannot be lifted out of a loop whose body is a call. - **Spills.** Values live across the call must be kept in callee-saved registers or memory. - **Pessimistic memory assumptions.** An unknown function may write anything, so values the loop already loaded may be reloaded after every call. That is the meaning of "zero-cost abstraction" in C++: a function, template or small wrapper costs nothing **once inlined**. An abstraction that blocks inlining in a hot loop is not zero-cost, whatever its syntax. ## The trap: a template over a polymorphic type The speed comes from the call being **non-virtual**, not from the word `template`. Instantiate the same template with `Circle`, a class that overrides virtual `Shape::area`: - `s.area()` through `const Circle&` is still a virtual call, because the object behind the reference could be a class derived from `Circle`; - the arm64 listing for `totalArea<Circle>` shows the vtable load and the `blr` indirect call in the loop; - marking `Circle` (or its `area`) `final` lets the compiler call `Circle::area` directly and inline it; devirtualisation rules are covered with virtual dispatch. ## What the template costs 1. **One container per concrete type.** A scene with spheres, boxes and capsules needs three vectors and three loops instead of one heterogeneous list. 2. **No run-time extensibility.** A plugin cannot add a new shape type without recompiling the code that instantiates the loop. 3. **Code size and compile time.** Every instantiation is a separate function; dozens of types times dozens of algorithms add up, and the instruction cache pays for it. 4. **Interfaces leak into headers.** Template code must be visible where it is instantiated. ## Middle grounds - **Bucket by type**: keep `std::vector<Disc>`, `std::vector<Box>` and so on, and run one template loop per bucket; the dispatch happens once per bucket, not per element. - **Batch the virtual call**: make the virtual function process a whole range, for example `virtual float totalArea() const` on a container type, so one indirect call covers thousands of elements and the loop inside is inlined. - **`std::variant` of the shape types** in one `std::vector`, visited per element: values stay contiguous and the dispatch is one the compiler can see, though it is still a per-element branch. ## Measuring the claim - Benchmark both with a realistic mix of types and sizes. With one concrete type in the vector, the indirect branch always goes to the same target and is predicted well, which hides part of the cost; a shuffled mix of five types is a fairer test. - Read the assembly for the hot loop: an indirect `call` or `blr` inside it means the abstraction is not free, and a vector multiply such as `mulps` or `fmul.4s` shows the inlined version paid off. - Check that the comparison is fair: the template version also stores values contiguously, so part of its gain is memory layout rather than dispatch, and both effects should be named when reporting the result.
- Why does std::sort with a lambda comparator usually beat qsort with a function pointer on the same data?`std::sort` is a template instantiated with the lambda's own closure type, so the comparison is a direct call the compiler inlines into the sorting loop, often down to one compare instruction. `qsort` receives a `void*`-based function pointer it calls for every comparison, and the library's compiled code cannot see or inline it.
- When is the virtual loop the right choice even in performance-sensitive code?When the per-element work is large compared with a call, such as a shape whose area triggers a tessellation, or the set of types is open-ended and loaded at run time. Then a few nanoseconds of dispatch are noise, and batching the virtual call over a range keeps the hottest inner loops inlined anyway.
- Templates are faster because template code is compiled with more optimisation.
- Any template instantiation removes virtual dispatch, even for a non-final class.
- The indirect call's few cycles are the whole cost of the virtual loop.
- Zero-cost abstraction means a template never adds code size or compile time.
- A virtual call can never be inlined under any circumstances.