Templates and Inlining

[Elpoca]

Hi:

What rules govern the inlining of templated functions and templated
class methods?

It has always been my understanding that both templated functions and
templated class methods were always expanded inline. Recently, I
replaced an explicitly written function with one implemented using
templates (and partial-template specialisation), in the belief that the
the latter would be entirely inlined-away by the compiler, leaving the
same machine code as the explicitly written function and no
function-call overhead. However, analysis of the machine code produced
by my compiler (Visual C++ 7.1) indicates that the templated functions
are not entirely being removed. In other words, there are still
function calls. By forcing inline expansion (using the non-standards
conformant __forceinline keyword), I can remove the function calls and
make my templated implementation produce exactly the same machine code
as the explicitly written function (and, more importantly, the same
performance). MingW is also not inlining the templated code.

So, my questions are:

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

Long e-mail, but I would appreciate any clarification!

Thanks,
El

[Ulrich Eckhardt]

Elpoca wrote:

What rules govern the inlining of templated functions and templated
class methods?

It has always been my understanding that both templated functions and
templated class methods were always expanded inline. Recently, I
replaced an explicitly written function with one implemented using
templates (and partial-template specialisation), in the belief that the
the latter would be entirely inlined-away by the compiler, [..]
I believe that a template specialisation is not implicitly inline, although
for classes the rule applies that every memberfunction defined in the body
of the class definition is implicitly inline.
[..] leaving the
same machine code as the explicitly written function and no
function-call overhead. However, analysis of the machine code produced
by my compiler (Visual C++ 7.1) indicates that the templated functions
are not entirely being removed. In other words, there are still
function calls. By forcing inline expansion (using the non-standards
conformant __forceinline keyword), I can remove the function calls and
make my templated implementation produce exactly the same machine code
as the explicitly written function (and, more importantly, the same
performance). MingW is also not inlining the templated code.

So, my questions are:

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

Firstly, inlining is only vaguely defined by the standard and always only a
suggestion to the compiler. The compiler is free to inline functions
without the 'inline' keyword and to not inline them even with it. People
also say that it's a 'quality of implementation' issue.

Secondly, what 'inline' guarantees is that it prevents a duplicate
definition from creating an error, but that's the only thing guaranteed.

Uli

--
FAQ: http://ma.rtij.nl/acllc-c++.FAQ.html

[Phlip]

Elpoca wrote:

What rules govern the inlining of templated functions and templated
class methods?

It has always been my understanding that both templated functions and
templated class methods were always expanded inline.
The keyword 'inline' has two implicit manifestations. Functions defined
inside a class, and template functions, have an implicit 'inline' on them.

The meaning of 'inline' is not that the function's opcodes will expand
inline. That is often a side-effect. The meaning is the function can break
the One Definition Rule, and can appear in many translation units (.cpp
files). The type of everything in the function must always be the same.

That rule permits the compiler to aggressively optimize the function's
opcodes, once per object file. So in-line opcodes are often the result.
However, the compiler is also allowed to in-line functions not declared
'inline'.

The compiler may do anything it likes to optimize, so long as the result
functions "as if" it had followed the Standard's instructions regarding
opcodes.
So, my questions are:

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
Because that's implementation specific to those compilers. They probably all
punted.
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
No.
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?
No.
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

Or maybe me. ;-)

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

[Phlip]

Elpoca wrote:

What rules govern the inlining of templated functions and templated
class methods?

Oh, one more thing. Excessive opcode inlining might make the calling
function overflow your CPU cache, and this will slow down your program.

Instead of reading the machine language output and guessing about
optimization, measure your program and see where it's slow. It might not be
these templates! Only optimize the parts that are measurably slow. This
strategy optimizes programmer performance.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

[Bart van Ingen Schenau]

Elpoca wrote:

Hi:

What rules govern the inlining of templated functions and templated
class methods?
<snip> So, my questions are:

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
They were not expanded inline, because the compiler decided not to do
so. :-)
During optimisation, the compiler must decide how the potential speed
gain from inlining a function weighs against the reduction in
executable size that comes from not inlining the function.
With todays computers with large instruction caches, it may well turn
out that reducing executable size ultimately results in a better
performance, because there are less cache misses.

