Asp Forum - vtable with virtual base class?

Dave Johansen

12/11/2008 4:57:00 AM

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

13 Answers

James Kanze

12/11/2008 9:36:00 AM

On Dec 11, 5:56 am, Dave Johansen <davejohan...@gmail.com> wrote:
> 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:james.kanze@gmail.com
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

12/11/2008 5:12:00 PM

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-pap...
) 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

On Dec 11, 2:36 am, James Kanze <james.ka...@gmail.com> wrote:
> On Dec 11, 5:56 am, Dave Johansen <davejohan...@gmail.com> wrote:
>
>
>
> > 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:james.ka...@gmail.com
> 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

12/11/2008 5:17:00 PM

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...

Dave

On Dec 11, 10:12 am, Dave Johansen <davejohan...@gmail.com> wrote:
> 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-pap...
> ) 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
>
> On Dec 11, 2:36 am, James Kanze <james.ka...@gmail.com> wrote:
>
> > On Dec 11, 5:56 am, Dave Johansen <davejohan...@gmail.com> wrote:
>
> > > 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:james.ka...@gmail.com
> > 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

12/12/2008 8:48:00 AM

On Dec 11, 6:12 pm, Dave Johansen <davejohan...@gmail.com> wrote:
> 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-pap...)
> 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.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

12/12/2008 5:35:00 PM

On Dec 12, 1:47 am, James Kanze <james.ka...@gmail.com> wrote:
> On Dec 11, 6:12 pm, Dave Johansen <davejohan...@gmail.com> wrote:
>
> > 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.

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-ove...
) the cost is not all that negligible.

>
> > Also, just for anyone else who may stumble along this thread.
> > I found this article
> > (http://www-plan.cs.colorado.edu/diwan/class-pap...)
> > 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.)

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.

Pete Becker

12/12/2008 5:59:00 PM

On 2008-12-12 12:35:12 -0500, Dave Johansen <davejohansen@gmail.com> said:

>
> 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-inher...
> rhead-gcc/
> ) the cost is not all that negligible.

That post is not particularly convincing, since it doesn't look at the
actual differences in generated code. There are TWO changes to the
hierarchy, ONE of which is removing virtual bases. The other is
removing multiple inheritance entirely, and that typically means fewer
vtables. A more careful analysis would tease these two apart, so that
you can see the effect of each separately.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Dave Johansen

12/12/2008 6:14:00 PM

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

On Dec 12, 10:59 am, Pete Becker <p...@versatilecoding.com> wrote:
> On 2008-12-12 12:35:12 -0500, Dave Johansen <davejohan...@gmail.com> said:
>
>
>
> > 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......
> > rhead-gcc/
> > ) the cost is not all that negligible.
>
> That post is not particularly convincing, since it doesn't look at the
> actual differences in generated code. There are TWO changes to the
> hierarchy, ONE of which is removing virtual bases. The other is
> removing multiple inheritance entirely, and that typically means fewer
> vtables. A more careful analysis would tease these two apart, so that
> you can see the effect of each separately.
>
> --
> Pete
> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> Standard C++ Library Extensions: a Tutorial and Reference
> (www.petebecker.com/tr1book)

Dave Johansen

12/12/2008 6:39:00 PM

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/wcz5...

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

On Dec 12, 10:59 am, Pete Becker <p...@versatilecoding.com> wrote:
> On 2008-12-12 12:35:12 -0500, Dave Johansen <davejohan...@gmail.com> said:
>
>
>
> > 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......
> > rhead-gcc/
> > ) the cost is not all that negligible.
>
> That post is not particularly convincing, since it doesn't look at the
> actual differences in generated code. There are TWO changes to the
> hierarchy, ONE of which is removing virtual bases. The other is
> removing multiple inheritance entirely, and that typically means fewer
> vtables. A more careful analysis would tease these two apart, so that
> you can see the effect of each separately.
>
> --
> Pete
> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> Standard C++ Library Extensions: a Tutorial and Reference
> (www.petebecker.com/tr1book)

Pete Becker

12/12/2008 6:58:00 PM

On 2008-12-12 13:38:53 -0500, Dave Johansen <davejohansen@gmail.com> said:

> 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/librar...
> .aspx

What they're saying is that if you use virtual bases instead of
non-virtual bases, the resulting objects will often be smaller. That's
trivially true: if you only have one copy of a virtual base object
you'll often end up smaller than if you have half a dozen, despite the
added overhead of finding that base object. The "processing overhead"
is typically one or two extra dereferences to get at data in the
virtual base object through a pointer to a derived type.

But all of that is irrelevant if virtual bases have the wrong semantics
for what you're doing. The decision whether a base should be virtual
depends on its role in the class hierarchy. That's a design decision,
not an optimization.

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

So do it. <g>

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

James Kanze

12/12/2008 7:02:00 PM

On Dec 12, 6:35 pm, Dave Johansen <davejohan...@gmail.com> wrote:
> On Dec 12, 1:47 am, James Kanze <james.ka...@gmail.com> wrote:
> > On Dec 11, 6:12 pm, Dave Johansen <davejohan...@gmail.com> wrote:

> > > 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.

> 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......)
> 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.

> > > Also, just for anyone else who may stumble along this thread.
> > > I found this article
> > > (http://www-plan.cs.colorado.edu/diwan/class-pap...)
> > > 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.)

> 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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

comp.lang.c++

vtable with virtual base class?

Dave Johansen

James Kanze

Dave Johansen

Dave Johansen

James Kanze

Dave Johansen

Pete Becker

Dave Johansen

Dave Johansen

Pete Becker

James Kanze

x Login to ForumsZone