17

Does the C++ Standard actually mandate that templates must be instantiated at compile-time, not run-time?

If not, is it a convention that we use purely because it obviously makes sense to do it that way? Or is there some practical reason that would, theoretically, prevent an implementation from existing that can instantiate templates at run-time?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055

3 Answers3

14

All the standard requires is that the observable behavior be as if the templates were instantiated before the program started to run. Any errors, for example, would have to trigger a message in some phase of the compilation, or at least before runtime. In theory, a compiler could probably defer full instantiation until runtime, but in practice, it would have to have done most of the work at compile time anyway, in order to be sure that any potential error messages appeared.

In a stricter sense, the standard considers "translation" as a unit; an implementation could, and implementations have (and I think some still do) defer instantiation until link time. Which leads to interesting questions when dynamic linking is involved. But the standard is silent about that: dynamic linking is really undefined behavior, as far as the standard is concerned, so it is up to the implementation.

In the end, however: instantiating templates is one of the most expensive operations a compiler does, and requires a very large and complex mechanism. Which no vendor wants to impose on an executable. So regardless of the loopholes, don't expect to see run time instantiation any time soon. Especially as it wouldn't buy you anything anyway: the standard requires that all templates can be instantiated at compile time, so you couldn't instantiate a template somehow dependent on a runtime argument and still be standard conform.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • 6
    "don't expect to see compile-time instantiation" `s/compile/run/` ? – Lightness Races in Orbit May 12 '11 at 15:32
  • Good answer, thanks. Could you stick some citations in there? – Lightness Races in Orbit May 12 '11 at 15:32
  • @Tomalak Citations are difficult, because it's spread out and done very indirectly: the restrictions on non-type arguments being compile time constants would be an example: even with runtime instantiation, the argument for `template class C{};` must be an integral constant expression, for example; if it is a variable, the compiler must issue a diagnostic. – James Kanze May 12 '11 at 15:43
  • @Tomalak A program which explicitly loads DLL's does have the option of using `system()` to invoke the compiler to generate them from source. I don't know if that would be considered runtime instantiation of templates which are in the source, however.:-) – James Kanze May 12 '11 at 15:45
  • @JamesKanze, did you silently mean _yes_ to LightnessRacesinOrbit's first comment? – Enlico Dec 13 '18 at 16:41
11

You can't create types in a C++ program at run time (while it is running); they are all known at compile time. Even dynamically loaded shared libraries don't change that; the set of types in the library is known at compile time (when the library is compiled), and the loading program must be able to handle the types that the library exposes.

So, there is no need for template evaluation at run time; the information is all known at compile time.

If you were to instantiate templates at run time, you'd need the compiler and the linker services as part of the run time. That greatly complicates the required run time environment - to no obvious advantage.

Clearly, an interpretive C++ system could, probably would, defer the template instantiation until needed - JIT (just in time) processing. But the compilation is still done before the code is executed.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Does the standard itself explicitly say this? Or is it just something that makes sense, and doesn't need explicitly stating in the standard? (Of course, I understand how templates work; I'm just wondering how much of how they work is mandated specifically by the C++ spec and how much of it is just filled by common sense.) – Lightness Races in Orbit May 12 '11 at 14:46
  • 1
    I don't buy this explanation.int is known at compile time but the object are instantiated at run time. – John Dibling May 12 '11 at 14:48
  • @Tomalak: The C++ standard does not explicitly say how the compilation must be done, or how programs are assembled, or when lots of things occur. It leaves those issues to the implementation. It simply specifies the required behaviour of the working program. – Jonathan Leffler May 12 '11 at 14:55
  • 1
    @John: individual objects are instantiated at run time, but the type of the objects that can be instantiated are known at compile time, even if you use a Factory constructor method. Ultimately, all the types in the program are known at compile time. – Jonathan Leffler May 12 '11 at 14:56
  • 2
    GNU suggests the linker might someday re-invoke the compiler with saved state to do the instantiation. Read http://gcc.gnu.org/onlinedocs/gcc/Template-Instantiation.html – Erik Olson May 12 '11 at 17:57
  • @Erik: interesting, and thanks for the URL - but still everything would be resolved prior to running the program. – Jonathan Leffler May 12 '11 at 18:51