Note: by the time the compiler starts to optimise the code, there is no
difference between a template (member-)function and a non-template
(member-)function that was declared inline.
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?
Even though you can define a template in multiple translation units
(read: source file with expanded headers), template (member-)functions
follow the same rules for inlining as non-template functions.

If you want a template function to be inlined, you must declare it with
the keyword 'inline', or you must have the full function definition
inside the class definition.

Note: the 'inline' keyword is just a hint to the compiler. The compiler
is free to completely disregard your request to inline the function.
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?
If there was, I hope to have clarified matters.

Long e-mail, but I would appreciate any clarification!

Thanks,
El

Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/

[Francis Glassborow]

In article <11*********************@g47g2000cwa.googlegroups. com>,
Elpoca <el****@gmail.com> writes

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
Even when a function is explicitly marked as inline the compiler is free
to ignore the request. It has to be because sometimes functions are
simply to complicated to be inlined in all contexts.
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
No they are not and it is an unfortunate consequence of the common
mechanisms for providing the definitions of template functions and
classes that the implicit inlining appears to be required.
3. Does the inline keyword have any impact when used with templated
functions and templated class methods? Only in that it allows the same function to be implemented more than
once within a program (which is the only required consequence of the
inline keyword)
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

In so far as you believe that the inline keyword and implicit inlining
of in class definitions of member functions places any mandatory
requirement on the implementation, Yes.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

[Elpoca]

Bart van Ingen Schenau wrote:

Elpoca wrote: [...]

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?

They were not expanded inline, because the compiler decided not to do
so. :-)
During optimisation, the compiler must decide how the potential speed
gain from inlining a function weighs against the reduction in
executable size that comes from not inlining the function.
With todays computers with large instruction caches, it may well turn
out that reducing executable size ultimately results in a better
performance, because there are less cache misses.

Note: by the time the compiler starts to optimise the code, there is no
difference between a template (member-)function and a non-template
(member-)function that was declared inline.

That is what I thought, but then why, when compiled with GCC, would my
templated method perform much worse then an explicitly written
function? I can't believe GCC's optimiser is so poor. With Visual C++
it performs better, but it not entirely inlining the code as I thought
it should (unless forced).

2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?

Even though you can define a template in multiple translation units
(read: source file with expanded headers), template (member-)functions
follow the same rules for inlining as non-template functions.

If you want a template function to be inlined, you must declare it with
the keyword 'inline', or you must have the full function definition
inside the class definition.

So, template functions are *not* inlined by default? If this is the
case, why does the compiler not complain about multiple definitions of
the same function in multiple translation units? Or do you mean
template specialisations? Those, we can all agree, definitely need to
be declared inline.
Note: the 'inline' keyword is just a hint to the compiler. The compiler
is free to completely disregard your request to inline the function.

4. Is there something fundamentally wrong with my understanding and
analysis of all of this?
If there was, I hope to have clarified matters.

Thanks for your response.

Long e-mail, but I would appreciate any clarification!

Thanks,
El

Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/

[Elpoca]

Francis Glassborow wrote:

[...]

3. Does the inline keyword have any impact when used with templated
functions and templated class methods?

Only in that it allows the same function to be implemented more than
once within a program (which is the only required consequence of the
inline keyword)

This implies that the absence of the inline keyword will lead to
problems. However, my understanding is that this is only the case for
template specialisations.

Perhaps an example will help. Is there a difference between the
following two functions?

template< typename T > sq( T x ) { return x*x; }
template< typename T > inline sq( T x ) { return x*x; }

I think no, but your answer suggests I think wrongly...

4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

In so far as you believe that the inline keyword and implicit inlining
of in class definitions of member functions places any mandatory
requirement on the implementation, Yes.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

[Stephan Brönnimann]

Elpoca schrieb:

Bart van Ingen Schenau wrote:

Even though you can define a template in multiple translation units
(read: source file with expanded headers), template (member-)functions
follow the same rules for inlining as non-template functions.

If you want a template function to be inlined, you must declare it with
the keyword 'inline', or you must have the full function definition
inside the class definition.

