Yes, I know it would be better to ask this in a Java forum, but I'm just
too lazy to dig one up (as well as not too eager to show my ignorance in
a random forum ;) ). Given the amount of programmers here, I'm sure at
least someone knows the answer to this.

  In C++, if you have a very complicated template type, such as for example:

std::map<std::string, std::vector<std::vector<std::string> > >

it would be quite laborious to have to write that type every single time
when you need it. The solution to this is to create a type alias:

typedef std::map<std::string, std::vector<std::vector<std::string> > >
    TheMap;

  Now it's much shorter to use that type. For example:

TheMap m;
for(TheMap::iterator iter = m.begin(); iter != m.end(); ++iter)
    ...

  Java supports generics, which are instantiated with a syntax very similar
to this. However, Java does not support type aliases.

  Is there a way in Java to shorten those long type names?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Is there a way in Java to shorten those long type names?
> 

Not that I know of. In fact, it's even more annoying in that you have to
type the whole type twice when creating an object.

Map<String, ArrayList<ArrayList<String>>> theMap =
   new HashMap<String, ArrayList<ArrayList<String>>>();
ArrayList<ArrayList<String>> someList = new ArrayList<ArrayList<String>>();

Of course, you could also use interfaces for the type and generic
parameters, only using a real class for the actual object you're creating,
making it a bit shorter:

Map<String, List<List<String>>> theMap =
   new HashMap<String, List<List<String>>>();
List<List<String>> someList = new ArrayList<List<String>>();

//and let's continue the example
List<String> deeperList = new ArrayList<String>();
List<String> otherDeeperList = new ArrayList<String>();
deeperList.add("one");
deeperList.add("two");
otherDeeperList.add("three");
otherDeeperList.add("four");
someList.add(deeperList);
someList.add(otherDeeperList);
theMap.put("foo", someList);

It's interesting to note that in scripting languages, all that could be a
one-liner. In Javascript:
var theMap = {"foo": [["one", "two"], ["three", "four"]]};

And even more interesting to note that C++0x will allow an initializer
syntax almost as short as that :)

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailcom> wrote:
> Warp wrote:
> >   Is there a way in Java to shorten those long type names?
> > 

> Not that I know of.

  I was thinking if it's not possible even through inheritance.
Something like (iirc Java syntax):

class TheMap extends Map<String, ArrayList<ArrayList<String>>>
{};

  Then just use TheMap? (Of course from a purely OO point of view this
could be seen as a misuse of inheritance, but...)

> In fact, it's even more annoying in that you have to
> type the whole type twice when creating an object.

  I will never understand why they decided to drop 'typedef' when they
designed Java in the first place. It's so handy in C++.

> It's interesting to note that in scripting languages, all that could be a
> one-liner. In Javascript:
> var theMap = {"foo": [["one", "two"], ["three", "four"]]};

  Yeah, but that's only possible in languages with weak typing (I think
that's the term?) In other words, in languages where you don't have to
specify types explicitly, as they are inferred from the values.

> And even more interesting to note that C++0x will allow an initializer
> syntax almost as short as that :)

  I also wonder if the new 'auto' feature in C++0x will help alleviating
this nuisance a bit. At least it will allow writing things like:

auto p = std::make_pair(value1, value2);

  You don't have to even care what is the type returned by std::make_pair
or the types of those values, which is cool.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Yes, I know it would be better to ask this in a Java forum, but I'm just
> too lazy to dig one up (as well as not too eager to show my ignorance in
> a random forum ;) ). Given the amount of programmers here, I'm sure at
> least someone knows the answer to this.

[insert ironic comment here]

>   Java supports generics.

...OK, I just learned something.

>   Is there a way in Java to shorten those long type names?

Given the statement above, is there any point in my answering this? ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:

>   I will never understand why they decided to drop 'typedef' when they
> designed Java in the first place. It's so handy in C++.

Well, in Java everything is a class. So it's not 100% obvious where 
you'd *put* a typedef. (I suppose it could be something that's local to 
a class or something...)

