On Sat, 10 May 2008 21:14:06 +0200, Warp <war### [at] tagpovrayorg> wrote:
> Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
>> Some linkers can recognise that the generated code is identical, and  
>> merge all the copies.
>
>   Not "some". All of them. They have to.
>
>   That's because, AFAIK, as per the C++ standard, you have to be able to,
> for example, create a function pointer to a given template function, and
> if two pointers initialized in different compilation units point to the
> same function, they have to compare equal. Another requisite is that if
> there are static variables inside the function, they must all use the  
> same static variable.

This is true for multiple definitions of the same object, but Darren was  
talking about instantiations on multiple distinct types.


-- 
FE

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Warp wrote:
>>> Darren New <dne### [at] sanrrcom> wrote:
>>>> For example, you have to parse and compile the 
>>>> templates each time from source
>>>   A compiler which supports export templates could conceivably have
>>> precompiled templates for certain (although obviously not all) types,
>>> such as for example for all basic types and STL classes. Thus it could
>>> avoid having to compile them each time.
> 
>> Yes. If you restrict templates to doing what generics do, you don't have 
>> to compile them each time. But that's a restriction on templates.
> 
>   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 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. 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, and (b) you can't tell if the template 
source code changed since you compiled those object files, because the 
object files don't carry around information about the template source code.

That's basically how almost every other language implements generics.

> 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 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.

>   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. 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.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?

>> Right. Generics do the same thing.
> 
>   Except that they don't work with basic types, at least not in Java,
> so they only solve part of the problem. :P

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.

>>> Thus any argument that
>>> templates cause memory bloat is usually false. (Yes, there may be a few
>>> situations where templated code causes more memory usage, but normally
>>> it's the opposite.)
> 
>> I think they likely cause code file bloat.
> 
>   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.

Some languages have restricted enough generics that you only need one 
copy of the object file regardless of what you instantiate it on. Java 
is like this, which is why it doesn't work with non-Object types - 
basically, you instantiate it once for Object and the compiler just 
checks you use it right at compile time.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Fredrik Eriksson wrote:
> This is true for multiple definitions of the same object, but Darren was 
> talking about instantiations on multiple distinct types.

More precisely, I was speaking of the differences between generics and 
templates, and why it's not unreasonable to say "we don't like 
templates, we do like generics."  Regardless of implementation 
technology and optimizations...

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

On Sat, 10 May 2008 22:05:53 +0200, Darren New <dne### [at] sanrrcom> wrote:
> OK. So the linker is doing duplicate-code removal. 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?

It must be the same, or the program is ill-formed.


> 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?

If you change T.chh, then A.cpp - and any other source file that includes  
T.chh - must be recompiled.


-- 
FE

Post a reply to this message

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

Fredrik Eriksson wrote:
> On Sat, 10 May 2008 22:05:53 +0200, Darren New <dne### [at] sanrrcom> wrote:
>> OK. So the linker is doing duplicate-code removal. 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?
> 
> It must be the same, or the program is ill-formed.

Um, OK. But that's unenforcable, right?  At least in C++?

>> 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?
> 
> If you change T.chh, then A.cpp - and any other source file that 
> includes T.chh - must be recompiled.

And this is why Java doesn't do templates. You may not have the source 
code for A.cpp.

It seems there are two kinds of languages out there: ones where the 
program is monolithic and if you don't have all the sources, you can't 
really use the object code effectively, and ones that are particularly 
designed to avoid the problems that the first group encounter. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> > If you change T.chh, then A.cpp - and any other source file that 
> > includes T.chh - must be recompiled.

> And this is why Java doesn't do templates. You may not have the source 
> code for A.cpp.

  You mean that if the public interface of a class T changes, nevertheless
the class A which uses T doesn't need to be recompiled? How does it manage
to do that?

  After all, the T.hh header might just contain the public interface for
the template code. Its implementation may be in its own compilation unit
(if the compiler supports fully the C++ standard).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> 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.

Because if the templates calculate something at compile-time based on a 
parameter you pass in (like the number of elements in an array), then 
you can't precompile it.

>>>   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.)

