Virtual method inlining

[s0suk3]

I've heard of virtual method inlining in Java, and I'd like to know if the same is possible in C++. If so, in which cases is it applicable?

I ask because I'm learning Direct3D, and I want to know if it's OK to use virtual methods for rendering operations that are performed at every frame, or if I should give up virtual methods and just do all rendering in a single file, of course at the expense of loss of abstraction.

 

[Ian Collins]

I've heard of virtual method inlining in Java, and I'd like to know if the same is possible in C++. If so, in which cases is it applicable?

I ask because I'm learning Direct3D, and I want to know if it's OK to use virtual methods for rendering operations that are performed at every frame, or if I should give up virtual methods and just do all rendering in a single file, of course at the expense of loss of abstraction.

** Please wrap your lines to something readable! **

The compiler may inline a virtual method if it knows the type of an
object. In the following trivial example, f.f() will probably be
inlined because the compiler knows that b is a B.

struct A
{
int n;
virtual void f() { n = 0; }
};

struct B : A
{
void f() { n = 10; }
};

int main()
{
B b;
b.f();
}

 

[1 2]

** Please wrap your lines to something readable! **

The compiler may inline a virtual method if it knows the type of an
object.  In the following trivial example, f.f() will probably be
inlined because the compiler knows that b is a B.

struct A
{
   int n;
   virtual void f() { n = 0; }

};

struct B : A
{
   void f() { n = 10; }

};

int main()
{
   B b;
   b.f();

}

Well that's pretty much non-virtual method inlining, because B::f is
not virtual (even though A::f is), not to mention that you're calling
it through a statically-known B instance.

In the code I'm writing, there are a lot of cases where the runtime
type is not known statically (after all, that's the whole point of
polymorphism).

 

[1 2]

I quote from Wikipedia:
"In computing, inline expansion, or inlining, is a manual or compiler
optimization that replaces a function call site with the body of the
callee."

How do you expect the (non-JIT-)compiler to know which body to inline if
the type of the object is not known at compile-time?

Thank you all, I guess that's why all the samples in the DX SDK are so
non-object-oriented and hard to follow

 

[Thomas Richter]

Am 07.11.2012 11:33, schrieb 1 2:

Well that's pretty much non-virtual method inlining, because B::f is
not virtual (even though A::f is), not to mention that you're calling
it through a statically-known B instance.

Ehem. B::f *is* virtual. It doesn't require a "virtual" keyword to make
it virtual - it is sufficient to have it virtual in the base class.

Yes, of course here the compiler can see the full type, and that is also
the reason why a compiler could inline it.

In the code I'm writing, there are a lot of cases where the runtime
type is not known statically (after all, that's the whole point of
polymorphism).

In that case, the compiler likely cannot inline it. (Of course, nothing
stops anyone from writing a JIT compiler for C++, but this is rather
untypical, and in classical compiler-linker setups, the compiler does
not know the dynamic type of a polymorphic class.)

Greetings,
Thomas

 

[Tobias Müller]

Well that's pretty much non-virtual method inlining, because B::f is
not virtual (even though A::f is),

B::f is implicitly virtual, if A::f is virtual.

not to mention that you're calling
it through a statically-known B instance.

That's the whole point.
Inlining means to copy the content of the called function into the calling
function. For this to be possible, the content of the called funtion has to
be known statically.

In C++11, you can qualify a virtual method 'final'. That means it can be
inlined if it is called via a pointer of the same class:

struct A
{
virtual void f() { /* do stuff */ }
};

struct B : A
{
virtual void f() final { /* do other stuff */ }
};

void process(A* a)
{
a->f(); // cannot be inlined
}

void process(B* b)
{
b->f(); // can be inlined
}

In the code I'm writing, there are a lot of cases where the runtime
type is not known statically (after all, that's the whole point of
polymorphism).

OO-style runtime polymorphism is not the only type of polymorphism.
Polymorphism via templates is another possibility.
We are using a template based rendering library at work, that generates
performant code even if the rendering of every pixel is done in its own
function.
The library is highly polymorphic, but at compile time, not at runtime.

There are programming languages like Haskell, that rely almost exclusively
on compile time polymorphism. And Haskell still allows to write highly
generic/polymorphic code. Typical Haskell code is probably even more
generic than typical C++ code.

Tobi

 

[1 2]

B::f is implicitly virtual, if A::f is virtual.


That's the whole point.
Inlining means to copy the content of the called function into the calling
function. For this to be possible, the content of the called funtion has to
be known statically.

In C++11, you can qualify a virtual method 'final'. That means it can be
inlined if it is called via a pointer of the same class:

struct A
{
   virtual void f() { /* do stuff */ }

};

struct B : A
{
   virtual void f() final { /* do other stuff */ }

};

void process(A* a)
{
   a->f(); // cannot be inlined

}

void process(B* b)
{
   b->f(); // can be inlined

}