>> It's interesting to note that in scripting languages, all that could be a
>> one-liner. In Javascript:
>> var theMap = {"foo": [["one", "two"], ["three", "four"]]};
> 
>   Yeah, but that's only possible in languages with weak typing (I think
> that's the term?) In other words, in languages where you don't have to
> specify types explicitly, as they are inferred from the values.

Two cases here:

- JavaScript is dynamically typed. Types become known only at runtime. 
Types are checked only at runtime. Many scripting languages follow this 
model. (Smalltalk immediately springs to mind here.)

- Haskell is statically typed, but types are [usually] inferred 
automatically. Types are checked at compile-time only. Types are not 
known at runtime at all. [With the exception of types belonging to a 
class of some kind.]



Obviously nobody cares, but:

   theMap = fromList [("foo", [["one", "two"], ["three", "four"]])]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:

> >   I will never understand why they decided to drop 'typedef' when they
> > designed Java in the first place. It's so handy in C++.

> Well, in Java everything is a class. So it's not 100% obvious where 
> you'd *put* a typedef.

  You'd put it in the exact same place as you'd put a class.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> >   Java supports generics.

> ...OK, I just learned something.

  Java generics are a bit ironical because before they existed the
common consensus among Java people was that C++ templates are an
abomination (in the same category as, for example, multiple inheritance,
if not even worse).

  Of course this was before all the generic programming craze, and when
it hit, the Java people had to swallow their pride and introduce some
crippled template mechanism into Java. Naturally since templates were
always considered an abomination they couldn't call them that, so they
tried to save even a bit of their pride by renaming them to "generics".
(I suppose "generics" rides more on the whole "generic programming"
thing.)

  Of course Java generics are a bit crippled because they don't support
basic types (such as int). Thus they solve only part of the problem which
Java had before.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>>>   Java supports generics.
> 
>> ...OK, I just learned something.
> 
>   Java generics are a bit ironical because before they existed the
> common consensus among Java people was that C++ templates are an
> abomination (in the same category as, for example, multiple inheritance,
> if not even worse).
> 
>   Of course this was before all the generic programming craze, and when
> it hit, the Java people had to swallow their pride and introduce some
> crippled template mechanism into Java. Naturally since templates were
> always considered an abomination they couldn't call them that, so they
> tried to save even a bit of their pride by renaming them to "generics".
> (I suppose "generics" rides more on the whole "generic programming"
> thing.)
> 
>   Of course Java generics are a bit crippled because they don't support
> basic types (such as int). Thus they solve only part of the problem which
> Java had before.

Well, actually Eiffel calls it generics too. I don't know when Eiffel 
was designed, but it's had generics from day 1, and that has always been 
its name.

I don't actually know how C++ templates work, but my take on it is this:

- Generics is the ability of a programming language to implement classes 
that are parameterised over another class.

- C++ implement this ability using templates.

- Templates can do other things besides implementing generics.

So to say that Java's generics is a crippled copy of C++'s template 
mechanism isn't entirely true.

OTOH, I haven't seen Java generics or C++ templates "for real", so maybe 
I'm mistaken.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> - Templates can do other things besides implementing generics.

  I think it suffices to say that with C++ templates you can, for example,
calculate at *compilation time* whether a certain number is prime or not.

  Moreover, you can even do that without using any integer literals or
any basic type, such as 'int'. (Although doing it like that is really
not the most efficient way.)

-- 
                                                          - Warp

Post a reply to this message

>> - Templates can do other things besides implementing generics.
> 
>   I think it suffices to say that with C++ templates you can, for example,
> calculate at *compilation time* whether a certain number is prime or not.

So... it's Turing-complete?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:
>   Yeah, but that's only possible in languages with weak typing (I think
> that's the term?) 

"Dynamic typing" is the term you're looking for - expressions have 
types, but not variables.
"Static typing" being the alternative, where variables have types.

"Weak typing" is when type operations aren't enforced, like in C. 
"Strong typing" is when type operations are enforced, like Java.

You can have strong typing that's also dynamic typing, like Smalltalk or 
Lisp or Erlang, or static typing that's weak like in C, or static typing 
that's strong like (say) Haskell (as I understand it), or dynamic typing 
that's weak (like Forth or assembler).

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

