vtable with virtual base class?

[Dave Johansen]

I've done some searching and haven't been able to an answer to this
question, but is a vtable (or any other sort of overhead) created/
added with using virtual inheritance to resolve the "diamond problem"
when there are no virtual functions?

For example, let's say that I have a setup like this

class base_data
{
static const int NUM_VALUES = 5;
....
protected:
int m_data[NUM_VALUES];
};

class data_reader : public virtual base_data
{
....
public:
data_reader &operator>>(int &value)
{
value = data[m_index];

m_index = (m_index + 1) % NUM_VALUES;

return *this;
}
....
protected:
int m_index;
};

class data_writer : public virtual base_data
{
....
public:
data_writer &operator<<(int value);
{
data[m_index] = value;

m_index = (m_index + 1) % NUM_VALUES;

return *this;
}
....
protected:
int m_index;
}

class data_reader_and_writer : public data_reader, public data_writer
{
....
};

I realize that the virtual inheritance used with data_reader/
data_writer allows data_reader_and_writer to have only a single
instance of the base_data class that is shared so the reading and
writing will happen from the same array (I realize that the read and
write indexes will be disjoint/independent in this implementation),
but is there anything else that's different about data_reader,
data_writer, or data_reader_and_writer (other than the single instance
of base_data, of course)? Anything else added to them? Or any sort of
performance penalty?

Thanks,
Dave

 

[James Kanze]

I've done some searching and haven't been able to an answer to
this question, but is a vtable (or any other sort of overhead)
created/ added with using virtual inheritance to resolve the
"diamond problem" when there are no virtual functions?

For example, let's say that I have a setup like this

class base_data
{
static const int NUM_VALUES = 5;
...
protected:
int m_data[NUM_VALUES];
};

class data_reader : public virtual base_data
{
...
public:
data_reader &operator>>(int &value)
{
value = data[m_index];

m_index = (m_index + 1) % NUM_VALUES;

return *this;
}
...
protected:
int m_index;
};

class data_writer : public virtual base_data
{
...
public:
data_writer &operator<<(int value);
{
data[m_index] = value;

m_index = (m_index + 1) % NUM_VALUES;

return *this;
}
...
protected:
int m_index;
}

class data_reader_and_writer : public data_reader, public data_writer
{
...
};

I realize that the virtual inheritance used with data_reader/
data_writer allows data_reader_and_writer to have only a
single instance of the base_data class that is shared so the
reading and writing will happen from the same array (I realize
that the read and write indexes will be disjoint/independent
in this implementation), but is there anything else that's
different about data_reader, data_writer, or
data_reader_and_writer (other than the single instance of
base_data, of course)? Anything else added to them? Or any
sort of performance penalty?

It depends on what you call a penalty. In a typical
implementation, each class will be laid out without considering
the virtual bases, then the virtual bases will be tacked onto
the end of the most derived class. So, for example, in your
case, if you have a data_reader object or a data_writer object,
it will be laid out:
data_reader::m_index
base_data::m_data
or
data_writer::m_index
base_data::m_data
, and a data_reader_and_writer will be laid out:
data_reader::m_index
data_writer::m_index
base_data::m_data
Note that the position of base_data::m_data in data_reader
varies depending on what the most derived class is. Which isn't
known to data_reader. The compiler must thus generate extra
code or data to find it dynamically: this may take the form of
an extra hidden pointer (in addition to the vptr) in the class
(which is initialized by the most derived class), or an
additional entry in the vtable, with the offset of the base
class. (Presumably, other implementations are also possible,
but these are the two I know of.)

Does this result in a "penalty"? Compared to what: if you don't
actually need virtual inheritance, then using it does have an
additional cost, although in most cases, it's probably
negligible. If you need it, I'd guess that most of the time,
the additional cost is less than the cost of the alternatives.

 

[Dave Johansen]

Thanks for the response and it answered exactly what I was looking
for. I agree that the penalty is small and "worth paying" to avoid the
duplicated code, when it's REALLY necessary and there's not a better
design to handle the problem.

