Resolution of virtual functions

[Aguilar, James]

I've heard that virtual functions are relatively ineffecient, especially
virtual functions that are small but get called very frequently. Could
someone describe for me the process by which the address of a virtual
function is resolved and what the hidden costs associated with virtual
functions are? I've heard the same of typeof (that it is inefficient if
used in high traffic code) -- if you've the time, could you explain how
typeof works (inside the computer) and why it costs so much?

 

[Alexander Terekhov]

: ...

Only because you kindly helped Bazarov. ;-)

http://www.codesourcery.com/cxx-abi/abi.html#vtable
http://www.codesourcery.com/cxx-abi/abi.html#vcall
http://www.codesourcery.com/cxx-abi/abi.html#rtti

regards,
alexander.

 

[Alf P. Steinbach]

* Aguilar, James:

I've heard that virtual functions are relatively ineffecient, especially
virtual functions that are small but get called very frequently.

The relative cost of a call increases with decreased size, as it does for
any function.

Could
someone describe for me the process by which the address of a virtual
function is resolved

In the simplest case, for a typical vtable-based implementation, o.m()
translates to

(*(o.__vtable + __index_of_m))( &o )

expressed in pseudo C.

and what the hidden costs associated with virtual functions are?

AFAIK there are no hidden costs.

I've heard the same of typeof (that it is inefficient if
used in high traffic code) -- if you've the time, could you explain how
typeof works (inside the computer) and why it costs so much?

'typeof' is a proposed extension to the language, it's not yet standard.

I'm not sure why it could be inefficient; the main idea is a compile-time
operator that does not add any overhead at all.

Possibly you mean 'typeid'? Yes that, and RTTI in general, can be perhaps be
inefficient, which is possibly why RTTI is off by default in MSVC. Consider


#include <iostream>
#include <typeinfo>

struct BaseA{ int x; virtual ~BaseA(){} virtual void foo(){} };
struct BaseB{ int x; virtual ~BaseB(){} virtual void foo(){} };
struct Lucky: BaseA, BaseB {};

int main()
{
Lucky me;
BaseA& a = me;

std::cout << typeid(a).name() << std::endl;
}


Here 'me' must logically (however it is optimized) contain _two_
vtable pointers; one to BaseA vtable, and one to BaseB vtable, for
otherwise 'a' would not have its vtable pointer at expected offset.

And typeid may not know anything about the excistence of Lucky, it
only has a bona-fide BaseA object.

So either each object must contain an id of the dynamic type class,
or vtables must be duplicated to serve as such id, or extra
indirection must be used in vtable pointer (i.e. pointer to
type-info which in turn contains pointer to vtable).

At least that's how far my thinking goes right now, late at night.

 

[Rolf Magnus]

* Aguilar, James:

The relative cost of a call increases with decreased size, as it does
for any function.

Not if the function gets inlined. And that's the problem with virtual
functions. As soon as you call them through a reference or pointer,
they can't get inlined anymore. Further, it usually needs to be called
through three levels of indirection.

 

[David Hilsee]

Not if the function gets inlined. And that's the problem with virtual
functions. As soon as you call them through a reference or pointer,
they can't get inlined anymore. Further, it usually needs to be called
through three levels of indirection.

You might want to clarify that third sentence. It almost sounds like you
meant that a virtual function will never be inlined anywhere in the code if
it is ever invoked through a reference or a pointer. Did you mean to say
that it is unlikely that a compiler will be able to inline a virtual
function at a particular location if, at that location, it is invoked
through a reference or pointer?

Also, I'm not sure what you meant by "three levels of indirection."

 

[Alf P. Steinbach]

* Rolf Magnus:

Not if the function gets inlined.

Yes, it's a bit late.

With inlining the relative cost per call can decrease with size, because
the cost is a consequence of the increased call site code size (if it is),
e.g. influencing caching or even swapping.

Some numbers would be great to clarify that "relatively inefficient".

And that's the problem with virtual
functions. As soon as you call them through a reference or pointer,
they can't get inlined anymore.

That turns out not to be the case. Only when the pointer or reference
refers to an object of statically unknown dynamic type is inlining
practically impossible. AFAICS.

Further, it usually needs to be called through three levels of indirection.

Whether that affects efficiency adversely depends very much on the computer
and C++ implementation.

 

[Ali Cehreli]

I've heard that virtual functions are relatively ineffecient,

Relative to what? If relative to non-virtual functions, we are
comparing apples and oranges.

Virtual functions provide behavior changes determined at run time. We
should compare virtual functions to other mechanisms that provide the
same flexibility. When compared to a C alternative, virtual functions
are not inefficient.

Here is a C program that implements an equivalent of the vtable
mechanims of C++. I didn't bother with the 'this' pointer or the extra
function arguments.

I marked the C equivalent of this inefficiency with 'HERE' in the code.

#include <stdio.h>

/* the virtual functions of the interface */
typedef struct AnimalBehavior
{
int (*walk)(void *);
int (*talk)(void *);
}
AnimalBehavior;

/* the Animal struct with the virtual function table (behavior) */
typedef struct Animal
{
size_t leg_count;
struct AnimalBehavior const * behavior;
}
Animal;

/* the implementations of the virtual functions of Cat and Dog */
int CatWalk(void * data) { printf("cat walk\n"); return 0; }
int CatTalk(void * data) { printf("cat talk\n"); return 0; }
int DogWalk(void * data) { printf("dog walk\n"); return 0; }
int DogTalk(void * data) { printf("dog talk\n"); return 0; }

/* virtual function tables of the two types */
AnimalBehavior const catBehavior = { CatWalk, CatTalk };
AnimalBehavior const dogBehavior = { DogWalk, DogTalk };

/* a user of the animal interface */
void use(Animal * animal)
{
/* HERE */
/* equivalent inefficiency when using the virtual functions */
animal->behavior->walk(0);
animal->behavior->talk(0);
}

/* the constructors of the two types */
Animal makeCat()
{
Animal cat = { 4, &catBehavior };
return cat;
}

Animal makeDog()
{
Animal dog = { 4, &dogBehavior };
return dog;
}

int main()
{
Animal cat = makeCat();
Animal dog = makeDog();

use(&cat);
use(&dog);

return 0;
}

Ali

 

[Rolf Magnus]

You might want to clarify that third sentence. It almost sounds like
you meant that a virtual function will never be inlined anywhere in
the code if it is ever invoked through a reference or a pointer.

That's what I meant. However, I see that the might in some cases be able
to optimize the call.

Did you mean to say that it is unlikely that a compiler will be able
to inline a virtual function at a particular location if, at that
location, it is invoked through a reference or pointer?
Yes.

Also, I'm not sure what you meant by "three levels of indirection."

Well, if you call the virtual function on the object itself, the
function will just be called and good. If you call it through a pointer
or reference to the object, first that pointer must be dereferenced (a
reference is internally the same as a pointer) to get the vtable
pointer. Then that vtable pointer is dereferenced to get to the vtable.
And the vtable then contains a pointer to the function to be called. So
you have three pointers to be dereferenced for the function call, i.e.
three additional levels of indirection.
This of course assumes the classical vtable implementation of virtual
functions, but I've never heared about a C++ compiler that does it
differently.