looking for validation/rebuttal on this claim

[phyto...@gmail.com]

Assume you have a class template parameterized by some set of types that provides some functionality. In the system there are three specific instantiations of that template. In another codebase a developer has created exactly the c++ code that those templates instantiations (i.e. 3 hand written classes that are verbatim the same except for naming). In this situation are there optimizations that can make the template version faster than the the handwritten?

In a nutshell are there advantages to using templates that can make it even faster than, say generated code with exactly the same content? If there are what are those optimizations?

[Thomas Richter]

On 22.04.2015 23:39, phyto...@gmail.com wrote:
> Assume you have a class template parameterized by some set of types that provides some functionality. In the system there are three specific instantiations of that template. In another codebase a developer has created exactly the c++ code that those templates instantiations (i.e. 3 hand written classes that are verbatim the same except for naming). In this situation are there optimizations that can make the template version faster than the the handwritten?
>
> In a nutshell are there advantages to using templates that can make it even faster than, say generated code with exactly the same content? If there are what are those optimizations?
>

That's one of the questions that are hard to answer without having
access to the compiler and the code in question. But one thing for sure:
Having the code *once* (and templated) makes it surely easier to
maintain and extend than to have it thrice and having to keep three
implementations consistent.

Greetings,
Thomas

[Melzzzzz]

I would be surprised if performance wouldn't be same.

[Öö Tiib]

On Thursday, 23 April 2015 00:39:22 UTC+3, Daniel Davidson wrote:
> Assume you have a class template parameterized by some set of types
> that provides some functionality. In the system there are three
> specific instantiations of that template. In another codebase a
> developer has created exactly the c++ code that those templates
> instantiations (i.e. 3 hand written classes that are verbatim the
> same except for naming). In this situation are there optimizations
> that can make the template version faster than the the handwritten?

One difference is that the templates are header-only.
The ordinary classes (and also full specializations of templates)
are typically split between interface declaration in header file
and translation unit that implements the functionality.

That makes templates to compile slower but gives better
opportunities for the compiler to optimize. Also linkers
sometimes merge code of different instances (that happen to
do exactly same thing) behind same binary code.

> In a nutshell are there advantages to using templates that can make
> it even faster than, say generated code with exactly the same
> content? If there are what are those optimizations?

The efficiency is actually not that interesting advantage. You pay
with slow compilation and linking and achieve that something that
was sufficiently fast is maybe some % faster. The advantage is lack
of maintenance head-ache of the alternative: massive copy-paste.

Lets imagine that there are *only* six copy-pastes of ~500 lines
class and only *one* defect lurking in it.

* The defect is reported by testing about "first" and fixed in that.
* It is reported slightly later in "second" and fixed in that too
but differently, by other guy.
* Some change is requested for "sixth" and yet another maintainer does
modify it but the defect is still there.
* The issue is later found in "third" too but experienced maintainer
senses Déjà vu. So he searches for copy-paste and finds "second",
"third", "fourth" and "fifth". The "first" and "sixth" have been
changed enough so search engine did not find those. He fixes the
4 copies he found in third way.
* Same change is requested for others five that was done in "sixth".

The two different fixes that are applied now to "second" did break
something else in it and "sixth" is still broken. Other five need
to be changed. Bear in mind that it was oversimplified toy example.

[Daniel Davidson]

I should not have said hand-written. This question theoretical - but the setting is actually code generation versus templates. Generated code is easier to understand/debug, etc. But I want to find if and when templates can outperform.

[Daniel Davidson]

Good points. I wanted to keep the question theoretical - but the real setting is templates vs code generation. We have no problem doing either and even mixing both. I want to know of any real *performance* advantages of templates over code generation. Compile time and headaches of each are understood but the real question is - can a compiler do better with a template in terms of faster code. If so under what circumstances?

[Öö Tiib]

I can try to elaborate. A template *is* technically script for
the code generator that is built into compiler. Compiler "knows"
that the code of template instatiation is generated and it does
not know that about code generated externally.

I already wrote about template being header-only. If the other
code generator also generates header-only code then they are on
equal grounds in that sense. Header-only can give serious
advantages but there are several things that are tricky to do
header-only for non-template.

Rest of it is quality of implementation of both contenders.

Modern C++ compilers do excellent work optimizing on all levels.
Everybody see how it is difficult for debugger to map the
optimized code back to C++ text again. On other hand it is tricky
to express some meta-knowledge (likely known for code-generator
writer) in current C++. "Reflection" and "Concepts" might
help ... but these are only future plans right now.

[Daniel Davidson]

I totally agree. A colleague mentioned a set of optimizations that a compiler can perform when dealing with templates that it could not do of the code were generated. Something along the lines of "because the compiler has special information that ties all template instances of a parameterized class together it can find ways of generating more runtime efficient code that the code generation case. I'm specifically looking for any such example - or an authoritative *no - that is not possible*.

[Martin Shobe]

