Are all template instantiations created at compile time?

Question

After learning about variadic function templates that use recursion, I am wondering:

Are all template instantiations that can possibly be needed during the program's execution created at compile time? Is there such thing as instantiation on-the-fly?

Answer 1

Templates are instantiated in the process of converting each translated translation unit into an instantiation unit.

A translation unit is essentially a source file.

A translated translation unit (try to say that three times fast) is the output from compilation without templates instantiated.

An instantiation unit is essentially the translated translation unit with templates instantiated.

Whether the instantiation occurs at "compile time" depends on the architecture of the implementation.

In a traditional "compile to objects and link the objects" architecture (which most developers working under windows or linux will be familiar with) the generation of translated translation units and generation of instantiation units are both phases (possibly combined phases) of the compiler. So, in this model, instantiation is a compile time activity.

However, there are implementations that use a "smart linker", and the compiler outputs translated translation units, with some auxiliary information that describes what template instantiations are needed by each translated translation unit. The process of converting those into an instantiation unit is then handled by the linker. With such implementations, template instantation is therefore a link-time activity rather than a compile time activity. The intent of this build model is that it provides opportunities for link-time optimisation (and the link-time template instantiation is more a side-effect than a goal).

The first implementation with a smart linker I encountered was available as an additional-cost option from Sun Microsystems on SunOS and later Solaris (those operating systems shipped by default with a toolchain that included a more typical dumb linker). I've encountered a couple of other such toolchains since, but can't recall their vendors offhand.

I'm not aware of any implementations where template instantiation occurs at run time. Conceivably, however, a C++ interpreter might work this way.

Answer 2

All template instantiations are created on compile time. Quote from standard:

N4296 2.2/1/8[lex.phases]

Translated translation units and instantiation units are combined as follows: [ Note: Some or all of these may be supplied from a library. — end note ] Each translated translation unit is examined to produce a list of required instantiations. [ Note: This may include instantiations which have been explicitly requested (14.7.2). — end note ] The definitions of the required templates are located. It is implementation-defined whether the source of the translation units containing these definitions is required to be available. [ Note: An implementation could encode sufficient information into the translated translation unit so as to ensure the source is not required here. — end note ] All the required instantiations are performed to produce instantiation units. [ Note: These are similar to translated translation units, but contain no references to uninstantiated templates and no template definitions. — end note ] The program is ill-formed if any instantiation fails.