When does implicit template instantiation occur?

Question

I wonder when/where implicit template instantiation occurs in the following situation.

// temp.h
template <typename T>
struct A {
    T value;
}

// foo.h
#include "temp.h"
void foo();

// foo.cpp
#include "foo.h"
void foo() { A<int> _foo; }

// bar.h
#include "temp.h"
void bar();

// bar.cpp
#include "bar.h"
void bar() { A<int> _bar; }

// main.cpp
#include "foo.h"
#include "bar.h"
int main() { foo(); bar(); return 0; }

I think it occurs when foo() is called because it is the first use of A<int>, so A<int> is implemented at foo.o.
And, when bar() is called, it linked to A<int> at foo.o.

Am I right? Or instantiation occurs twice?

Answer 1

The standard doesn't say anything about how compiler should instantiate template implicitly.

I'm not sure about other compiler, this is how g++ deals with it, from 7.5 Where's the Template?:

Somehow the compiler and linker have to make sure that each template instance occurs exactly once in the executable if it is needed, and not at all otherwise. There are two basic approaches to this problem, which are referred to as the Borland model and the Cfront model.

• Borland model:

Borland C++ solved the template instantiation problem by adding the code equivalent of common blocks to their linker; the compiler emits template instances in each translation unit that uses them, and the linker collapses them together. The advantage of this model is that the linker only has to consider the object files themselves; there is no external complexity to worry about. The disadvantage is that compilation time is increased because the template code is being compiled repeatedly. Code written for this model tends to include definitions of all templates in the header file, since they must be seen to be instantiated.

• Cfront model:

The AT&T C++ translator, Cfront, solved the template instantiation problem by creating the notion of a template repository, an automatically maintained place where template instances are stored. A more modern version of the repository works as follows: As individual object files are built, the compiler places any template definitions and instantiations encountered in the repository. At link time, the link wrapper adds in the objects in the repository and compiles any needed instances that were not previously emitted. The advantages of this model are more optimal compilation speed and the ability to use the system linker; to implement the Borland model a compiler vendor also needs to replace the linker. The disadvantages are vastly increased complexity, and thus potential for error; for some code this can be just as transparent, but in practice it can been very difficult to build multiple programs in one directory and one program in multiple directories. Code written for this model tends to separate definitions of non-inline member templates into a separate file, which should be compiled separately.

This is how g++ implements it, emphasis is mine:

G++ implements the Borland model on targets where the linker supports it, including ELF targets (such as GNU/Linux), Mac OS X and Microsoft Windows. Otherwise G++ implements neither automatic model.

That said: with g++, each translation unit will have its own instantiation. It has been mentioned again in that page:

..., but each translation unit contains instances of each of the templates it uses. The duplicate instances will be discarded by the linker, but in a large program, this can lead to an unacceptable amount of code duplication in object files or shared libraries.

Your option to avoid it (of course first and last option is explicit):

1. Duplicate instances of a template can be avoided by defining an explicit instantiation in one object file, and preventing the compiler from doing implicit instantiations in any other object files by using an explicit instantiation declaration, using the extern template syntax

2. Compile your template-using code with -frepo. The compiler generates files with the extension .rpo listing all of the template instantiations used in the corresponding object files that could be instantiated there; the link wrapper, collect2, then updates the .rpo files to tell the compiler where to place those instantiations and rebuild any affected object files. The link-time overhead is negligible after the first pass, as the compiler continues to place the instantiations in the same files.

3. Compile your code with -fno-implicit-templates to disable the implicit generation of template instances, and explicitly instantiate all the ones you use.

Answer 2

According to GNU C++ compiler documentation (https://gcc.gnu.org/onlinedocs/gcc/Template-Instantiation.html) "each translation unit contains instances of each of the templates it uses". So unless your unused _foo and _bar objects are optimize out, both object files should have the duplicating instances. Then, "the duplicate instances will be discarded by the linker", which generally means that the order of linking decides which instance is used. But end result will still be no different in either of the two orders.