Also, just for anyone else who may stumble along this thread. I found
this article ( http://www-plan.cs.colorado.edu/diwan/class-papers/mi.pdf
) and Section 7 actually discusses the logic behind the use of virtual
base classes to resolve the "diamond problem" and Section 7.1
discusses the methodology used to implement the virtual base classes
in multiple inheritance (which is the method that James had pointed
out). Also, I didn't even think about this, but it points outs that
"one can cast from a derived class to a virtual base class, but not
from a virtual base class to a derived class" and it explains the
reasoning as to why.

Thanks again for the help and the quick response,
Dave

I've done some searching and haven't been able to an answer to
this question, but is a vtable (or any other sort of overhead)
created/ added with using virtual inheritance to resolve the
"diamond problem" when there are no virtual functions?
For example, let's say that I have a setup like this
class base_data
{
  static const int NUM_VALUES = 5;
...
protected:
  int m_data[NUM_VALUES];
};
class data_reader : public virtual base_data
{
...
public:
  data_reader &operator>>(int &value)
  {
    value = data[m_index];

    m_index = (m_index + 1) % NUM_VALUES;

    return *this;
  }
...
protected:
  int m_index;
};
class data_writer : public virtual base_data
{
...
public:
  data_writer &operator<<(int value);
  {
    data[m_index] = value;

    m_index = (m_index + 1) % NUM_VALUES;

    return *this;
  }
...
protected:
  int m_index;
}

class data_reader_and_writer : public data_reader, public data_writer
{
...
};
I realize that the virtual inheritance used with data_reader/
data_writer allows data_reader_and_writer to have only a
single instance of the base_data class that is shared so the
reading and writing will happen from the same array (I realize
that the read and write indexes will be disjoint/independent
in this implementation), but is there anything else that's
different about data_reader, data_writer, or
data_reader_and_writer (other than the single instance of
base_data, of course)? Anything else added to them? Or any
sort of performance penalty?

It depends on what you call a penalty.  In a typical
implementation, each class will be laid out without considering
the virtual bases, then the virtual bases will be tacked onto
the end of the most derived class.  So, for example, in your
case, if you have a data_reader object or a data_writer object,
it will be laid out:
    data_reader::m_index
    base_data::m_data
or
    data_writer::m_index
    base_data::m_data
, and a data_reader_and_writer will be laid out:
    data_reader::m_index
    data_writer::m_index
    base_data::m_data
Note that the position of base_data::m_data in data_reader
varies depending on what the most derived class is.  Which isn't
known to data_reader.  The compiler must thus generate extra
code or data to find it dynamically: this may take the form of
an extra hidden pointer (in addition to the vptr) in the class
(which is initialized by the most derived class), or an
additional entry in the vtable, with the offset of the base
class.  (Presumably, other implementations are also possible,
but these are the two I know of.)

Does this result in a "penalty"?  Compared to what: if you don't
actually need virtual inheritance, then using it does have an
additional cost, although in most cases, it's probably
negligible.  If you need it, I'd guess that most of the time,
the additional cost is less than the cost of the alternatives.

--
James Kanze (GABI Software)             email:[email protected]
Conseils en informatique orientée objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

 

[Dave Johansen]

Sorry for the multiple posts, but here's a link to the previously
mentioned article that will probably be a little more permanent.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.8766

Dave

Thanks for the response and it answered exactly what I was looking
for. I agree that the penalty is small and "worth paying" to avoid the
duplicated code, when it's REALLY necessary and there's not a better
design to handle the problem.

Also, just for anyone else who may stumble along this thread. I found
this article (http://www-plan.cs.colorado.edu/diwan/class-papers/mi.pdf
) and Section 7 actually discusses the logic behind the use of virtual
base classes to resolve the "diamond problem" and Section 7.1
discusses the methodology used to implement the virtual base classes
in multiple inheritance (which is the method that James had pointed
out). Also, I didn't even think about this, but it points outs that
"one can cast from a derived class to a virtual base class, but not
from a virtual base class to a derived class" and it explains the
reasoning as to why.

Thanks again for the help and the quick response,
Dave