On 4/23/2015 11:15 AM, Daniel Davidson wrote:
> I totally agree. A colleague mentioned a set of optimizations that a compiler can perform when dealing with templates that it could not do of the code were generated. Something along the lines of "because the compiler has special information that ties all template instances of a parameterized class together it can find ways of generating more runtime efficient code that the code generation case. I'm specifically looking for any such example - or an authoritative *no - that is not possible*.

I'm afraid you won't get either. I can't think of any optimizations that
a compiler can perform on a template that it can't perform on code
generated functions. It might be easier for the compiler to optimize the
template and therefore more likely to actually be optimized, but a
compiler could still perform it in the other case as well.

In the end, the answer to the question of whether or not you should
generate templated or non-templated code boils down to.

1) Is the performance of the generated code critical? If not, answer
based on the maintainability of the code-generator (not the generated
code as I'm assuming that you won't have to maintain the generated code
directly.).

2) Otherwise, do it both ways and measure the results. Do it the more
performant way.

Martin Shobe

[woodb...@gmail.com]

On Thursday, April 23, 2015 at 11:15:51 AM UTC-5, Daniel Davidson wrote:
> I totally agree. A colleague mentioned a set of optimizations that a compiler can perform when dealing with templates that it could not do of the code were generated. Something along the lines of "because the compiler has special information that ties all template instances of a parameterized class together it can find ways of generating more runtime efficient code that the code generation case. I'm specifically looking for any such example - or an authoritative *no - that is not possible*.

I'm skeptical about what your colleague says. As Iiib said,
a C++ compiler "knows" the source of the generated code in case
of a template instantiation. Is that something it can build on
in order to make optimizations?

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[woodb...@gmail.com]

> I already wrote about template being header-only. If the other
> code generator also generates header-only code then they are on
> equal grounds in that sense.


> Header-only can give serious
> advantages but there are several things that are tricky to do
> header-only for non-template.

What tricky things do you mean?

>
> Rest of it is quality of implementation of both contenders.
>
> Modern C++ compilers do excellent work optimizing on all levels.
> Everybody see how it is difficult for debugger to map the
> optimized code back to C++ text again. On other hand it is tricky
> to express some meta-knowledge (likely known for code-generator
> writer) in current C++. "Reflection" and "Concepts" might
> help ... but these are only future plans right now.

Are modules getting lost in the shuffle? I hope not.

Brian
Ebenezer Enterprises - "Buy truth, and do not sell it,
get wisdom and instruction and understanding." Proverbs 23:23

http://webEbenezer.net

[Scott Lurndal]

woodb...@gmail.com writes:
>On Thursday, April 23, 2015 at 11:15:51 AM UTC-5, Daniel Davidson wrote:

>> I totally agree. A colleague mentioned a set of optimizations that a comp=
>iler can perform when dealing with templates that it could not do of the co=
>de were generated. Something along the lines of "because the compiler has s=
>pecial information that ties all template instances of a parameterized clas=
>s together it can find ways of generating more runtime efficient code that =
>the code generation case. I'm specifically looking for any such example - o=

>r an authoritative *no - that is not possible*.
>
>I'm skeptical about what your colleague says. As Iiib said,
>a C++ compiler "knows" the source of the generated code in case

>of a template instantiation. Is that something it can build on=20
>in order to make optimizations? =20
>

The compiler will translate the template definition into an
internal intermediate representation. This representation
is designed in such a way as to allow optimization before
the code generation phase. It is much easier to apply
transformations to the intermediate representation than it
is to [re]optimize already generated object code.

[Daniel Davidson]

This knowledge is what I'm after. Do you have a concrete example of such an optimization that occurs in the one case and not in the other?

This is maybe better asked in a c++ compiler group. Anyone know of a better forum to ask this question?

In particular I'm interested in a real optimization - not just an ability to. Although knowing something that can be optimized but is not yet supported by compilers would be useful too.

[Scott Lurndal]

Gcc and LLVM are both open-source. As Linus is wont to say,
'use the source, luke'.

[Scott Lurndal]

You may also wish to consult the dragon book.

[Daniel Davidson]

my force are not so strong.

[Daniel Davidson]

not looking for theory - just an answer to specific question.

[Alain Ketterlin]

Daniel Davidson <phyto...@gmail.com> writes:

>> The compiler will translate the template definition into an
>> internal intermediate representation. This representation
>> is designed in such a way as to allow optimization before
>> the code generation phase. It is much easier to apply
>> transformations to the intermediate representation than it
>> is to [re]optimize already generated object code.
>
> This knowledge is what I'm after. Do you have a concrete example of
> such an optimization that occurs in the one case and not in the other?

No, because there is none. Templates are a source language ("front-end")
thing. They are pure syntax, and template instanciations can be thought
of as being transformed into various pieces of concrete (i.e., not
template) source code before entering the rest of the compilation
pipeline ("middle-end" for target-independent optimizations, and then
"back-end" for architecture-specific optimizations and code-generation).
This ensures optimizations apply to all languages supported by the
compiler.

