Templates, Code Bloat, and Link Time

Fifty source files include <vector> and call push_back on a std::vector<int>. Each of them compiles the same member function from the same source text into the same machine code. Then, as cppreference puts it, at link time identical instantiations generated by different translation units are merged. Forty-nine copies are discarded. The compiler did the work fifty times so the linker could throw most of it away.

That is not a bug in anyone’s build system. It falls directly out of the instantiation model. cppreference states that the definition of a class template must be visible at the point of implicit instantiation, which is why template libraries typically provide all template definitions in the headers, giving most Boost libraries as the example of header-only distribution. Header-only means every consumer instantiates independently, and the merge rule exists because without it the first nontrivial use would be a duplicate-symbol error.

The idea

The unit of cost is the distinct template argument list, not the call site. Ten thousand calls to std::vector<int>::push_back cost one instantiation. Ten types instantiated with an allocator they never touch cost ten. Every technique in this note is the same move applied at a different scale: find a piece of code that was parameterized on something it does not actually use, and take the parameter away. Reducing uses does nothing. Reducing distinct argument lists is the entire game.

Where the copies come from

Three multipliers stack.

The first is the one above. Compile time is paid per translation unit and per distinct specialization, and the linker’s merge only reclaims object size, not the time already spent. This is what explicit instantiation attacks: an explicit instantiation declaration, extern template class Vec<int>;, tells a translation unit not to instantiate at all. cppreference names the technique explicitly, saying it can be used to reduce compilation times by declaring the instantiation in all but one of the source files using it and defining it in the remaining file. It is a manual, per-specialization approximation of what separate compilation does for ordinary functions automatically.

The second is virtual functions in class templates, and it is worse than it looks. The C++ Core Guidelines note that in a class template, non-virtual functions are only instantiated if they are used, but virtual functions are instantiated every time. Rule T.80 works the example: a Container<T> interface with get, first, next, and sort as virtual functions, and a Vector<T> deriving from it. Given that, the Guidelines observe, the compiler cannot know if vector<int>::sort() is called, so it must generate code for it, and likewise for vector<string>::sort(). Unless those two functions are called, that is code bloat. They add that the same instantiation-every-time rule might overconstrain a generic type by instantiating functionality that is never needed, and that the standard-library facets made this mistake.

The third is over-parameterization, which is the subtle one.

SCARY, and the parameter that was never used

Guidelines rule T.61 is titled “Do not over-parameterize members (SCARY)” and its reason is one sentence: a member that does not depend on a template parameter cannot be used except for a specific template argument, which limits use and typically increases code size.

The example is a linked list:

template<typename T, typename A = std::allocator<T>>
class List {
public:
    struct Link {   // does not depend on A
        T elem;
        Link* pre;
        Link* suc;
    };
    using iterator = Link*;
    // ...
};

Link holds a T and two pointers. It has nothing to do with the allocator. But because it is nested inside List<T, A>, the Guidelines point out, Link formally depends on the allocator even though it does not use it, and this forces redundant instantiations that can be surprisingly costly in some real-world scenarios. List<int>::Link and List<int, My_allocator>::Link are unrelated types, and an iterator obtained from one cannot be handed to code expecting the other.

The fix is to lift Link out of the class and give it its own minimal parameter list, so both lists share one Link<T>. The Guidelines record the reaction and the name: some people found the idea that the Link no longer was hidden inside the list scary, so the technique was named SCARY, for assignments and initializations that are seemingly erroneous, appearing constrained by conflicting generic parameters, but actually work with the right implementation, unconstrained by the conflict due to minimized dependencies.

Rule T.62 generalizes it past nested types: place non-dependent class template members in a non-templated base class, so that the base class members can be used without specifying template arguments and without template instantiation. Rule T.84 pushes the same idea all the way to the module boundary, recommending a non-template core implementation to provide an ABI-stable interface, for the stated reasons of improving stability and avoiding code bloat, with a Link_base holding the raw pointers and a Link<T> template adding the type-safe wrapper on top.

The pattern under all three is the same as the one under std::string holding characters rather than being parameterized on a storage policy: put the code that does not vary somewhere it cannot be duplicated.

The work inside the body

Even a template with a single parameter can be fatter than it needs to be. The Guidelines make the point while discussing a const-deducing helper, noting that you should not do large non-dependent work inside a template, because it leads to code bloat, and that a further improvement would be to factor out all or part of the helper into a common non-template function for a potentially big reduction in code size.

That is the thin-template idiom stated as a rule. The template is the part that has to be regenerated per type. Anything inside it that could have been written once should be written once, called from the template, and left alone by the instantiation machinery.

What it costs, and what it buys

Object size is the visible cost, and it is not purely a disk number. Duplicated instantiations occupy instruction cache and page in through the same memory hierarchy as everything else, so code that is generated but rarely called still competes for the fastest storage in the machine. Link time is the other visible cost, since the linker has to see every copy before it can merge them.

Against that sits the reason anyone accepts it. Per-specialization code generation is what allows the generated code to be as specific as hand-written code for that type: no indirect call, no boxing, and full visibility for the optimizer. That is the trade monomorphization versus erasure describes in general terms, and Rust’s version of it is the same bargain reached from the other direction. Rust type-checks the generic once at its definition and then monomorphizes, so the duplication is a code-size problem only. C++ has no definition-site check, so its per-specialization generation is doing double duty: it is the code generation strategy and the type checking strategy. That is why C++ template errors historically arrived from inside the implementation, and why the cure had to be constraints stated at the interface rather than a change to how code is emitted.

The diagnostic question

When a build is slow or a binary is fat, do not count call sites. Count distinct template argument lists, and for each one ask which of its parameters the emitted code actually reads. Every parameter that turns out to be unused is a multiplier you are paying for nothing.

Related Notes

• Monomorphization and Code Bloat - the same cost model with a definition-site type check in front of it
• Generics: Monomorphization vs Erasure - the cross-language version of this trade
• Template Instantiation and the Two-Phase Rule - what triggers a copy, and how to tell a translation unit not to make one
• Modules, Signatures, and Separate Compilation - the boundary header-only generic code gives up
• Memory Hierarchy and Caching - why generated code size is a runtime concern and not only a build one
• Build Systems and Dependency Management - where the compile-time half of this bill actually lands

Sources

• “Templates,” cppreference.com. https://en.cppreference.com/w/cpp/language/templates.html . Supports link-time merging of identical instantiations from different translation units, and the requirement that a class template definition be visible at the point of implicit instantiation with the resulting header-only distribution convention.
• “Class template,” cppreference.com. https://en.cppreference.com/w/cpp/language/class_template.html . Supports explicit instantiation declarations skipping implicit instantiation and their stated use for reducing compilation times.
• “C++ Core Guidelines,” isocpp.github.io. https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines . Supports T.61 including the List and Link example, the redundant-instantiation cost, and the SCARY acronym; T.62 on non-dependent members in a non-templated base; T.80 on templatized hierarchies with the sort example; the note that virtual functions in a class template are instantiated every time while non-virtual ones are not, with the facets remark; T.84 on a non-template core for ABI stability; and the advice against large non-dependent work inside a template.