I'm saying that the things templates do that generics don't are the 
things that make it difficult to precompile 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.

Sure. Generics are (usually) restricted in a way that allows you to 
distribute the executable (or .o file) without distributing the source 
and others can still use it.

>   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.

Funky. OK.  That's getting closer to being what people generally mean by 
"generics". :-)

Put it this way: If you can't compile it and distribute a .o file 
*before* you know what type you're instantiating it with, it's probably 
not what people mean by the word "generic".

>>>   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).

Isn't that duplicate code removal by the linker? Maybe we're in 
agreement and I'm just not understanding the subtleties or something. :-)

>   I assume it would be possible for the functions to actually be different
> in content (which might happen if you have broken dependencies),

Yeah. That's the sort of "bondage and discipline" that Ada enforces to 
keep that mistake from surfacing. If you compile a generic in Ada, you 
can't change the header file and then link against the old .o file.

[snip of lots of explanation]
Thanks for clarifying that for me.


>> 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.

It would seem that way, especially if you're generating different code 
for every type even if you don't have to. Or you could even have the 
linker detect (say) that the code generated for MyTemplate<int*> and 
MyTemplate<long*> both come out the same and use the same object code 
for both.

>> 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. 

Got it. That's what I thought.

>   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.)

That's essentially right, yes.  Generics and delegation are actually 
unrelated, and you probably can't even reasonably have both in the same 
language.  Generics are a way of having one function/class/etc work with 
variables of multiple types, which implies you have static typing, i.e., 
that your variables have types to start with. Delegation is an 
alternative to inheritance, where you "inherit" from object instances 
instead of statically from classes. `In other words, instead of having 
class A say "I'm just like class B, except for the differences I declare 
here," you have *instance* A say "I'm just like *instance* B, except for 
what I have dynamically assigned into my object." It's also called 
"prototype inheritance" sometimes.  You can do delegation "manually" in 
statically-typed languages (or get compiler support for it), and it's 
still called "delegation", but it's only "prototype inheritance" if 
every object works that way.


>   Delegation sounds like an alternative to templates/generics.

It's more an alternative to inheritance. You don't need generics if you 
don't have static typing (i.e., if your variables are untyped, 
regardless of whether operations on values are type-checked).

Here's my understanding of the terms as they're used in a more general 
sense:

Macro - transforms almost arbitrary pieces of text into other pieces of 
text at compile time.

Macro[2] - (Lisp sense, Erlang "parse transform" sense) - transforms 
arbitrary subtrees of the parse tree into other arbitrary subtrees of 
the parse tree. (I.e., if it didn't parse before you applied the macro, 
it won't parse after, either. Erlang has both types, fwiw.)

Template - A macro that is restricted to generating a particular node of 
a parse tree, given other particular nodes of a parse tree. I.e., a C++ 
template can only generate functions or classes (IIUC) and can only take 
types or integers as parameters. These restrictions let the compiler do 
things like duplicate code removal. But it's still essentially a 
compile-time source transformation.

Generics - A type of object that is parameterized at compile-time. 
Usually only takes types as arguments. Invariably can be (often, must 
be) compiled before being instantiated, and can be instantiated with 
types created after the generic is compiled.

"is-a" inheritance  - (I don't remember what the people who play with 
different inheritance methods call this, beyond "class-based 
inheritance".) The usual class/superclass inheritance.

"prototype inheritance" - Object instances inherit from other object 
instances. There usually isn't the idea of a "type" as such in the 
language, other than as defined by the behavior of different objects. 
Naturally, you often have lots of objects delegating to some other 
object that has only functions in it, at which point it behaves a lot 
like "is-a" inheritance.

"delegation" - Manual or automated support for dispatching unknown 
method invocations to another object when the original target object 
doesn't define the method.

"aspect-oriented programming" - Took me a while to figure this one out. 
It lets you say things like "every method in class B should call "debug" 
before it starts and "end_debug" before it exits", and in another place 
say "every method of A or subclasses should call "transaction_begin" at 
the start and "transaction_end" at the end, and if B is a subclass of A, 
then B gets both new behaviors, without having to muck with B or callers 
of B. Sort of like how some languages let you use "super" to say "first 
do this, then invoke my superclass's behavior for this method, then do 
that", only in a more general way. Same sorts of advantages you get with 
inheritance/dynamic dispatch not making you put case statements all over.

>>>   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.

So, like the same object file showing up in separate libraries in C, it 
just links in the first one because it already satisfied the 
dependencies. OK. Now that I realize templates really only build code 
that you dont *have* to inline, it makes sense. (Contrasted with C-style 
macros, which can build expressions that would make no sense on their own.)

It's all coming together... :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>>> If you change T.chh, then A.cpp - and any other source file that 
>>> includes T.chh - must be recompiled.
> 
>> And this is why Java doesn't do templates. You may not have the source 
>> code for A.cpp.
> 
>   You mean that if the public interface of a class T changes, nevertheless
> the class A which uses T doesn't need to be recompiled? How does it manage
> to do that?

Dynamic loading. :-)

Seriously, tho, I wasn't necessarily talking about the public interface. 
I was talking about the implementation of the functions. In Java, the 
code for the generic isn't duplicated for different types, and it gets 
linked in at runtime. Hence, the whole question of "what if it changes" 
doesn't matter - you compile against the types, not against the bodies 
of the code. If you change the public interface to the point where the 
old code won't work, then when you try to instantiate the generic, it'll 
tell you that code couldn't be dynamically loaded. I.e., it falls back 
to being a run-time error, just like if you try to load a .so / .dll and 
that isn't present on the disk. (Which I guess is in some ways worse 
than what you get with C++ and static linking. :-)

>   After all, the T.hh header might just contain the public interface for
> the template code. Its implementation may be in its own compilation unit
> (if the compiler supports fully the C++ standard).

The whole "export template" bit I don't understand. I have to believe 
that either there are restrictions on what a template can do and still 
be able to be an export template, or there are bits in the object file 
which are essentially getting recompiled at compile-time.

How does it work if the template class declares in one of the functions 
an array of type T (where T is one of the generic parameters), and then 
indexes that with []?  If T overrides [], it has to call different 
things for each T, and if T doesn't override [], it has to use different 
multipliers based on the size of each T object, yes? If you're not doing 
that, then you have generics instead of templates, where the same code 
is getting used and when you "instantiate" it, it fills in blanks like 
"pointer to function that does indexing, size of one element of the 
array", etc?

I've even seen purposely-obtuse C++ template stuff that either declares 
a type or a function (both with the same name) depending on the size of 
the generic type passed in or some such, which would seem to be 
something really difficult to put into object code that doesn't have to 
get recompiled when you instantiate it.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

On Sun, 11 May 2008 19:32:15 +0200, Darren New <dne### [at] sanrrcom> wrote:
>>> OK. So the linker is doing duplicate-code removal. 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?
>>  It must be the same, or the program is ill-formed.
>
> Um, OK. But that's unenforcable, right?  At least in C++?

Compilers/linkers are free to enforce it, but I think most implementors  
see it as not being worth the effort.



> It seems there are two kinds of languages out there: ones where the  
> program is monolithic and if you don't have all the sources, you can't  
> really use the object code effectively, and ones that are particularly  
> designed to avoid the problems that the first group encounter. :-)

Support for modules (similar to how Java does it) in C++ is planned for  
the future. Last I heard it will not be included in the upcoming standard,  
but will most likely be in the next Technical Report.


-- 
FE

Post a reply to this message