So, template functions are *not* inlined by default? If this is the
case, why does the compiler not complain about multiple definitions of
the same function in multiple translation units? Or do you mean
template specialisations? Those, we can all agree, definitely need to
be declared inline.

It is up to the compiler how multiple template instantiations are
handled.
Sun CC creates object files, g++ issues weak symbols (see man nm
for details).

Regards, Stephan
br****@osb-systems.com
Open source rating and billing engine for communication networks.

[James Dennett]

Elpoca wrote:

Hi:

What rules govern the inlining of templated functions and templated
class methods?

It has always been my understanding that both templated functions and
templated class methods were always expanded inline. Recently, I
replaced an explicitly written function with one implemented using
templates (and partial-template specialisation), in the belief that the
the latter would be entirely inlined-away by the compiler, leaving the
same machine code as the explicitly written function and no
function-call overhead. However, analysis of the machine code produced
by my compiler (Visual C++ 7.1) indicates that the templated functions
are not entirely being removed. In other words, there are still
function calls. By forcing inline expansion (using the non-standards
conformant __forceinline keyword), I can remove the function calls and
make my templated implementation produce exactly the same machine code
as the explicitly written function (and, more importantly, the same
performance). MingW is also not inlining the templated code.

So, my questions are:

1. Why aren't my templated functions and templated class methods calls
being removed (i.e., optimised away) by inlining?
Accurate but useless answer: because the compiler chooses
not to inline them. As for why it might choose not to do
so, or to inline things, there are many possible factors,
including optimization settings, the "inline" keyword, the
complexity of the item being inlined and so on.
2. Are templated functions and templated class methods supposed to be
inlined by the compiler?
Nothing is "supposed" to be inlined by the compiler -- it's
up to those writing compilers to choose what to inline. They
are "supposed" to consider inlining functions that are marked
as inline by users, for some meaning of "supposed". We might
also want them to make smart choices and inline where it will
help performance, and avoid inlining where it would hurt
performance, but that's not easy to determine.
3. Does the inline keyword have any impact when used with templated
functions and templated class methods?
It could do -- it acts as a hint to the compiler to consider
inlining them. (Compilers can inline without this hint, for
any function, not just function templates, but the "inline"
keyword may be considered by some compilers when optimizing.)
4. Is there something fundamentally wrong with my understanding and
analysis of all of this?

Only that you seem to be assuming that optimizations (such as
inlining) are imposed by standards, when in reality they're up
to the "quality of implementation" of individual compilers.

(For completeness I should mention that "inline" has one
effect that is more than just a hint, which is to allow
multiple (identical) definitions of a function in different
translation units within a program, but that's an effect
that is not relevant in the case of function templates, as
they have the same dispensation in any case.)

-- James

[Chris Theis]

"Elpoca" <el****@gmail.com> wrote in message
news:11*********************@g49g2000cwa.googlegro ups.com...

[SNIP] That is what I thought, but then why, when compiled with GCC, would my
templated method perform much worse then an explicitly written
function? I can't believe GCC's optimiser is so poor. With Visual C++
it performs better, but it not entirely inlining the code as I thought
it should (unless forced).

Are you sure that you're really comparing the performance of these few
(inline-expanded) instructions only and that there are not other factors
that might be slowing down your program?

Chris

[Chris Theis]

"Elpoca" <el****@gmail.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

Francis Glassborow wrote:

[...]

3. Does the inline keyword have any impact when used with templated
functions and templated class methods?

Only in that it allows the same function to be implemented more than
once within a program (which is the only required consequence of the
inline keyword)

This implies that the absence of the inline keyword will lead to
problems. However, my understanding is that this is only the case for
template specialisations.

Perhaps an example will help. Is there a difference between the
following two functions?

template< typename T > sq( T x ) { return x*x; }
template< typename T > inline sq( T x ) { return x*x; }

I think no, but your answer suggests I think wrongly...

[SNIP]

Your thoughts are right, but as pointed out before by others the "inline"
keyword simply breaks the one-definition rule. However, templates are
special anyway in this respect and their treatment differs by the different
compilers. So you can think of them as implicitly inlined, which does not
necessarily mean that they are or need to be inline expanded!

Cheers
Chris