Empty Data Member Optimization: would it be possible?

Question

In C++, most of the optimizations are derived from the as-if rule. That is, as long as the program behaves as-if no optimization had taken place, then they are valid.

The Empty Base Optimization is one such trick: in some conditions, if the base class is empty (does not have any non-static data member), then the compiler may elide its memory representation.

Apparently it seems that the standard forbids this optimization on data members, that is even if a data member is empty, it must still take at least one byte worth of place: from n3225, [class]

4 - Complete objects and member subobjects of class type shall have nonzero size.

Note: this leads to the use of private inheritance for Policy Design in order to have EBO kick in when appropriate

I was wondering if, using the as-if rule, one could still be able to perform this optimization.

---

edit: following a number of answers and comments, and to make it clearer what I am wondering about.

First, let me give an example:

struct Empty {};

struct Foo { Empty e; int i; };

My question is, why is sizeof(Foo) != sizeof(int) ? In particular, unless you specify some packing, chances are due to alignment issues that Foo will be twice the size of int, which seems ridiculously inflated.

Note: my question is not why is sizeof(Foo) != 0, this is not actually required by EBO either

According to C++, it is because no sub-object may have a zero size. However a base is authorized to have a zero size (EBO) therefore:

struct Bar: Empty { int i; };

is likely (thanks to EBO) to obey sizeof(Bar) == sizeof(int).

Steve Jessop seems to be of an opinion that it is so that no two sub-objects would have the same address. I thought about it, however it doesn't actually prevent the optimization in most cases:

If you have "unused" memory, then it is trivial:

struct UnusedPadding { Empty e; Empty f; double d; int i; };
// chances are that the layout will leave some memory after int

But in fact, it's even "worse" than that, because Empty space is never written to (you'd better not if EBO kicks in...) and therefore you could actually place it at an occupied place that is not the address of another object:

struct Virtual { virtual ~Virtual() {} Empty e; Empty f; int i; };
// most compilers will reserve some space for a virtual pointer!

Or, even in our original case:

struct Foo { Empty e; int i; }; // deja vu!

One could have (char*)foo.e == (char*)foo.i + 1 if all we wanted were different address.

Answer 1

It is coming to c++20 with the [[no_unique_address]] attribute.

The proposal P0840r2 has been accepted into the draft standard. It has this example:

template<typename Key, typename Value, typename Hash, typename Pred, typename Allocator>
class hash_map {
  [[no_unique_address]] Hash hasher;
  [[no_unique_address]] Pred pred;
  [[no_unique_address]] Allocator alloc;
  Bucket *buckets;
  // ...
public:
  // ...
};

Answer 2

Under the as-if rule:

struct A {
    EmptyThing x;
    int y;
};

A a;
assert((void*)&(a.x) != (void*)&(a.y));

The assert must not be triggered. So I don't see any benefit in secretly making x have size 0, when you'd just need to add padding to the structure anyway.

I suppose in theory a compiler could track whether pointers might be taken to the members, and make the optimization only if they definitely aren't. This would have limited use, since there'd be two different versions of the struct with different layouts: one for the optimized case and one for general code.

But for example if you create an instance of A on the stack, and do something with it that is entirely inlined (or otherwise visible to the optimizer), yes, parts of the struct could be completely omitted. This isn't specific to empty objects, though - an empty object is just a special case of an object whose storage isn't accessed, and therefore could in some situations never be allocated at all.

Answer 3

C++ for technical reasons mandates that empty classes should have non-zero size.
This is to enforce that distinct objects have distinct memory addresses. So compilers silently insert a byte into "empty" objects.
This constraint does not apply to base class parts of derived classes as they are not free-standing.

Answer 4

Because Empty is a POD-type, you can use memcpy to overwrite its "representation", so it better not share it with another C++ object or useful data.

Answer 5

Given struct Empty { }; consider what happens if sizeof(Empty) == 0. Generic code that allocates heap for Empty objects could easily behave differently, as - for example - a realloc(p, n * sizeof(T)), where T is Empty, is then equivalent to free(p). If sizeof(Empty) != 0 then things like memset/memcpy etc. would try to work on memory regions that weren't in use by the Empty objects. So, the compiler would need to stitch up things like sizeof(Empty) on the basis of the eventual usage of the value - that sounds close to impossible to me.

Separately, under current C++ rules the assurance that each member has a distinct address means you can use those addresses to encode some state about those fields - e.g. a textual field name, whether some member function of the field object should be visited etc.. If addresses suddenly coincide, any existing code reliant on these keys could break.