Avoiding the memory overhead by using virtual inheritance

Question

The following code aims at providing my library with reflection information about the base classes from which the user's classes derive:

template <class Base1_ = void, class Base2_ = void, class Base3_ = void,
          class Base4_ = void>
struct ManagedNode;

// For classes that do not derive
template <> struct ManagedNode<void, void, void, void> {
    using Base1 = void; using Base2 = void; using Base3 = void;
    using Base4 = void;
};
// To avoid inaccessible base
// See http://stackoverflow.com/q/34255802/2725810
struct Inter0: public ManagedNode<>{};

// For classes that derive from a single base class
template <class Base1_>
struct ManagedNode<Base1_, void, void, void> : public Inter0,
                                               public Base1_ {
    using Base1 = Base1_;
};
// To avoid inaccessible base
template <class Base1_>
struct Inter1: public ManagedNode<Base1_>{};

// For classes that derive from two base classes
template <class Base1_, class Base2_>
struct ManagedNode<Base1_, Base2_, void, void> : public Inter1<Base1_>,
                                                 public Base2_ {
    using Base2 = Base2_;
};

// We can continue in the same manner for 3 and 4 base classes

Here is an example user code:

struct A : public ManagedNode<> {
    int data1;
};

struct B : public ManagedNode<> {};

struct C : public ManagedNode<A, B> {};

int main() {
    C c;
    std::cout << sizeof(c) << std::endl;
    return 0;
}

This code produces the output of 12, which means that c contains the data1 member three times!

I considered using virtual inheritance to avoid this memory overhead. If I simply insert the word virtual before the word public for each inheritance, then I get a warning about the base class becoming inaccessible... If I put the word virtual in every such place besides the declaration of Inter0, then I get the output of 16 -- worse than before!

I would very much appreciate an explanation of what happens when I use virtual inheritance here.

EDIT: For completeness, here is the version with virtual inserted (the comment indicates which virtual needs to be removed for the code to compile):

template <class Base1_ = void, class Base2_ = void, class Base3_ = void,
          class Base4_ = void>
struct ManagedNode;

// For classes that do not derive
template <> struct ManagedNode<void, void, void, void> {
    using Base1 = void; using Base2 = void; using Base3 = void;
    using Base4 = void;
};
// To avoid inaccessible base
// See http://stackoverflow.com/q/34255802/2725810
struct Inter0: virtual public ManagedNode<>{}; // without the word virtual
                                               // in this line, the code compiles

// For classes that derive from a single base class
template <class Base1_>
struct ManagedNode<Base1_, void, void, void> : virtual public Inter0,
                                               virtual public Base1_ {
    using Base1 = Base1_;
};
// To avoid inaccessible base
template <class Base1_>
struct Inter1: virtual public ManagedNode<Base1_>{};

// For classes that derive from two base classes
template <class Base1_, class Base2_>
struct ManagedNode<Base1_, Base2_, void, void> : virtual public Inter1<Base1_>,
                                                 virtual public Base2_ {
    using Base2 = Base2_;
};

// Some user classes for testing the concept

struct A : public ManagedNode<> {
    int data1;
};

struct B : public ManagedNode<> {};

struct C : public ManagedNode<A, B> {};

int main() {
    C c;
    std::cout << sizeof(c) << std::endl;
    return 0;
}

Here is the output from the compiler:

temp.cpp: In instantiation of ‘struct ManagedNode<A, void, void, void>’:
temp.cpp:27:8:   required from ‘struct Inter1<A>’
temp.cpp:31:8:   required from ‘struct ManagedNode<A, B>’
temp.cpp:44:19:   required from here
temp.cpp:21:8: error: virtual base ‘ManagedNode<void, void, void, void>’ inaccessible in ‘ManagedNode<A, void, void, void>’ due to ambiguity [-Werror=extra]
 struct ManagedNode<Base1_, void, void, void> : virtual public Inter0,
        ^
temp.cpp: In instantiation of ‘struct Inter1<A>’:
temp.cpp:31:8:   required from ‘struct ManagedNode<A, B>’
temp.cpp:44:19:   required from here
temp.cpp:27:8: error: virtual base ‘ManagedNode<void, void, void, void>’ inaccessible in ‘Inter1<A>’ due to ambiguity [-Werror=extra]
 struct Inter1: virtual public ManagedNode<Base1_>{};
        ^