OO-style runtime polymorphism is not the only type of polymorphism.
Polymorphism via templates is another possibility.
We are using a template based rendering library at work, that generates
performant code even if the rendering of every pixel is done in its own
function.
The library is highly polymorphic, but at compile time, not at runtime.

There are programming languages like Haskell, that rely almost exclusively
on compile time polymorphism. And Haskell still allows to write highly
generic/polymorphic code. Typical Haskell code is probably even more
generic than typical C++ code.

Thanks, very insightful!

I hadn't thought of using compile-time polymorphism, but that's
probably because I think the lack of method signatures is a bit of a
problem. For example, with runtime polymorphism, you might have
something like this:

class Shape
{
public:
virtual void Draw(int x, int y) = 0;
};

void DrawShape(Shape* s)
{
s->Draw(200, 100);
}

With compile-time polymorphism, you would have:

// Note: no Shape base class

template<class Shape>
void DrawShape(Shape* s)
{
s->Draw(200, 100);
}

It's not clear what operations the class supports, and what are the
parameter/return types of the methods. On the other hand, compile-time
polymorphism works nicely for things like STL iterators, where the
supported operations are clear from the nature of the object
(basically, iterators should behave as pointers).

P.S. didn't know about the "once virtual, always virtual" rule, even
after using C++ for so long!

 

[Stuart]

P.S. didn't know about the "once virtual, always virtual" rule, even
after using C++ for so long!

That's why I always put the keyword "virtual" on virtual methods,
regardless whether the method is implicitly or explicitly virtual. If I
don't put a comment in front of it, then it should be clear that the
method overrides a base class method:

class Foo {
/** Does something.
*/
virtual void doSomething ();
};

class Bar : public Foo {
// No comment needed, the "superfluous" virtual
// should indicate that this method is explained
// in some base class.
virtual void doSomething ();

/** Does another thing.
*/
virtual void doAnotherThing (); // comment needed
};

Regards,
Stuart

 

[Jorgen Grahn]

.

I hadn't thought of using compile-time polymorphism, but that's
probably because I think the lack of method signatures is a bit of a
problem. For example, with runtime polymorphism, you might have
something like this:

class Shape
{
public:
virtual void Draw(int x, int y) = 0;
};

void DrawShape(Shape* s)
{
s->Draw(200, 100);
}

With compile-time polymorphism, you would have:

// Note: no Shape base class

template<class Shape>
void DrawShape(Shape* s)
{
s->Draw(200, 100);
}

I'd prefer to pass a const reference, not a pointer to non-const.

It's not clear what operations the class supports, and what are the
parameter/return types of the methods. On the other hand, compile-time
polymorphism works nicely for things like STL iterators, where the
supported operations are clear from the nature of the object
(basically, iterators should behave as pointers).

Isn't the situation the same here, though? Shapes can be drawn. Just
document that, and trust the compiler to catch any errors.

On the other hand ...

I don't use run-time polymorphism much, and I don't like working with
it. I never used Smalltalk or Java. But when the alternative is a
huge switch statement even I find it preferable. Isn't this a
textbook example of such a case?

If you have to draw a changing bunch of mixed objects that means you
have to call various drawing functions, and you cannot statically
decide which ones in which order. You worry about the performance
penalty for virtual calls, but what alternative would be faster?
The same job still has to be done.

(The only optimization I can think of at the moment is to draw all Foo
objecte before all Bar objects, to keep the instruction cache warm.)

/Jorgen

 

[1 2]

On Wed, 2012-11-07, 1 2 wrote:

...











I'd prefer to pass a const reference, not a pointer to non-const.


Isn't the situation the same here, though?  Shapes can be drawn. Just
document that, and trust the compiler to catch any errors.

On the other hand ...

I don't use run-time polymorphism much, and I don't like working with
it.  I never used Smalltalk or Java.  But when the alternative is a
huge switch statement even I find it preferable.  Isn't this a
textbook example of such a case?