I've done some searching and haven't been able to an answer to
this question, but is a vtable (or any other sort of overhead)
created/ added with using virtual inheritance to resolve the
"diamond problem" when there are no virtual functions?
For example, let's say that I have a setup like this
class base_data
{
  static const int NUM_VALUES = 5;
...
protected:
  int m_data[NUM_VALUES];
};
class data_reader : public virtual base_data
{
...
public:
  data_reader &operator>>(int &value)
  {
    value = data[m_index];
    m_index = (m_index + 1) % NUM_VALUES;
    return *this;
  }
...
protected:
  int m_index;
};
class data_writer : public virtual base_data
{
...
public:
  data_writer &operator<<(int value);
  {
    data[m_index] = value;
    m_index = (m_index + 1) % NUM_VALUES;
    return *this;
  }
...
protected:
  int m_index;
}
class data_reader_and_writer : public data_reader, public data_writer
{
...
};
I realize that the virtual inheritance used with data_reader/
data_writer allows data_reader_and_writer to have only a
single instance of the base_data class that is shared so the
reading and writing will happen from the same array (I realize
that the read and write indexes will be disjoint/independent
in this implementation), but is there anything else that's
different about data_reader, data_writer, or
data_reader_and_writer (other than the single instance of
base_data, of course)? Anything else added to them? Or any
sort of performance penalty?

It depends on what you call a penalty.  In a typical
implementation, each class will be laid out without considering
the virtual bases, then the virtual bases will be tacked onto
the end of the most derived class.  So, for example, in your
case, if you have a data_reader object or a data_writer object,
it will be laid out:
    data_reader::m_index
    base_data::m_data
or
    data_writer::m_index
    base_data::m_data
, and a data_reader_and_writer will be laid out:
    data_reader::m_index
    data_writer::m_index
    base_data::m_data
Note that the position of base_data::m_data in data_reader
varies depending on what the most derived class is.  Which isn't
known to data_reader.  The compiler must thus generate extra
code or data to find it dynamically: this may take the form of
an extra hidden pointer (in addition to the vptr) in the class
(which is initialized by the most derived class), or an
additional entry in the vtable, with the offset of the base
class.  (Presumably, other implementations are also possible,
but these are the two I know of.)

Does this result in a "penalty"?  Compared to what: if you don't
actually need virtual inheritance, then using it does have an
additional cost, although in most cases, it's probably
negligible.  If you need it, I'd guess that most of the time,
the additional cost is less than the cost of the alternatives.

--
James Kanze (GABI Software)             email:[email protected]
Conseils en informatique orientée objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

 

[James Kanze]

Thanks for the response and it answered exactly what I was
looking for. I agree that the penalty is small and "worth
paying" to avoid the duplicated code, when it's REALLY
necessary and there's not a better design to handle the
problem.

I'm not sure what you mean by "really" necessary? Anytime
inheritance is being used to extend an interface, you should
probably use virtual inheritance. The cost is generally
negligeable, and virtual inheritance will be more robust with
regards to different client use.

In this regard, I'd suggest reading Barton and Nackman. They
discuss the various design trade-offs in detail.

