2

In C, partial compilation is possible since the entire *.c file can be compiled into machine code with resolution and relocation left for the linker to handle. This is just an issue of calculating the displacement certain instructions have in the final executable or knowing the absolute address for some global variable.

In C++ it would seem that almost the same can be done - there exists a fairly uncomplicated mapping between C++ code and equivalent C code (as far as mappings between programming languages go). However, templates seem to complicate things.

If I use, for instance, a std::vector<int> in 1.c, then, since the template class was specified by the <vector> header, the compiler can generate machine code for an int specification. Suppose in the same project there is a file 2.c which also relies on a std::vector<int> specialization, and that 1.o and 2.o must be linked. Is partial compilation of 1.c and 2.c to their own *.o files to be linked later possible?

As mentioned in the linked question in the comments below, there are two commonly used methods for this problem: both generate std::vector<int> code, or the linker goes through another round of "dependency compilations" where a single vector<int> is compiled and then linked to both files.

Regarding "greedy compilation" - does this mean that every use of template class methods in every compilation unit must be put in the linker relocation table? Also, certain calls may not use long jumps (i.e., a template class is defined right above the method using it). However, if the linker is going to force a compilation unit to use the specialization it has selected, then a long jump would be necessary - but the instruction size would be too large to patch in.

VF1
  • 1,594
  • 2
  • 11
  • 31
  • AFAIK, both `.o` files will contain the code for `std::vector` (or the parts of it that are required), and the linker will figure out that both files contain code for the same methods (probably by name). It will then only include one instance of those methods in the linked file, and make all references use that. Caution, this is just off the top of my head and I don't think I explicitly read anywhere that it works like this (that's why it's not an answer). I'd be surprised if it didn't, though. – Medo42 Jan 27 '14 at 22:49
  • @Medo42 So then the linker has to go through _every_ `*.o` file that uses its own template specification and then edit every single reference to that class (calls to its methods, etc...)? That's a lot of instructions to keep track of for more linking... – VF1 Jan 27 '14 at 22:51
  • @harmic Thanks for the link. As AProgrammer mentions in his answer to the linked question, both of the solutions I suggested (greedy and iterated) are apparently used. However, his answer did not address my more specific concerns, like how the instructions are changed on the machine code level. – VF1 Jan 27 '14 at 22:56
  • @VF1 I don't see anything in the process that would make it terribly inefficient. You need to keep track of all the symbols anyway, and you don't need to remember all the duplicates. If you link the files one at a time, you can discard all information about duplicates in a `.o` file once you're done with it, if you need to remember it at all - it might be enough to just ignore extra instances with the same name. Again, not sure how the process works in detail. – Medo42 Jan 27 '14 at 22:57
  • @VF1 It won't have to keep track of duplicates as it would remove them in each step of the linking process. Basically, think of it like a set of types ... If I pull in a new set of types (that has both types I already have, and types I do not yet have), only the new types get added. – Zac Howland Jan 27 '14 at 23:00

2 Answers2

3

This is a slightly more complicated question than what most people will realize.

In the general and simplest case, the template definition is present in the header, and it behaves as inline functions. The compiler will generate the code for those functions needed in each translation unit that needs them. Then the linker will resolve the duplicate symbols by removing all but one. Since the standard requires that they are exactly equivalent, the linker can pick any one from the list.

If the template need only work with a couple of types, you can move the definition to a single translation unit and explicitly instantiate the template for those types there. This would behave as a non-inline function in the general case.

Somewhere in between, if the template can be instantiated with any type but it is commonly instantiated with a few of them, the implementor of the template can use a mixed approach, where the template and the members are defined in the header, but explicit instantiations are also declared. Then in a single translation unit, those explicit instantiations can be done.