Exactly. In real code, a class might support quite a few methods
(maybe a couple dozen if it's part of a class hierarchy), and the
parameters for some of them can be more numerous and complicated than
in the example above.

Actually I just thought of a solution: combine the contracts provided
by runtime polymorphism with the fast calls of compile-time
polymorphism. We can define a COM interface or an abstract class for
the polymorphic operations:

interface IShape : IUnknown
{
HRESULT Draw(int x, int y);
}

And in the code that uses the polymorphic operations, we use a
template parameter, but make sure that it implements the interface by
using a static_assert that tests a std::is_base_of:

template<class Shape>
void DrawShape(Shape* s)
{
static_assert(std::is_base_of<IShape, Shape>::value, "Shape must
implement IShape");

s->Draw(200, 100);
}

I can definitely see this being used at large scale.

 

[1 2]

Missing /virtual/ keyword.







What is the point of doing that?  The compiler doesn't know that Draw is
"final" so still requires dynamic (virtual dispatch) unless it knows
Shape is the most derived type; the "final" overrider in C++11 improves
the situation somewhat.

OK, then maybe it can be changed to the following to disable calling
through the vtable:

template<class Shape>
void DrawShape(Shape* s)
{
static_assert(std::is_base_of<IShape, Shape>::value, "Shape must
implement IShape");

s->Shape:raw(200, 100);
}

 

[1 2]

Totally pointless.

Why? It accomplishes what I said earlier: combine the contracts
provided by runtime polymorphism with the fast (w/o virtual dispatch)
calls of compile-time polymorphism.

 

[1 2]

Pointless because you need the object that draws all the shapes to be
aware of all the different types of shapes which is a nonsense from a
design point of view.

No it doesn't need that. Where in this code:

template<class Shape>
void DrawShape(Shape* s)
{
static_assert(std::is_base_of<IShape, Shape>::value, "Shape must
implement IShape");

s->Shape:raw(200, 100);
}

do you see awareness of all the different types of shapes? It's just
like the original runtime polymorphism and compile-time polymorphism
examples in my reply to Tobias Müller, except that I basically
combined the two into one.

 C++ templates are great especially for things
such as generic containers/algorithms, traits and policies but you are
misusing them: you need to learn how to do proper OOP.

I know proper OOP. Normally I would just use runtime polymorphism and
no templates at all (in this case), but this is more of an
optimization issue (maybe premature optimization if the virtual call
overhead is negligible compared to the actual work of the method, but
not otherwise).

 

[Tobias Müller]

The code that instantiates the template has to pass an object of the
correct type to benefit from your "optimization" which means that code
needs to know all the different types which is a nonsense from a design point of view.

That's exactly the point of compile time polymorphism. The caller can of
course be a template itself, but at one point you have an object of a
concrete type anyway, that's where the template is instanciated.
This whole concept is of course pointless if you want to draw an
inhomogenous collection of shapes. There you have to find out the concrete
type by hand, which is worse that normal virtual function dispatch IMO.

It is an "optimization" I have never had to employ modulo *normal* (read:
"sane") template use.

Then again it seems to be a real demand amongst 'sane' developers to
restrict the types for template arguments, how else do you explain C++
'concepts'? IShape is just a poor men's 'concept'.
Typeclasses in Haskell or Traits in Rust (www.rust-lang.org) are also
conceptionally similar.

Tobi

 

[Bo Persson]

Tobias Müller skrev 2012-11-07 13:50:

In C++11, you can qualify a virtual method 'final'. That means it can be
inlined if it is called via a pointer of the same class:

struct A
{
virtual void f() { /* do stuff */ }
};

struct B : A
{
virtual void f() final { /* do other stuff */ }
};

void process(A* a)
{
a->f(); // cannot be inlined
}

Assuming inlining, if 'process' gets inlined we again might know the
static type of a at the call site, and inline that call too.

void process(B* b)
{
b->f(); // can be inlined
}

Here is is easier, but just a little bit.


Bo Persson

 

[Tobias Müller]

That was the point I was making: if a single object is responsible for
drawing all the shapes then for it to benefit from this dubious
"optimization" it needs to be aware of all the different sub-class types
in order to correctly instantiate this useless function template.

I really cannot that single object you are talking about.
For example if you want to draw all pixels of an Image, you could use the
same rendering algorithm for your collection of pixels and it will be
nicely optimized due to inlining.
I wouldn't even consider rendering pixel like this with runtime
polymorphism.

Consider the following example:

class Drawable
{
public:
virtual void draw(/*...*/) = 0;
};

template <typename Iterator>
void drawSequence(Iterator begin, Iterator end)
{
static_assert(std::is_base_of<Drawable,
std::iterator_traits<Iterator>::value_type>::value, "Must implement
Drawable");
for (Itetator it = begin; it != end; ++it)
it->draw(/*...*/);
}

class Pixel : public Drawable
{
public:
virtual void draw(/*...*/) final { /* simple */ }
};

class Image : public Drawable
{
public:
virtual void draw(/*...*/) final
{
// can be optimized, value type is statically known
drawSequence(pixels.begin(), pixels.end());
}
private:
std::vector<Pixel> pixels;
};

class Path : public Drawable
{
public:
virtual void draw(/*...*/) final { /* complex */ }
};

typedef boost::indirect_iterator<std::vector<Drawable*>, Drawable> ItD;

int main(/*.../)
{
std::vector<Drawable*> objects;
objects.push_back(new Image);
objects.push_back(new Path);
// Normal runtime polymorphism
draw_sequence(ItD(objects.begin()), ItD(objects.end()));
}

Like I said earlier C++ templates are great I just feel they are being
misused in this case. This is a classic example of premature optimization.

I think in a program or library that deals with graphics, this an important
design decision, not premature optimization.

Tobi