Orchid XP v8 wrote:
>>   Java supports generics.
> ....OK, I just learned something.

Are they actually supported as new types? Or is it just syntactic 
shorthand? I wouldn't think you could really have generics if you didn't 
change the .class file format, which I think Sun's trying to avoid?

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

Orchid XP v8 wrote:
> So... it's Turing-complete?

Yep.  I saw a turing machine emulator written as templates, with a 
series of error messages from the compiler tracing the path through the 
state changes.

In any case, generics are a subset of templates. It's entirely possible 
to think that generics are a good idea and that templates are a bad way 
to implement them. For example, you have to parse and compile the 
templates each time from source, and you get a new blob of code for each 
type you instantiate a template with. Both of these are a bad idea when 
you're trying to make a system where you can distribute object code 
without source for generics, or you want to instantiate a generic at 
runtime with some other class you just loaded.

Now, "crippled" is what I'd call the baroque C++ syntax. I mean, really, 
folks, can't we accept that languages that aren't C don't need to avoid 
C special characters in new syntax? :-) What's with this "::" for 
namespaces in Tcl and <<>> for generics in Java? Ugly, guys, uUUUuugly!

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

> Orchid XP v8 wrote:
>>>   Java supports generics.
>> ....OK, I just learned something.
> 
> Are they actually supported as new types? Or is it just syntactic
> shorthand? I wouldn't think you could really have generics if you didn't
> change the .class file format, which I think Sun's trying to avoid?
> 

http://java.sun.com/docs/books/tutorial/java/generics/erasure.html
http://java.sun.com/docs/books/tutorial/extra/generics/legacy.html
http://java.sun.com/docs/books/tutorial/extra/generics/convert.html

Basically, it looks like anything related to generics is removed from the
compiled code.

Post a reply to this message

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.

> and you get a new blob of code for each 
> type you instantiate a template with.

  If you are using the same code with two different types you are obviously
going to get two different pieces of code, no matter how you do it.
Templates just make it easier to avoid code repetition. (In other words,
if you want, for example, a vector of ints and a vector of doubles, you
don't need to write the vector code twice.)

  Templated data containers in C++ usually produce more memory-efficient
code than equivalent data containers using the pointer-to-base-Object
mechanism, which usually wastes a lot of memory. 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.)

> Now, "crippled" is what I'd call the baroque C++ syntax.

  Syntax doesn't really matter all that much. It's how you use it.

-- 
                                                          - Warp

Post a reply to this message

>> So... it's Turing-complete?
> 
> Yep.

Right. Well, the good thing about Turing-complete languages is that they 
can do everything. The bad part is... they can do everything. SQL is so 
damn efficient precisely *because* there are things it can't do.

Java's generics [if they anything like any other language] are nowhere 
near Turing-complete, which makes them much easier to handle. [And 
harder to misuse.]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

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.

>> and you get a new blob of code for each 
>> type you instantiate a template with.
> 
>   If you are using the same code with two different types you are obviously
> going to get two different pieces of code, no matter how you do it.

Not in every language, no.  Depending on what you do with the types, 
yes. That, for example, *is* one difference between generics and 
templates. Obviously Java "generics" (such as they are) don't have this 
restriction, because by the time you get to object code, all the actual 
type information is gone.

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?  If I have std:vector<MyType> having functions 
called in one module, then I compile another module with 
std:vector<MyType>, does the linker see that it's the same code and 
function on the same type and only include one copy of the object code 
in the linked result?

> Templates just make it easier to avoid code repetition. (In other words,
> if you want, for example, a vector of ints and a vector of doubles, you
> don't need to write the vector code twice.)

Right. Generics do the same thing. They're just more restricted than 
what templates give you.

>   Templated data containers in C++ usually produce more memory-efficient
> code than equivalent data containers using the pointer-to-base-Object
> mechanism, which usually wastes a lot of memory. 

Unless everything's already a pointer-to-base-Object, as you already 
decry. ;-)

> 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. If you use the same template 
and instantiate it on 10 different types of pointers, aren't you going 
to get ten different copies of object code?

>> Now, "crippled" is what I'd call the baroque C++ syntax.
>   Syntax doesn't really matter all that much. It's how you use it.

