Common base class breaks empty base class optimization for tuples

Question

gcc 4.7.1 does empty base class optimization for tuples, which I consider a really useful feature. However, there appears to be an unexpected limit to this:

#include <tuple>
#include <cstdint>
#include <type_traits>
class A { };
class B : public A { std::uint32_t v_; };
class C : public A { };
static_assert(sizeof(B) == 4,                "A has 32 bits.");
static_assert(std::is_empty<C>::value,       "B is empty.");
static_assert(sizeof(std::tuple<B, C>) == 4, "C should be 32 bits.");

In this case, the last assertion fails, as the tuple is in fact larger than 4 bytes. Is there a way to avoid this, without breaking the class hierarchy? Or do I have to implement my own pair implementation which optimizes for this case in some other way?

Maybe [this](http://flamingdangerzone.com/cxx11/2012/07/06/optimal-tuple-i.html) could help — Andy Prowl, Feb 25 '13 at 21:38
@AndyProwl, interesting to read, but I fail to see the immediate connection. It says both common implementations of tuples use EBCO, but makes no indication about the kind of EBCO failure I see here. — MvG, Feb 25 '13 at 21:47
That optimization cannot be applied in your case. In your tuple there are **two** `A` objects, and each one must have a different address. You don't need to add tuples to the code, you can add a fourth type: `struct D : B, C {};` and you will see that `sizeof(D) > sizeof(B)`. — David Rodríguez - dribeas, Feb 25 '13 at 21:52
I'm not sure what this has to do with the empty base class optimization. `class C` still must have a size of at least 1 whether or not it derives from `class A` and whether or not `class A` is 'optimized away' in `class C`. `std::tuple<>` doesn't use inheritance to package the parametrized types into a tuple, so `std::tuple` won't add an opportunity for EBCO to occur. So I'm not sure what "gcc 4.7.1 does empty base class optimization for tuples" means. — Michael Burr, Feb 26 '13 at 01:37
@MichaelBurr: For *empty* parameter types, libstdc++ as shipped with [gcc *will* use inheritance](http://tinyurl.com/afdf2lf) to package things into the tuple. One practical application is that e.g. a [`unique_ptr` won't require more space than a classical dumb pointer](http://stackoverflow.com/q/13460395/1468366). Both [the document pointed out by Andy Prowl](http://flamingdangerzone.com/cxx11/2012/07/06/optimal-tuple-i.html) and [this one here](http://mitchnull.blogspot.de/2012/06/c11-tuple-implementation-details-part-1.html) will explain some of the details. — MvG, Feb 26 '13 at 06:15

score 6 · Accepted Answer · answered Feb 25 '13 at 21:59

The reason that an empty object must take some space is that two different objects must have different addresses. The exception to that is that the base subobject of a derived type can have the same address as the derived complete object (if the first non-static member of the derived type is not of the same type as the base ^[*]. The empty base optimization uses that to remove the additional space that is added to an empty base arbitrarily to ensure that sizeof x!=0 for any complete object.

In your case, the tuple is holding two A subobjects, one is the base of C the other is the base of B, but they are different and as such they must have different addresses. None of those two objects is the base subobject of the other, so they cannot have the same address. You don't even need to use std::tuple to see this effect, just create another type:

struct D : B, C {};

The size of D will be strictly greater than the size of both B and C. To check that there are in fact two A subobjects, you can try to upcast to a pointer to A and the compiler will gladly spit some ambiguity error in your direction.

^[*] The standard explicitly forbids this case also, for the same reason:

struct A {};
struct B : A { A a; };

Again, in this case in each complete object of type B, there are two A objects, and they must have different addresses.

Howard Hinnant · Answer 2 · 2013-02-26T00:57:05.017

2

This optimization can be tricky to pull off, as you can easily see with your experiment. I find this optimization most useful when the tuple is a data member of another class (especially if I anticipate putting that class in a container). Are there other data members that you can bundle in this tuple without exposing that fact? For example:

class D
{
    std::tuple<B, int, C, int> data_;
public:
    B& get_B() {return std::get<0>(data_);}
    C& get_C() {return std::get<2>(data_);}
    int& get_size() {return std::get<1>(data_);}
    int& get_age() {return std::get<3>(data_);}
};

For me, and this is by no means guaranteed, std::tuple<B, int, C, int> is only 12 bytes, and so C is getting optimized away.

edited Feb 26 '13 at 00:57

answered Feb 25 '13 at 21:57

Howard Hinnant

206,506
52
449
577

Unfortunately not an option in my case, but useful to know in general. In my case, I dropped the inheritance from `A`, as it wasn't absolutely necessary in this specific case. Other cases may require other approaches, yours among them. – MvG Feb 25 '13 at 22:07
1

@MvG: Inheritance is one of the most abused constructs. If it is not necessary, just *don't* use it. – David Rodríguez - dribeas Feb 25 '13 at 22:48
@DavidRodríguez-dribeas: in my case, the common ancestor was a simple tagging type. I had intended it as a means to allow templated operators to apply to all of my classes but no other classes. I guess I'll implement a separate predicate template instead. If C++ had *concepts,* I'd probably be less tempted to (ab)use inheritance for this kind of thing. But I'll remember this lesson anyway. – MvG Feb 26 '13 at 06:22
@MvG: That is the reason that `boost::noncopyable` was not added to the standard. While it is *free* in many contexts, there are constructs in which there is a cost, in particular in the presence of multiple inheritance under some specific cases, including the one in this question :) – David Rodríguez - dribeas Feb 26 '13 at 14:00

Common base class breaks empty base class optimization for tuples

2 Answers2

Linked