This approach can be used, for example, to minimize compile and link time when using std::string (which is really std::basic_string<char, std::char_traits<char>, std::allocator<char> >). The compiler can, in a single translation unit provide all of the functions for the common instantiation, but still provide the definition of the template functions in the header so that if you opt to use a different instantiation of the basic_string template it will still work for you. In all translation units that only use std::string, the compiler knows not to generate the code for all members as those will be available to the linker.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • So where exactly are the explicit specifications, such as `std::string`, if not in any of the compiled files? You mention that the linker has them "available". – VF1 Jan 27 '14 at 23:17
  • Another question: wouldn't explicitly specified templates have to somehow be available during the compilation time as well? How would you calculate `sizeof(std::string)` otherwise? – VF1 Jan 28 '14 at 00:35
  • @VF1: They will be in one translation unit, but often you won't compile them, but rather link them from a library. Regarding the second comment, there are two things to be defined here, the class template and the members. The class template must be defined in the header (as with any other type), the members need not be available to the compiler. Once the declarations are present, the compiler can just *refer* to them. – David Rodríguez - dribeas Jan 28 '14 at 05:05
  • How can the compiler just refer to them? If I have a class which contains a `std::string` and then, say, an `int`, then the compiler will need to know how large the string is in order to access the integer member (for instance). Similarly, it needs to know how large the object is whenever I allocate one on the stack. Being able to refer to the declared methods, classes, etc. wouldn't be enough. – VF1 Jan 28 '14 at 06:02
  • Also, linking the explicit version from a library makes sense if the explicit template is defined by default like `std::string`, but what if one of my source code files explicitly defines a template? How does the compiler know which one to instantiate the code in? – VF1 Jan 28 '14 at 06:05
  • @VF1: It seems I am not making myself clear. The *class* (template) needs to be defined, the member [functions, static member variables] need not be defined. That can be moved to a single translation unit. To be able to hold a `std::string` you need the *footprint* of the string object. Consider that all member functions were regular functions, the declaration must be present, the definition can be in a single TU. Static member variables act like extern variables, the declaration suffices. Non-static member variables affect the layout and need to be seen. – David Rodríguez - dribeas Jan 28 '14 at 15:13
  • @VF1: For explicit/manual instantiation the compiler does not *know* what arguments it must instantiate the template with, **you** must tell it. In the case of `std::string` the implementor of the library would have to do that. For your own particular templates, you would have to do it, or default to the common simpler approach of just providing the whole template in the header and let the compiler implicitly instantiate the needed members on demand. – David Rodríguez - dribeas Jan 28 '14 at 15:16
1

The compiler generates code for each instantiation of the template and makes sure that there are no name clashes. It is not like ordinary functions, where you get linker errors if a .cpp file is used in two compilation units.

It is possible to save some compilation time by explicitly instantiating the template in some compilation unit and use that template elsewhere, but this needs quite a bit of manual housekeeping (adding explicit instantiations for each new type that is used in the project). You can also save some compilation time by avoiding some unnecessary conversions by using the keyword explicit on templated constructors.

Jens Munk
  • 4,627
  • 1
  • 25
  • 40
  • I'm afraid I don't understand what you mean with your last sentence. Could you please explain what's so special about `explicit` with templates? – VF1 Jan 27 '14 at 23:05
  • @VF1: *explicit instantiation* or manual instantiations is a mechanism in the language. It is not related to any `explicit` keyword, it is just explicit as opposite of implicitly instantiated by the compiler when needed. – David Rodríguez - dribeas Jan 27 '14 at 23:11
  • You can use the keyword explicit to avoid unnecessary conversions and thereby save compile time. A simple example for a constructor can be found here, http://blog.emptycrate.com/node/367 – Jens Munk Jan 27 '14 at 23:15
  • @DavidRodríguez-dribeas That's what I thought too, but the word "keyword" threw me off. – VF1 Jan 27 '14 at 23:18
  • You also save compilation time by explicitly instantiating your templates like David is referring to, but that is another story and not worth the extra development time. I can see why you got confused, sorry about the wording in the first post – Jens Munk Jan 27 '14 at 23:21
  • You should at least mention the context in which the `explicit` keyword "helps", because currently your answer is quite confusing. – juanchopanza Jan 27 '14 at 23:26
  • Now, the answer is more accurate – Jens Munk Jan 27 '14 at 23:29