True. It's a pretty minor thing, once you get used to it. I just dislike 
people taking the syntax into languages that don't need it. Right up 
there with people who think a leading zero means octal is a good idea on 
values rather than constants.

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

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

>  If I have std:vector<MyType> having functions 
> called in one module, then I compile another module with 
> std:vector<MyType>, does the linker see that it's the same code and 
> function on the same type and only include one copy of the object code 
> in the linked result?

  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.
  (The only "problem" with template code is the increased compilation
time and object file sizes.)

> > Templates just make it easier to avoid code repetition. (In other words,
> > if you want, for example, a vector of ints and a vector of doubles, you
> > don't need to write the vector code twice.)

> 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

> > 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 much smaller
than the extra amount of RAM required if templates were avoided. Usually
template functions are relatively small, like some hundreds of bytes at
most, while the data containers they are instantiating handle even
megabytes of memory at a time. With C++ templates the optimization is
in the right place: In the memory usage of the data containers, not the
machine code in the functions of that data container.

-- 
                                                          - Warp

Post a reply to this message

On Sat, 10 May 2008 19:44:53 +0200, Darren New <dne### [at] sanrrcom> wrote:
> 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?  If I have std:vector<MyType> having functions  
> called in one module, then I compile another module with  
> std:vector<MyType>, does the linker see that it's the same code and  
> function on the same type and only include one copy of the object code  
> in the linked result?

Some compilers delay code generation of some templates until link time.  
Even in the absence of delayed code generation, the linker merges  
duplicates.



>> 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. If you use the same template  
> and instantiate it on 10 different types of pointers, aren't you going  
> to get ten different copies of object code?

Some linkers can recognise that the generated code is identical, and merge  
all the copies.


-- 
FE

Post a reply to this message

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.

-- 
                                                          - Warp

Post a reply to this message

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

On Sun, 11 May 2008 20:35:50 +0200, Darren New <dne### [at] sanrrcom> wrote:
> 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.

Read this paper to learn a little about what 'export' means, and why many  
consider it to a bad idea:
http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1426.pdf



-- 
FE

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> 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.

  AFAIK there are no restrictions on what an export template function
can contain.

  The basic implementation of export templates, from the point of view
of the compiler, is that the template *source* code gets written to the
object file (either as raw source code or some kind of pre-parsed code
or whatever; I don't know how eg. gcc does it in practice). When the
linker sees that it needs a specific instance for a certain template
function, it calls the compiler and tells it "I need an instance of
this template function with these types", the compiler compiles the
function for those types, and then the linker uses the generated code.

  As you might imagine this is far from trivial to implement, which is
the reason why so few compilers support this.

  In theory you could distribute template code as "precompiled" object
files, without the original source. However, I assume that with most
implementations of export templates, creating a decompiler for those
object files is probably fairly trivial (because, after all, the object
file has to have the original source code in one form or another inside
it for the whole export template mechanism to be possible).

  Btw, there's an additional advantage in export templates besides the
smaller simpler header files and object files, and it's one which cannot
be used with compilers which do not support export templates and it can
have very practical uses: Export template code can use functions and
types which are local to that compilation unit. This can be used to
increase modularity (by hiding implementation details).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> 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.

> object files is probably fairly trivial (because, after all, the object
> file has to have the original source code in one form or another inside
> it for the whole export template mechanism to be possible).

OK, that would be my second statement, then. The template is actually 
getting recompiled down to object code each time you instantiate it, 
even if it's an "export" template.

In a language like Ada (which has generics but not templates), you 
compile the generic down to object code, and when you instantiate it, 
you don't need the source for the implementations. I believe it can work 
by basically, at instantiation time, building a descriptor not too 
different from a vtable. If the only difference is which overloaded 
functions get used, the object code will expect a table of pointers to 
be created for it to invoke those functions. If it expects a different 
size, then the object code is (possibly) duplicated and the size filled 
in (just as you would fix up external references at link time), or the 
code is slightly less efficient and takes as one parameter the size it 
needs to work with.

In Java, of course, it compiles down to the same code as you would have 
without generics, and you compile it once and ship the bytecodes. The 
compiler basically just does error checking if the declaration is in 
scope and casts the result of operations at runtime if so needed.

-- 
   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:
> OK, that would be my second statement, then. The template is actually 
> getting recompiled down to object code each time you instantiate it, 
> even if it's an "export" template.

  But it's compiled only once even if the same template function is used
with a given type at several places in the program. (Without the export
template mechanism the function would be compiled every time it's used.)

  And, as I said, I can imagine that compilers could implement optimizations
where they cache compiled export templates. IOW, if you compile your project
for the first time, the template code gets compiled, but if you recompile
the project a second time, the already-compiled template code is used.
(But I doubt any C++ compiler so far uses this kind of optimization.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> OK, that would be my second statement, then. The template is actually 
>> getting recompiled down to object code each time you instantiate it, 
>> even if it's an "export" template.
> 
>   But it's compiled only once even if the same template function is used
> with a given type at several places in the program. (Without the export
> template mechanism the function would be compiled every time it's used.)

Even if the places it's used are in different compilation units? As in, 
if I invoke the compiler 12 times with 12 instantiations of the same 
template in 12 different .cpp files, isn't that code going to have to 
get translated into object code 12 different times?

To phrase it differently, say it took one minute to compile the program 
with the template inline. Could I compile 12 compilation units that 
instantiate the template in 2 minutes? Or is it going to take on the 
order of 12 minutes?

>   And, as I said, I can imagine that compilers could implement optimizations
> where they cache compiled export templates. IOW, if you compile your project
> for the first time, the template code gets compiled, but if you recompile
> the project a second time, the already-compiled template code is used.
> (But I doubt any C++ compiler so far uses this kind of optimization.)

 From the link Fredrik posted, it looks like you can't really do this, 
because the environment that invokes the instantiation may be different. 
(E.g., there may be different overloaded functions in scope that would 
change the meaning of the template.)

-- 
   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:
> >   But it's compiled only once even if the same template function is used
> > with a given type at several places in the program. (Without the export
> > template mechanism the function would be compiled every time it's used.)

> Even if the places it's used are in different compilation units?

  Yes. The compiler couldn't compile the template function even if it wanted
because it only has its declaration, not the implementation (which is in
its own compilation unit).

> As in, 
> if I invoke the compiler 12 times with 12 instantiations of the same 
> template in 12 different .cpp files, isn't that code going to have to 
> get translated into object code 12 different times?

  We are talking about export templates here, not regular ones.

> To phrase it differently, say it took one minute to compile the program 
> with the template inline. Could I compile 12 compilation units that 
> instantiate the template in 2 minutes? Or is it going to take on the 
> order of 12 minutes?

  If the function is an export template, it will only be compiled once,
not 12 times. (Well, naturally assuming all those 12 times use the same
type with that template.)

> >   And, as I said, I can imagine that compilers could implement optimizations
> > where they cache compiled export templates. IOW, if you compile your project
> > for the first time, the template code gets compiled, but if you recompile
> > the project a second time, the already-compiled template code is used.
> > (But I doubt any C++ compiler so far uses this kind of optimization.)

>  From the link Fredrik posted, it looks like you can't really do this, 
> because the environment that invokes the instantiation may be different. 
> (E.g., there may be different overloaded functions in scope that would 
> change the meaning of the template.)

  The environment doesn't change with export templates because they are
in their own compilation units. The only environment is that compilation
unit in question. They are basically no different from regular functions.

-- 
                                                          - Warp

Post a reply to this message

On Tue, 13 May 2008 11:56:34 +0200, Warp <war### [at] tagpovrayorg> wrote:
>   The environment doesn't change with export templates because they are
> in their own compilation units. The only environment is that compilation
> unit in question. They are basically no different from regular functions.

The instantiation context changes, and thus the exported template must be  
recompiled. When compiling a template, name lookup of dependent names is  
performed both in the definition context and in the instantiation context.


-- 
FE

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>>>   But it's compiled only once even if the same template function is used
>>> with a given type at several places in the program. (Without the export
>>> template mechanism the function would be compiled every time it's used.)
> 
>> Even if the places it's used are in different compilation units?
> 
>   Yes. The compiler couldn't compile the template function even if it wanted
> because it only has its declaration, not the implementation (which is in
> its own compilation unit).

Um, OK. That's not what the folks who implemented it in their compiler 
seemed to be saying.

>> As in, 
>> if I invoke the compiler 12 times with 12 instantiations of the same 
>> template in 12 different .cpp files, isn't that code going to have to 
>> get translated into object code 12 different times?
> 
>   We are talking about export templates here, not regular ones.

Right. That's why I'm asking. :-)

>   If the function is an export template, it will only be compiled once,
> not 12 times. (Well, naturally assuming all those 12 times use the same
> type with that template.)

Um, ok.

>   The environment doesn't change with export templates because they are
> in their own compilation units. The only environment is that compilation
> unit in question. They are basically no different from regular functions.

But if in A.cpp I have xyz:MyTemplate<T> and in the body of MyTemplate 
it invokes T.x(i), isn't the code generated going to depend on the 
declarations of T.x that are available at the point I instantiate the 
template? If x is an overloaded function, doesn't it have to know all 
the overloaded functions in scope to pick the one most likely to be the 
one I meant by passing whatever type "i" is?

That seemed to be what the paper about the compiler was talking about.

-- 
   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:
> But if in A.cpp I have xyz:MyTemplate<T> and in the body of MyTemplate 
> it invokes T.x(i), isn't the code generated going to depend on the 
> declarations of T.x that are available at the point I instantiate the 
> template? If x is an overloaded function, doesn't it have to know all 
> the overloaded functions in scope to pick the one most likely to be the 
> one I meant by passing whatever type "i" is?

  I can't think of any way how a certain type T can change in different
compilation units without causing a linker error.

  If you have a class T, it will have a certain declared interface. That
interface doesn't change depending on the context. If you give the template
some other class, for example one derived from T, that's a *different* type,
and thus requires its own instantiation of the template function.

-- 
                                                          - Warp

Post a reply to this message

On Tue, 13 May 2008 21:58:54 +0200, Warp <war### [at] tagpovrayorg> wrote:
>   I can't think of any way how a certain type T can change in different
> compilation units without causing a linker error.
>
>   If you have a class T, it will have a certain declared interface. That
> interface doesn't change depending on the context. If you give the  
> template
> some other class, for example one derived from T, that's a *different*  
> type,
> and thus requires its own instantiation of the template function.

If you change the set of functions that take objects of type T as a  
parameter, the instantiation context changes for a template with T as a  
type parameter, even though the signature of the template remains the same.


-- 
FE

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> If you change the set of functions that take objects of type T as a  
> parameter, the instantiation context changes for a template with T as a  
> type parameter, even though the signature of the template remains the same.

  Can you give me a concrete example?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Can you give me a concrete example?

I probably have all the syntax mixed up, and maybe you need to do 
something more complicated with friend functions and everything else, 
but this is my understanding of what they were talking about in the 
paper?  Basically, the environment in which X<T> is expanded is 
different, so the xyz.xx(4) would promote 4 to a long in main1 and not 
main2.


*** A.h

void X<T>(void);

class A {
   void xx(long i) {
     cout << "Alpha!\n";
   }
}


*** X.cpp

void X<T>(void) {
   T xyz;
   xyz.xx(4);
}

*** Main1.cpp

#include <A.h>

void main1(void) {
   X<A>();
}

*** Main2.cpp

#include <A.h>

void A::xx(int i) {
   cout << "Beta!\n";
}

void main2(void) {
   X<A>();
}



-- 
   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 Wed, 14 May 2008 18:23:54 +0200, Darren New <dne### [at] sanrrcom> wrote:
>
> *** Main2.cpp
>
> #include <A.h>
>
> void A::xx(int i) {
>    cout << "Beta!\n";
> }

This will fail to compile, because you cannot redefine A::xx.

What I had in mind is something like this (untested, for obvious reasons):


// g.hpp
   template <typename T> void g(T t) { /* Do whatever */ }
// end g.hpp

// main.cpp
   export template <typename T> void f();

   int main(){ f<int>(); }
// end main.cpp

// export.cpp
   #include "g.hpp"

   template <typename T> void f(){ g( T() ); }
// end export.cpp


Now make a small change to main.cpp:

// main.cpp
   export template <typename T> void f();

   #include "g.hpp"
   template <> void g(int i) { /* Do something completely different */ }

   int main(){ f<int>(); }
// end main.cpp


The instantiation context for the exported template changes, because there  
is now an additional function participating in name lookup. In this case  
the behaviour also changes because the new function is a better match.  
Note that the signature of the exported template remains the same.

Note: I think the same should apply even if 'g' was not a template, but  
GCC disagrees (tested without 'export' of course). VC does what I expect  
though. I wish I knew which is right.


-- 
FE

Post a reply to this message

Fredrik Eriksson wrote:
> On Wed, 14 May 2008 18:23:54 +0200, Darren New <dne### [at] sanrrcom> wrote:
>>
>> *** Main2.cpp
>>
>> #include <A.h>
>>
>> void A::xx(int i) {
>>    cout << "Beta!\n";
>> }
> 
> This will fail to compile, because you cannot redefine A::xx.

I didn't. I created an overloaded version. One takes an int, the other 
takes a long.  Am I *completely* clueless about C++?

My intent was to get one match to do a silent upcast from int to long, 
and the other to match the more-appropriate int-accepting function.

-- 
   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 Wed, 14 May 2008 22:52:33 +0200, Darren New <dne### [at] sanrrcom> wrote:
> Fredrik Eriksson wrote:
>> On Wed, 14 May 2008 18:23:54 +0200, Darren New <dne### [at] sanrrcom> wrote:
>>>
>>> *** Main2.cpp
>>>
>>> #include <A.h>
>>>
>>> void A::xx(int i) {
>>>    cout << "Beta!\n";
>>> }
>>  This will fail to compile, because you cannot redefine A::xx.
>
> I didn't. I created an overloaded version. One takes an int, the other  
> takes a long.  Am I *completely* clueless about C++?

You cannot add overloads to class methods from outside the class. All  
overloads must be declared in the class declaration.


-- 
FE

Post a reply to this message

Fredrik Eriksson wrote:
> You cannot add overloads to class methods from outside the class. All 
> overloads must be declared in the class declaration.

Thanks!

-- 
   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:
> *** A.h

> void X<T>(void);

> class A {
>    void xx(long i) {
>      cout << "Alpha!\n";
>    }
> }

> #include <A.h>

> void A::xx(int i) {
>    cout << "Beta!\n";
> }

  You are trying to implement a function void A::xx(int) which hasn't
been declared in the class A declaration. It won't compile.

  Note that void A::xx(long) and void A::xx(int) are two different functions,
with different fingerprints. You cannot override one with the other.

-- 
                                                          - Warp

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> Now make a small change to main.cpp:

> // main.cpp
>    export template <typename T> void f();

>    #include "g.hpp"
>    template <> void g(int i) { /* Do something completely different */ }

>    int main(){ f<int>(); }
> // end main.cpp

  I don't see how this causes a problem described earlier. This simply
requires main.cpp to be recompiled (after all, it's the one which has
been changed), which will result in a new object file which does not
use the export template.

  Why would this cause the need to recompile the export template for
each usage in the program?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   You are trying to implement a function void A::xx(int) which hasn't
> been declared in the class A declaration. It won't compile.

That I didn't know. Will it work if you just make xx(int) and xx(long) 
globals?

>   Note that void A::xx(long) and void A::xx(int) are two different functions,
> with different fingerprints. You cannot override one with the other.

Well, I was trying to overload, not override as such.

-- 
   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:
> That I didn't know. Will it work if you just make xx(int) and xx(long) 
> globals?

  Maybe what you are trying to write is something like this:

foo.cc:
export template<typename T>
void foo(T t) { bar(t); }


a.cc:
export template<typename T>
void foo(T t);

void bar(int i);

void a() { foo(5); }


b.cc:
export template<typename T>
void foo(T t);

void bar(long i);

void b() { foo(5); }


  I see how that could make some difference.

-- 
                                                          - Warp

Post a reply to this message