0

I'm not in the habit of reading the standard, but Stroustrup's C++ Programming Language is usefully precise.

A.9 Templates: gives the grammar for template declaration; the type-parameter is one of class, typename, or another template - so the type is known, static. (it's not dynamic. one could imagine giving a typeinfo object if C++ were a dynamic language. But that wasn't your question.)

C.13.8.3 Point of Instantiation Binding: says that the point of instantiation for a template is just before the declaration using it.

The example given is concerned with resolving names in the template definition to the correct scope. This would be very hard to do at run-time!

e.g. from Stroustrup C.13.8.3:

template<class T> void f(T a) { g(a); }

void g(int);

void h()
{
    extern g(double);
    f(2);
}

"Here the point of instantiation for f is just before h(), so the g() called in f() is the global g(int) rather than the local g(double)."

I guess this doesn't rule out JIT, but as a practical matter, instantiating the template f requires knowing the correct scoped resolution of g at a particular line. As Jonathan says, you'd need the compiler's services as part of the run-time, along with the full context built up in the compiler while compiling that unit. If that's not a "compile-time" job, I don't know what is.

EDIT: This all relies on an antique version of the C++ standard.

Erik Olson
  • 1,154
  • 8
  • 18
  • 2
    Non-dependent names like `g` are looked up at template *definition* time, and must be visible then: your code snippet correctly fails compilation on Comeau with 'identifier "g" is undefined'. (You also need a return type for `extern g(double)` BTW.) When you think about it this is the only sensible way, since if it looked up these names at instantation time, what code got run would depend on what declarations were in scope before the call, which can vary a lot, making template instantiation very fragile. – j_random_hacker May 12 '11 at 15:49
  • 1
    Not relevant - g IS a dependent name (depends on T), so it's looked up at instantiation time. BTW, snippet is from Stroustrup, 2000, and except for missing return type, my g++ 4.1.2 compiles it. I didn't know about Comeau until now (nice to have), but I don't think they're right. – Erik Olson May 12 '11 at 17:55
  • 1
    Comeau has their own -tused option to instantiate the template where it is defined. This makes Comeau's behavior non-standard. See Stroustrup C.13.8.2, "[in a definition] If a name is dependent, looking for its definition is postponed until instantiation." – Erik Olson May 12 '11 at 19:04
  • You're right, `g` is a dependent name. But according to my reading of 14.6.4/1 in the 2003 standard, you (and g++, and Comeau w/o -tused, and even Stroustrup!) are wrong about whether this is legal code: "In resolving dependent names, names from the following sources are considered: Declarations that are visible at the point of definition of the template; Declarations from namespaces associated with the types of the function arguments both from the instantiation context and from the definition context." `g` is not declared prior to definition, and `int` has no associated namespaces. – j_random_hacker May 12 '11 at 21:56
  • This exact problem seems to have popped up here: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23885#c6 The Intel dev came to the same conclusion as me -- that the code should fail to compile. (BTW the fact that Stroustrup's book came out in 2000 makes things clearer -- the standard didn't come out till 2003.) Don't you love C++? :-P – j_random_hacker May 12 '11 at 21:59
  • OK, I get it. I read Draft standard N3242 (Feb 2011) §14.6.4.1/1, Point of Instantiation is after the scope of the first use, just as described in Stroustrup (2000) but by §3.4.2, if “int” is the argument type, instantiation context for dependent names in f contains nothing that was not visible at the definition. So to make Stroustrup’s point today, you must specialize f and g(T) on some class, not a primitive type, to bring in T’s enclosing namespace. One less barrier to JIT instantiation, FWIW. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf for those following. – Erik Olson May 13 '11 at 20:44
  • @j_random_hacker: Actually, the first standard was ratified in 1998. – Lightness Races in Orbit Nov 17 '12 at 21:22