14

From what I understand, if you have, for example, an std::vector<int> and an std::vector<float>, the compiler creates two classes, one for each type. Thus, although you reduce the amount of code written, you do not reduce executable size (correct me if I'm wrong).

Is the same true even if the type is a pointer? For example, would instantiating an std::vector<SomeClass*> and an std::vector<SomeOtherClass*> necessarily cause the compiler to generate separate code for each of the two instantiations?

7
  • 5
    Semantically, the classes std::vector<SomeClass*> and std::vector<SomeOtherClass*> are different, but it may be that, due to optimization, the compiler is able to share code between them, so that, for some or all routines of an instantiated template, only one set of code is generated. Is that what you intended to ask? Dec 17, 2012 at 12:23
  • 1
    @Najzero I don't see any mix up, the executable also requires memory to be loaded. If your executable grows, so does your memory requirements. Dec 17, 2012 at 12:24
  • 2
    @Najzero Umm, what? The point of the question is whether having both vector<A*> and vector<B*> will result in two sets of vector member function implementations in the code of the executable. Which indeed does affect executable size (depending on how much inlining occurs, of course). Dec 17, 2012 at 12:26
  • 1
    @EricPostpischil I suppose I meant that, yes, though I hadn't considered there was a difference!
    – Anthony
    Dec 17, 2012 at 12:27
  • 1
    Besides, the compiler only generates code for methods that are actually used for each class. This allows writing templates with methods that would be illegal for some template parameters, as long as you don't use these parameters. E.g. std::list<T>::sort() is illegal if T has no operator< defined, but you can create an std::list<T> providing that you don't try to sort it.
    – Gorpik
    Dec 17, 2012 at 12:27

5 Answers 5

8

This is an implementation dependent as-if optimization and, as thus, is permitted!

In fact, this does not even have to be done by the compiler. The standard library can implemented that way. For example, an implementation could use std::is_pointer and then defer everything to a single void* based implementation. (This is the Thin Template idiom). In fact, doing this on the library side seems to be more feasible than the compiler merging code after instantiating it, but that is possible as well.

0
6

The compiler instantiates as many classes from the template as your program uses. Code generated to go in your executable is a slightly different matter, though, from what classes exist in your program.

In practice, most operations on vector will be inlined. So the executable size probably doesn't change very much according to how many different classes are instantiated from that template because the bulk of the code size is per function call site rather than per distinct class. But as far as it does depend on the number of instantiations, vector<SomeClass*> and vector<SomeOtherClass*> are different classes.

If you do an explicit instantiation of vector, then all the member functions will get generated for the class. You'll probably see that difference in code size, if you look for it. But normally you don't explicitly instantiate template classes, and so only the member functions you use are generated.

3
  • 2
    An explicit instantiation is a semantic operation: It causes corresponding declarations and definitions of the instance to exist. It does not compel generation of code for functions. The compiler is free not to generate code for functions that are not used. Dec 17, 2012 at 12:39
  • @EricPostpischil: But you can combine an explicit instantiation in one TU with an extern declaration of the same instantiation in another. In practice, compilers do generate the code for functions that can be accessed from other TUs. Quite aside from the separation between compilation and link phases, they're left in to support dlls. In principle of course the standard doesn't mandate any such mechanism, but neither does it talk about "executable size". So from the strict POV of the standard, you could argue that nothing "reduces executable size". It's all implementation detail. Dec 17, 2012 at 12:42
  • Btw, I agree with your answer of course. There's nothing to stop the compiler (or for that matter the linker, or some run-time mechanism) from identifying common pieces of code and reducing the executable size by sharing them. The common code could have originated from templates or otherwise. Since this is the opposite of inlining I doubt much of it will happen for normal uses of vector on common compilers. That's speculation on my part, I haven't checked. For something potentially bulky like std::sort it might be more important whether identical code is folded. Dec 17, 2012 at 12:48
5

It is permissible for the compiler to generate a single set of code that implements both instantiations of a template, provided the resulting behavior is correct. This can happen for pointer types and for non-pointer types. It can happen independently for each routine (a.k.a. “method”) in a template class.

It may be difficult to determine when this can happen, and a compiler might or might not recognize opportunities to do so.

For example, if a routine merely copies a class, as an assignment operator typically does, then it may be possible to use the same code for any instantiation of the template in which the class data has the same size. Code to add two int objects may be the same as code to add to unsigned int objects, on some processors.

5
  • 1
    Note that &vector<SomeClass*>::push_back and &vector<SomeOtherClass*>::push_back are required to compare unequal. This means that the compiler can only fold functions where it can determine that this code doesn't exist anywhere in the program. (If the amount of code generated were significant, the implementation could hoist common parts up into a non-template base class.) Dec 17, 2012 at 12:55
  • @JamesKanze: And a good optimizer would solve that problem with LabelForSomeClass: nop; LabelForSomeOtherClass: …remainder of code…. That is, essentially all of the code would be common; a simple nop or branch would create a distinct address. Dec 17, 2012 at 13:02
  • The "identical comdat folding" that the MS compiler does is actually done in the linker (which allows it to be done across separate translation units) and I don't know if the linker can adjust entry points like that, or if that would have to have been done by the compiler prior to linking. Dec 17, 2012 at 13:48
  • @EricPostpischil Solutions are certainly possible. I don't think many compilers bother; the size of the execution image doesn't seem to be a high priority for them. Dec 18, 2012 at 8:40
  • @JamesKanze Comparing two incompatible function pointers is illegal in C++, so there is nothing wrong in making them point to the same address.
    – Karol S
    May 25, 2022 at 10:02
4

Yes, you're right. There are ways to mitigate the duplication, see slides 18-26 in my Diet Templates presentation.

At one point is was "common knowledge" that std::vector<T*> and std::vector<U*> could both be implemented as thin wrappers around a vector_impl<void*> specialization, so they share the same generated code where possible (this is what I refer to as hoisting in my slides) but I don't think modern std::lib implementations actually do that optimisation. Certainly libstdc++ doesn't.

2

The compiler doesn't "create two classes". Rather, std::vector<int> and std::vector<float> are two distinct classes. Don't confuse classes and templates — those are core concepts of the lan­guage! And similarly, std::vector<SomeClass *> and std::vector<SomeOtherClass *> are two distinct classes, which should answer your question.

5
  • 5
    Although the body of the question asks about creating two classes, the title shows that the concern is whether code is duplicated. This answer does not answer that question. Dec 17, 2012 at 12:24
  • I guess you could still say that the compiler creates those two classes by instantiating the class template, though. Dec 17, 2012 at 12:26
  • @Angew: Leave the compiler out of it. The compiler has nothing to do with the language rules, and the language rules are quite happy independent of any compiler...
    – Kerrek SB
    Dec 17, 2012 at 12:27
  • @KerrekSB OK, but even without the compiler, one could say that "instantiating a class template creates a class." Dec 17, 2012 at 12:31
  • @Angew: That's right, and that's basically what I'm saying :-)
    – Kerrek SB
    Dec 17, 2012 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.