temp.cpp: In instantiation of ‘struct ManagedNode<A, B>’:
temp.cpp:44:19:   required from here
temp.cpp:31:8: error: virtual base ‘ManagedNode<void, void, void, void>’ inaccessible in ‘ManagedNode<A, B>’ due to ambiguity [-Werror=extra]
 struct ManagedNode<Base1_, Base2_, void, void> : virtual public Inter1<Base1_>,
        ^
temp.cpp:44:8: error: virtual base ‘ManagedNode<void, void, void, void>’ inaccessible in ‘C’ due to ambiguity [-Werror=extra]
 struct C : public ManagedNode<A, B> {};
    ^

Are you assembling your entire project from SO questions? I mean, there isn't a limit on questions, but 15 questions over a long weekend indicates that you should probably spend a bit more time researching and experimenting on your own. Good questions that are useful for the community usually come out at a lower rate. — Kerrek SB, Dec 13 '15 at 22:27
@KerrekSB You might notice that all the code is mine. My questions aim at clarifying non-trivial aspects of the language. In fact, I think that the code I come up with based on the understanding gained from the answers is a contribution to the community. — AlwaysLearning, Dec 13 '15 at 22:32
I appreciate that, but a lot of the information you seek is already on SO and elsewhere (e.g. here is [one example](https://stackoverflow.com/questions/11048045)), and you would surely discover a lot of that if you researched a bit more patiently. — Kerrek SB, Dec 13 '15 at 22:35
@KerrekSB Did you discover that post by search or you remembered the post from seeing it earlier? If it's the former, what keywords did you use in the search? I mean, you do not expect me to search through all the posts on multiple inheritance, do you? — AlwaysLearning, Dec 13 '15 at 22:40
Yes, in general we do expect that. Posting a new question should be the [absolute last resort](http://meta.stackoverflow.com/a/261593). (In this example, I think I searched for "size empty class base" or something like that. It might take a few tries and permutations of terms, but that's why I suggested patience.) — Kerrek SB, Dec 13 '15 at 22:41
You are exaggerating, don't you? To make it more evident, if I did not find it by searching on *multiple inheritance* (probably thousands of posts), would I proceed to look though all the posts on *inheritance* (probably tens of thousands)? — AlwaysLearning, Dec 13 '15 at 22:44
Unclear what you're asking. Please clarify what it is that you actually did with the `virtual` keyword and the actual errors that you got when you did it. **In your question.** — user207421, Dec 13 '15 at 22:50
In fact all higher level language features (higher than asm) are implemented by the compiler. And usually the higher features (inheritance, virtual methods) are meant to be user-friendly, not always memory efficient. As far I know the "virtual" keyword adds some extra logic and routing so simply don't care about it. — gusto2, Dec 13 '15 at 22:51
@GabrielVince I fail to see anything useful about your comment. — user207421, Dec 13 '15 at 22:54
@GabrielVince But I care about space. This is C++, the world of efficiency (of course, when it's not premature optimization, which it isn't in this case; these are search nodes of A* and there can be billions of those, so memory counts). — AlwaysLearning, Dec 13 '15 at 23:00
What happens when you just write `struct A : virtual public ManagedNode<> {`, and similar for B and C? Without all the `Inter0` stuff which I am not getting the point of at all. — user207421, Dec 13 '15 at 23:05
@EJP Same error: direct base ‘ManagedNode’ inaccessible in ‘ManagedNode’ due to ambiguity — AlwaysLearning, Dec 13 '15 at 23:13

Jarod42 · Answer 1 · 2015-12-13T23:11:27.350

2

which means that C contains the data1 member three times!

It is not this reason that C is bigger than expected.

The problem is that all your classes inherit from ManagedNode<> and so, as each object must have a unique combination of address and type, an offset is added in the final structure.

layout C:

- 0x00: ManagedNode<> // From Inter0
- 0x04: ManagedNode<> // From A
- 0x04: int           // From A
- 0x08: ManagedNode<> // From B

Note: ManagedNode<> is empty.

edited Dec 13 '15 at 23:11

answered Dec 13 '15 at 22:32

Jarod42

203,559
14
181
302

Isn't the whole purpose of virtual inheritance to make sure that each member of the base is inherited only once (i.e. through a unique path)? – AlwaysLearning Dec 13 '15 at 22:36
Do you mean to say that I don't have several `A` sub-objects in `C` even without the use of virtual inheritance? This is nightmare, I am totally confused. Where can I read about all this stuff in detail? – AlwaysLearning Dec 13 '15 at 22:50
@AlwaysLearning No, of course not. This poster doesn't appear to have read the question properly. – user207421 Dec 13 '15 at 22:51
How come `ManagedNode<>` is included several times, while `data1` isn't? Also, if this was the case, then the Empty Base-class Optimization would have to kick in (see http://stackoverflow.com/a/11049434/2725810) – AlwaysLearning Dec 13 '15 at 23:18
@AlwaysLearning: `A` and `B` inherit directly from `ManagedNode<>`, for `C` there are more indirections. There is a rule which disallow Empty Base-class optimization here: each `ManagedNode<>` should have different addresses. – Jarod42 Dec 13 '15 at 23:29
@Jarod42 Besides going into the Standard, is this topic covered in sufficient detail in any book or article? – AlwaysLearning Dec 13 '15 at 23:34
@Jarod42 I meant more broadly the topic of the memory layout for multiple inheritance, including the case of virtual inheritance and the case of empty or non-empty base class. – AlwaysLearning Dec 13 '15 at 23:49
@Jarod42 It's 2 AM here, so I will be better fit to look at this code tomorrow. But from the first look it looks like CRTP! I have been thinking for some time how CRTP might be relevant here: http://stackoverflow.com/q/34223547/2725810) – AlwaysLearning Dec 13 '15 at 23:55
[what-is-the-vtt-for-a-class](http://stackoverflow.com/questions/6258559/what-is-the-vtt-for-a-class) may interest you (no EBO though). – Jarod42 Dec 13 '15 at 23:56
@Jarod42 OK. I got too curious, so I looked at the code despite the late hour. Could you please shed some light on how the extra template parameter helps to avoid the shifting of addresses that you described? Actually, all of this would be a great supplement to your answer and would surely help future readers. – AlwaysLearning Dec 14 '15 at 00:02
You no longer have 3 `ManagedNode<>`, but `ManagedNode`, `ManagedNode` and `ManagedNode` which are not the same type, so can be at the same address with EBO. – Jarod42 Dec 14 '15 at 00:04
@Jarod42 Wow. I have a lot of food for thought and learning, but that must be tomorrow. Thank you so much! – AlwaysLearning Dec 14 '15 at 00:07
@Jarod42 The solution you offered almost solves the problem. There is still an ambiguity when accessing the base types. I have added two line in main(). Both lines result in a problem: ideone.com/X2hp4E – AlwaysLearning Dec 17 '15 at 10:41
You have indeed to hide parent baseX typedef, as in the following: http://ideone.com/YJNNG3 – Jarod42 Dec 17 '15 at 16:15
@Jarod42 But then there is no benefit in inheriting from `Inter`. There is no benefit from using CRTP (i.e. having the `Der` template parameter) either. In other words, the naive code I gave in my answer is the best solution... Is it? – AlwaysLearning Dec 18 '15 at 08:01
`CRTP` will allow EBO. Indeed, I don't see interest of `InterX`. If you have access to c++11, variadic template can be better than those `void`. – Jarod42 Dec 18 '15 at 09:30

score 0 · Answer 2 · answered Dec 17 '15 at 11:01

After much struggle (see the comments to Jarod42's answer), I came up with the following very naive solution. It has some duplication of code, but avoids all the hassle with ambiguity in the base classes:

// For classes that do not derive
template<> struct ManagedNode<void, void, void, void> {
    using Base1 = void;
};

// For classes that derive from a single base class
template <class Base1_>
struct ManagedNode<Base1_, void, void, void> : public Base1_ {
    using Base1 = Base1_;
    using Base2 = void;
};

// For classes that derive from two base classes
template <class Base1_, class Base2_>
struct ManagedNode<Base1_, Base2_, void, void>
    : public Base1_, public Base2_ {
    using Base1 = Base1_;
    using Base2 = Base2_;
    using Base3 = void;
};

Avoiding the memory overhead by using virtual inheritance

2 Answers2