Template turing-completeness and code size optimization

A

a.tavs

Hello everyone,

I'd like to bother you asking two questions:
1) does the turing-completeness of c++ template metalanguage hinders
templated code optimization? If so, how?
2) is it possible to write a c++ compiler that removes ``duplicated
instantiations'' i.e. template instantiations with different template
parameters but identical low-level implementation such as,
presumeably,
Foo<int*> and Foo<void*>?

TIA,

Tavs
 
J

joecook

Hello everyone,

I'd like to bother you asking two questions:
1) does the turing-completeness of c++ template metalanguage hinders
templated code optimization? If so, how?

That's an interesting question, albeit a bit confusing. One way to
answer might be that if the template features in C++ had been defined
more narrowly, such as to further restrict the possible set of
problems that could be solved in it, then there would be potentially
be better optimizations possible. Of course, this is assuming that
such a definition would be simpler (it's hard to imagine otherwise).
Nevertheless, you could have a non-turing complete language that was
much more difficult to optimize.

What you are asking might be equivalant to:

Given a new programming language X, would this hinder or help
optimizations vs. c++ ? But you don't mention what "X" might be.
2) is it possible to write a c++ compiler that removes ``duplicated
instantiations'' i.e. template instantiations with different template
parameters but identical low-level implementation such as,
presumeably,
Foo<int*> and Foo<void*>?

Sure! I don't see why not. In fact, in many cases, compilers remove
the only instantiation of a template because it is optimized away.

Joe C
 
B

Bart van Ingen Schenau

Hello everyone,

I'd like to bother you asking two questions:
1) does the turing-completeness of c++ template metalanguage hinders
templated code optimization? If so, how?
2) is it possible to write a c++ compiler that removes ``duplicated
instantiations'' i.e. template instantiations with different template
parameters but identical low-level implementation such as,
presumeably,
Foo<int*> and Foo<void*>?

Yes, it is possible to write such a compiler (or rather linker). In
fact, it has already been done. The Microsoft linker supports such
optimisations.
Note that enabling these optimisations makes the implementation non-
conforming w.r.t. the C++ standard, as different functions end up
having the same address, which goes contrary to the rules in the C++
standard.
TIA,

Tavs

Bart v Ingen Schenau
 
P

Pascal J. Bourguignon

Bart van Ingen Schenau said:
Yes, it is possible to write such a compiler (or rather linker). In
fact, it has already been done. The Microsoft linker supports such
optimisations.
Note that enabling these optimisations makes the implementation non-
conforming w.r.t. the C++ standard, as different functions end up
having the same address, which goes contrary to the rules in the C++
standard.

Well it's easy enough to allocate a 'JMP common' instruction for each
function...
 
A

a.tavs

(e-mail address removed) ha scritto:
On Jan 27, 5:45 pm, (e-mail address removed) wrote:
Given a new programming language X, would this hinder or help
optimizations vs. c++ ? But you don't mention what "X" might be.
Ada/Java generics?
Sure! I don't see why not. In fact, in many cases, compilers remove
the only instantiation of a template because it is optimized away.
Uh, I made a mistake with the 2nd the question, you know, it was late
for me when I wrote the post...
Obviously, if you have the same object code in more than one
instanciation, you can trash all but one instantiation at link time.
What I wanted to ask was: can the compiler optimize space consumption
by guessing that two instantiations Foo<T1> and Foo<T2> /can/ be
compiled into the same object code?

For example the compiler could compile Foo<T1> and Foo<T2>
differently, because of some optimization, writing two different
object files. On the other hand, if I care about space consumption, I
may want to have those instantiations compiled into the same object.


Tavs
 
J

James Kanze

Well it's easy enough to allocate a 'JMP common' instruction for each
function...

Or just insert a no-op instruction in front of the code, and use
its address for one of the functions. Only when taking the
function's address, of course, and only do this when the code
actually does compare the two addresses. Admittedly, this does
require a bit of intelligence from the linker. But no more than
a lot of other modern optimization techniques.

In practice, I don't know if it is really worth the effort.
Just do it the way Microsoft does, with a compiler switch to
turn it off if you need strict compatibility. Probably 99% of
all programs will never notice, and not need the switch.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top