How does C++ link template instances

Question

If I define a function (maybe a class member function but not inlined) in a header file that is included by two different translation units I get a link error since that function is multiply defined. Not so with templates since they are not compilable types until the compiler resolves a declaration of an object of a templatized type. This made me realize I don't know where compiled template code resides and how it is linked since C++ does not just create multiple copies of code to define SomeTemplateClass. Any info would be appreciated. Thanks!

Answer 1

There are 3 implementation schemes used by C++ compilers:

• greedy instantiation, where the compiler generates an instantiation in each compilation unit that uses it, then the linker throws away all but one of them (this is not just a code-size optimization, it's required so that function addresses, static variables, and the like are unique). This is the most common model.

• queried instantiation, where the compiler has a database of instantiations already done. When an instantiation is needed, the DB is checked and updated. The only compiler I know which uses this is Sun's, and it isn't used by default anymore.

• iterated instantiation, where the instantiations are made by the linker (either directly or by assigning them to a compilation unit, which will then be recompiled). This is the model used by CFront -- i.e. historically it was the first one used -- and also by compilers using the EDG front-end (with some optimisations compared to CFront).

(See C++ Templates, The Complete Guide by David Vandevoorde and Nicolai Josuttis. Another online reference is http://www.bourguet.org/v2/cpplang/export.pdf, which is more concerned about the compilation model but still has descriptions of the instantiation mechanisms).

Answer 2

All template functions are implicitly inline. Just as methods defined in the class declaration are implicitly inline.

When I say implicitly inline I mean the more modern usage of the word. See my lengthy description here.

In short, inline, static, and extern are all sibling linkage directives. inline tells the linker to ignore duplicate definitions of a function. Generally this means the linker will pick one definition and use it for all compilation units. I don't know of any compilers that do or did leave all duplicate template code in the final executable.

Where are template instantiations stored?
They are stored in the same way in the same place as inline functions. The details of that are compiler specific.

Answer 3

This is implementation specific.

Some compilers will generate the same template instances over and over for each translation unit they are instantiated in and let the linker fold the duplicates.
Templates got a bad reputation for "code bloat" when linkers weren't yet up to that task. Nowadays this is probably undeserved. Some implementations will even fold different instantiations when they compile to the same target machine code. (Like f<A*>() and f<B*>(), as pointer types are just addresses in the generated machine code.)

Others will defer template compilation until link-time instead, and there might be still other ways to deal with this. As I said, it's up to the implementation.

These all have different advantages and disadvantages. Absent of a true module concept I doubt anyone will come up with the perfect scheme.

With export there used to be a requirement for compilers to pre-compile template code and instantiate at request. However, except for one vendor nobody implemented export for their compiler, and now it's removed.

Answer 4

It actually does create multiple copies. Those copies are special and don't violate the one-definition rule. Some linkers will come along, remove the copies, and relink the functions using them; not all do.