Of course, the details will vary from one compiler to the other. For
instance, gcc front-ends translate into a format called GIMPLE.
LLVM-based compilers (like clang) translate into, well, LLVM (which is
not a compiler, but rather an intermediate representation---but the name
is also used as an huge number of "optimization passes" and the
orchestration infrastructure). As far as I know, none of these
intermediate representations care about templates. The corresponding
front-ends process templates with their own format (see, e.g., clang's
AST at http://clang.llvm.org/docs/IntroductionToTheClangAST.html).

> In particular I'm interested in a real optimization - not just an
> ability to. Although knowing something that can be optimized but is
> not yet supported by compilers would be useful too.

Go to llvm.org and check documentation there:

- http://llvm.org/docs/LangRef.html describes the intermediate
representation LLVM optimization passes work on

- http://llvm.org/docs/Passes.html gives you a list of common passes

The docs on gcc internals is at https://gcc.gnu.org/onlinedocs/gccint/

There are many things that can be optimized but are not (see
http://en.wikipedia.org/wiki/Full_employment_theorem for an extreme
view on the question). But this does not mean that it is easy to find
something valuable to add...

-- Alain.

[Öö Tiib]

For example it is tricky to define static data members of class
for non-template (or full specialization) in header-only manner.
Knowledge about value of static data member may help compiler to
optimize something.

>
> >
> > Rest of it is quality of implementation of both contenders.
> >
> > Modern C++ compilers do excellent work optimizing on all levels.
> > Everybody see how it is difficult for debugger to map the
> > optimized code back to C++ text again. On other hand it is tricky
> > to express some meta-knowledge (likely known for code-generator
> > writer) in current C++. "Reflection" and "Concepts" might
> > help ... but these are only future plans right now.
>
> Are modules getting lost in the shuffle? I hope not.

What shuffle? I was referring to some obscure preprocessor and template
usages that can be hopefully get rid of with reflection or concepts.

[Scott Lurndal]

Ah, but then someone must, for free, spend the time to
construct an example that will illustrate sufficiently for
someone not versed in compiler technology. Who has the time?

[woodb...@gmail.com]

On Thursday, April 23, 2015 at 4:58:44 PM UTC-5, Alain Ketterlin wrote>

+1

Brian
Ebenezer Enterprises
http://webEbenezer.net

[A. Bolmarcich]

On 2015-04-23, Scott Lurndal <sc...@slp53.sl.home> wrote:
> The compiler will translate the template definition into an
> internal intermediate representation. This representation
> is designed in such a way as to allow optimization before
> the code generation phase. It is much easier to apply
> transformations to the intermediate representation than it
> is to [re]optimize already generated object code.

True. However, is it possible to do those types of optimizations when
linking. A compiler can put the intermediate representation in the
object file, in a section separate from the traditional text section.
Doing such optimizations when linking can be time comsuming, but the
resulting optimization of an exeuctable as a whole may be worth it.

[Daniel Davidson]

This is great! Thank you Alain

[Jorgen Grahn]

On Thu, 2015-04-23, Daniel Davidson wrote:
> On Thursday, April 23, 2015 at 2:05:55 AM UTC-5, Thomas Richter wrote:
>> On 22.04.2015 23:39, phyto...@gmail.com wrote:

>> > Assume you have a class template parameterized by some set of
>> > types that provides some functionality. In the system there are three
>> > specific instantiations of that template. In another codebase a
>> > developer has created exactly the c++ code that those templates
>> > instantiations (i.e. 3 hand written classes that are verbatim the same
>> > except for naming). In this situation are there optimizations that can
>> > make the template version faster than the the handwritten?

>> > In a nutshell are there advantages to using templates that can
>> > make it even faster than, say generated code with exactly the same
>> > content? If there are what are those optimizations?

>> That's one of the questions that are hard to answer without having
>> access to the compiler and the code in question. But one thing for sure:
>> Having the code *once* (and templated) makes it surely easier to
>> maintain and extend than to have it thrice and having to keep three
>> implementations consistent.

> I should not have said hand-written. This question theoretical - but
> the setting is actually code generation versus templates. Generated
> code is easier to understand/debug, etc.

Isn't one of the main problems with generated code that it's /hard/ to
understand and debug? If you have a buggy code generator (compiler
which generates C++, really) you're going to have major problems.

> But I want to find if and
> when templates can outperform.

It's an interesting question, but I don't have any answers.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Daniel Davidson]

On Saturday, April 25, 2015 at 2:06:51 PM UTC-5, Jorgen Grahn wrote:
> > I should not have said hand-written. This question theoretical - but
> > the setting is actually code generation versus templates. Generated
> > code is easier to understand/debug, etc.
>
> Isn't one of the main problems with generated code that it's /hard/ to
> understand and debug? If you have a buggy code generator (compiler
> which generates C++, really) you're going to have major problems.
>

Well, you are asking for an opinion. I'm using tools that make the code fairly straightforward -
https://pub.dartlang.org/packages/ebisu_cpp

I just want to know case where I may be giving something up.