Darren New <dne### [at] sanrrcom> wrote:
> >   At least Java generics do not support basic types, so I don't really
> > understand what you are talking about.

> I'm saying you could pre-compile many templates if the templates only 
> are capable of doing what generics do.

  I don't see why that would be so.

> >   I suppose that no compiler so far uses this optimization, but I can
> > perfectly imagine it being absolutely possible: When a template class or
> > function is instantiated for a certain type, the compiler could compile
> > it into some type of object file. Next time that template is used with
> > the same type (be it in the same compilation process, by another compilation
> > unit, or in a future one) it can simply use that object file instead of
> > recompiling the template code. 

> Yes. Bingo. That's a generic.

  I don't see why. (Or, more precisely, I don't see why this would limit
anything in templates.)

> You can't do that with templates because 
> you (a) can't tell if the template will generate the same code with 
> different classes/parameters

  I was just saying that the compiler could generate reusable object files
from used types (so that when those types are used again with those templates,
the template code doesn't need to be compiled again). Granted, you still
can't make binary-only distributions of libraries, but at least you cut
down compilation times if the same types are used a lot with a given
template.

> > The mechanism to do this could be similar
> > and related to export templates (or if technical reasons mandate it, it
> > could only work with export templates).

> I don't know what an "export template" is, so you may be right there.

  In C++ an export template is a template mechanism where the implementation
of a template can be located in its own compilation unit (meaning that the
implementation of the template code is in its own .cc file and the template
code gets actually inserted in an object file). In other words, the
implementation of a template function doesn't need to be in the header file
where the template function is declared. This makes header files simpler,
object files smaller and compilation of complicated template code faster.

  What this means in practice is that the linker will re-call the compiler
for any export template which is used in the code in order to get the
actual template instance. OTOH, the template is instantiated only once
instead of being instantiated for every usage.

  While export templates are defined in the C++98 standard, sadly not
many compilers support them yet (gcc fairly recently introduced experimental
support).

> >> In any case, what *I* meant was that you get a new blob of code compiled 
> >> every time you instantiate a template. Not for each different type, but 
> >> even for the same types in different compilation units. Yes? Or am I 
> >> confused about that?
> > 
> >   Currently yes, but as I said, it's perfectly conceivable that this
> > could be optimized by compilers.

> Sounds like it would be difficult, given that there's no relationship 
> the compiler can rely on between template sources and template object code.

  As I said, the export template mechanism I described above might be
usable for this kind of optimization.

> >   The linker always merges all template instantiations of a given type
> > into one (this is required by the C++ standard, AFAIK). In other words,
> > the final executable will have only one instance of those functions.
> > That's not the problem.

> OK. So the linker is doing duplicate-code removal.

  No. The compiler marks the function type names with the 'inline' tag,
which means that when the linker sees that type name in more than one
object file, it only uses one of them (instead of giving you a linker
error about duplicate function type names).

  In other words, basically, when the compiler name-mangles the function
it just created from the template, it puts a mark in it which tells the
linker "if you see this same function name in another object file, just
use one of them, ignore the rest".

  I assume it would be possible for the functions to actually be different
in content (which might happen if you have broken dependencies), in which
case you get undefined behavior (I suppose in practice the linker will
choose one of the functions, probably the first one it encounters, and
ignores the rest).

  Note that any inline function (if it's not actually inlined by the
compiler) gets the same treatment, not just template functions: Even if
the inline function appears in more than one object file, the linker
will use just one of them and ignore the rest.

  (Export templates are not "inline", but that doesn't matter because
their implementation is in one object file anyways.)

> It also would seem to 
> assume that all your object code is compiled with the same template 
> source code? Or does it actually look at the object code to make sure 
> it's the same?

  I actually don't know. I suppose that a smart linker could actually
double-check that the functions in the different object files actually
are identical and give an error if they aren't. I have never tested
what eg. the gnu linker does. It would sound rather trivial to do.

> I.e., if I compile A.cpp that includes T.chh to instantiate 
> xyz:vector<long>, and then I edit T.chh and then compile B.cpp that 
> instantiates xyz:vector<long> but that now generated different code, 
> does the linker carry around both versions of the object code?

  The object file created from A.cpp and the one created from B.cpp
both will claim to contain the same function, but their machine code
will be different. As I said, I have never tested if linkers actually
test if they are, in fact, identical.

> Generics in Java aren't even really generics, since they get 
> type-erased. But yes, I'm not talking about "generics as implemented in 
> Java without actually changing any object code." I'm talking about when 
> people speak of generics in a language that actually supports generics, 
> like Eiffel or Ada, for example.

  Btw, what is the basic difference between generics (as in Eiffel&co)
and delegation?

  If I'm not completely mistaken, delegation is like having all functions
virtual, but without having to declare them in the base class. In other
words, if you have a reference-to-Base, but that reference is actually
pointing to an object of type Derived, and then you call a function foo()
through that reference, and there is no foo() in Base, but there is one
in Derived, it gets called ok. The delegation system checks at runtime
what is the actual object behind that reference, and if it has a function
called foo(), and calls it if that's so. (If I'm not mistaken, this is
how inheritance works in Objective-C.)

  Delegation sounds like an alternative to templates/generics.

> >   The amount of code "bloat" caused by templates is usually

> I wasn't aware the linker removed duplicate object code. That's the 
> bloat I was speaking of.

  It's not so much that the linker "removes" code per se, it's more that
it just uses one instance of a given function and ignores the rest. (Well,
I assume that's how linkers do it in practice.) After all, the linker is
building an executable from a bunch of object files, deciding what to
take from each object file. In the case of inline/template functions it
just takes one duplicate and leaves the rest.

-- 
                                                          - Warp

Post a reply to this message