Is virtual methods overhead significant?

Question

I have somewhat complicated inheritance structure which is mainly there to avoid code-duplicating and to facilitate common interface for various classes. It relies on virtual and non-virtual inheritance and looks more or less like this:

class AbstractItem
{
   //bunch of abstract methods
};

class AbstractNode : virtual public AbstractItem
{
    //some more virtual abstract methods
};

class AbstractEdge : virtual public AbstractItem
{
    //yet some different virtual abstract methods
};

and then some "real" classes like this

class Item : virtual public AbstractItem
{
    //implements AbstractItem
};

class Node : public Item, public AbstractNode
{
    //implements AbstractNode
};

class Edge : public Item, public AbstractEdge
{
    //implemetns AbstractEdge
};

and this is packed into a graph model class so that:

class AbstractGraph
{
    virtual QList<AbstractNode*> nodes() const = 0;
    virtual QList<AbstractEdge*> edges() const = 0;
};

class GraphModel : public AbstractGraph
{
public:
    virtual QList<AbstractNode*> nodes() const override; //this converts m_Nodes to a list of AbstractNode*
    virtual QList<AbstractEdge*> edges() const override; //dtto

private:
    QList<Node*> m_Nodes;
    QList<Edge*> m_Edge;
};

The reason for this convoluted structure is that there are different classes implementing AbstractGraph such as sorting models, filtering and those come in different variants - some store their data just as the model shown and have their own sets of AbstractItem/Node/Edge derived classes, others are dynamic and rely on the data of underlying graph/model without data of their own. Example:

class FilterNode : public AbstractNode
{
    //access the data in the m_Item via AbstractItem interface and implements differently AbstractNode interface
private:
    AbstractItem *m_Item = nullptr; //this variable holds pointer to some real item with actual data such as the one from GraphModel
};

class GraphFilter : public AbstractGraph
{
    //implements the interface differently to the GraphModel
private:
    QList<FilterNode*> m_Nodes;
    AbstractGraph *m_Source = nullptr; //source graph...
};

I have second thoughts about this because it relies on (virtual)inheritance, relies on abstract methods called through base etc. Is the overhead from this all that significant?

The alternative would be either:

a) Copy-paste lots of code to avoid virtual methods and most of the inheritance but it would be code maintanance nightmare. Plus no common interfaces...

b) Template it all out somehow... this I am somewhat unsure about and I do not know whether it is even possible. I do use them at few places in this already to avoid code duplication.

So does it seem reasonable or like an overkill? I might add that in some cases I will call the methods directly (inside the models) bypassing the virtual calls but on the outside it will pretty much always called via the abstract base.

Answer 1

Trying to implement generic graph algorithms using dynamic polymorphism with C++ makes things

1. Unnecessary hard.
2. Unnecessary slow.

The virtual function overhead stands out more significantly the simpler the functions are. In the quoted interface you also do return containers from various functions. Even if these are COW container, there is some work involved and accessing the sequence casually may easily unshare (i.e., copy) the represetation.

In the somewhat distant past (roughly 1990 to 1996) I have experimented with a dynamic polymorphism based generic implementtion of graph algorithms and was struggling with various problems to make it work. When I read first about STL it turned out that most of the problems can be addressed via a similar abstraction (although one key idea was still missing: property maps; see the reference to BGL below for details).

I found it preferable to implement graph algorithms in terms of an STL-like abstraction. The algorithms are function template implemented in terms of specific concepts which are sort of like base classes except for two key differences:

1. There are no virtual function calls involved in the abstraction and functions can normally be inlined.
2. The types returned from functions only need to model an appropriate concept rather than having to be compatible via some form of inheritance to some specific interface.

Admittedly I'm biased because I wrote my diploma thesis on this topic. For an [independently develop] application of this approach have a look at the Boost Graph Library (BGL).

For some performance measurements comparing different function call approaches, have a look at the function call benchmarks. They are modelled after the performance measurements for function calls from the Performance TR.