Also, just for anyone else who may stumble along this thread.
I found this article
(http://www-plan.cs.colorado.edu/diwan/class-papers/mi.pdf)
and Section 7 actually discusses the logic behind the use of
virtual base classes to resolve the "diamond problem"

I couldn't find any mention of a "diamond problem" in it.
(I've found mention of a "diamond problem" is often a symptom
that the author really doesn't understand the issues that well.
The fact that you have a diamond in your inheritance graph is
not a problem; it is, in fact, perfectly normal.)

 

[Dave Johansen]

I'm not sure what you mean by "really" necessary?  Anytime
inheritance is being used to extend an interface, you should
probably use virtual inheritance.  The cost is generally
negligeable, and virtual inheritance will be more robust with
regards to different client use.

In this regard, I'd suggest reading Barton and Nackman.  They
discuss the various design trade-offs in detail.

I understand the logic behind recommending to just make all
inheritance virtual (similar to the recommendation of making all
destructors virtual), but I've never agreed either of those being a
good rule for general use.

Also, I realize that this is just one compiler and an extreme example,
but according to this post (
http://www.codesynthesis.com/~boris/blog/2008/04/17/virtual-inheritance-overhead-gcc/
) the cost is not all that negligible.

I  couldn't find any mention of a "diamond problem" in it.
(I've found mention of a "diamond problem" is often a symptom
that the author really doesn't understand the issues that well.
The fact that you have a diamond in your inheritance graph is
not a problem; it is, in fact, perfectly normal.)

He doesn't not use the term "diamond problem" but Section 7 explains
the issue exactly and describes the motivation for why C++ chose the
methodology that it did.

 

[Dave Johansen]

I agree 100% that it's a poor example because the 2 methods are very
different and that it is FAR from a thorough/effective analysis, but
it was the only thing that I could find that was even close to looking
at what using virtual inheritance did. If someone knows of a better
analysis, then I'd LOVE to see it.
Dave

 

[Dave Johansen]

I would also like to point out the the Visual Studio documentation
claims "Virtual inheritance provides significant size benefits when
compared with nonvirtual inheritance. However, it can introduce extra
processing overhead.", see http://msdn.microsoft.com/en-us/library/wcz57btd..aspx

I would still love to see a more detailed analysis to see what the
exact costs (memory and performance) are for using virtual
inheritance.

Dave

 

[James Kanze]

I understand the logic behind recommending to just make all
inheritance virtual (similar to the recommendation of making
all destructors virtual), but I've never agreed either of
those being a good rule for general use.

I don't understand the logic behind recommendation to just make
all inheritance virtual, and I didn't recommend it. I said that
when you define an interface which extends another interface,
you should use virtual inhertitance. In most other cases I've
encountered, such as mixins, it's obvious up front that you need
virtual inheritance, so you don't need a guideline whether to
use it or not.

And I'd still suggest you read Barton and Nackman; they treat
the issues in some detail, including the cost aspects.

Also, I realize that this is just one compiler and an extreme
example, but according to this post
(http://www.codesynthesis.com/~boris/blog/2008/04/17/virtual-inheritan...)
the cost is not all that negligible.

I couldn't deduce that from the article. There was a lot of
hand waving in it, but no concrete facts.

He doesn't not use the term "diamond problem" but Section 7
explains the issue exactly and describes the motivation for
why C++ chose the methodology that it did.

He doesn't use the term "diamond problem" because there isn't
any problem, except in people's imagination.

 

[Dave Johansen]

I don't understand the logic behind recommendation to just make
all inheritance virtual, and I didn't recommend it.  I said that
when you define an interface which extends another interface,
you should use virtual inhertitance.  In most other cases I've
encountered, such as mixins, it's obvious up front that you need
virtual inheritance, so you don't need a guideline whether to
use it or not.

I apologize. I guess I misunderstood the sentence "Anytime inheritance
is being used to extend an interface, you should probably use virtual
inheritance." to mean always using virtual inheritance, but now that I
re-read it, I understand what you meant.

And I'd still suggest you read Barton and Nackman; they treat
the issues in some detail, including the cost aspects.

I will definitely check it out.

I couldn't deduce that from the article.  There was a lot of
hand waving in it, but no concrete facts.

The article is definitely sparse on details/facts, but it's the best
example/analysis that I was able to find.

He doesn't use the term "diamond problem" because there isn't
any problem, except in people's imagination.

I agree that it's not technically a "problem" but just the way the
language is defined/behaves, but that doesn't mean that the term
"diamond problem" doesn't have merit (easily describes a situation
that may not be familiar to programmers not familiar with the details
of C++ multiple inheritance).

 

[Dave Johansen]

I would still love to see a more detailed analysis to see what the

So do it. <g>

You're right. I will do just that.

And a big thanks to everyone for all of the help/comments,
Dave

 

[James Kanze]

I agree that it's not technically a "problem" but just the way
the language is defined/behaves, but that doesn't mean that
the term "diamond problem" doesn't have merit (easily
describes a situation that may not be familiar to programmers
not familiar with the details of C++ multiple inheritance).

The word "problem" is loaded, and creates the wrong impression.
Diamond inheritance would be the descriptive term. But I'm not
sure that we even need a special name for it.