How to emulate EBO when using raw storage?

I have a component I use when implementing low-level generic types that store an object of arbitrary type (may or may not be a class type) which may be empty to take advantage of the empty base optimization:

template <typename T, unsigned Tag = 0, typename = void>
class ebo_storage {
  T item;
public:
  constexpr ebo_storage() = default;

  template <
    typename U,
    typename = std::enable_if_t<
      !std::is_same<ebo_storage, std::decay_t<U>>::value
    >
  > constexpr ebo_storage(U&& u)
    noexcept(std::is_nothrow_constructible<T,U>::value) :
    item(std::forward<U>(u)) {}

  T& get() & noexcept { return item; }
  constexpr const T& get() const& noexcept { return item; }
  T&& get() && noexcept { return std::move(item); }
};

template <typename T, unsigned Tag>
class ebo_storage<
  T, Tag, std::enable_if_t<std::is_class<T>::value>
> : private T {
public:
  using T::T;

  constexpr ebo_storage() = default;
  constexpr ebo_storage(const T& t) : T(t) {}
  constexpr ebo_storage(T&& t) : T(std::move(t)) {}

  T& get() & noexcept { return *this; }
  constexpr const T& get() const& noexcept { return *this; }
  T&& get() && noexcept { return std::move(*this); }
};

template <typename T, typename U>
class compressed_pair : ebo_storage<T, 0>,
                        ebo_storage<U, 1> {
  using first_t = ebo_storage<T, 0>;
  using second_t = ebo_storage<U, 1>;
public:
  T& first() { return first_t::get(); }
  U& second() { return second_t::get(); }
  // ...
};

template <typename, typename...> class tuple_;
template <std::size_t...Is, typename...Ts>
class tuple_<std::index_sequence<Is...>, Ts...> :
  ebo_storage<Ts, Is>... {
  // ...
};

template <typename...Ts>
using tuple = tuple_<std::index_sequence_for<Ts...>, Ts...>;

Lately I've been messing about with lock-free data structures and I need nodes that optionally contain a live datum. Once allocated, nodes live for the lifetime of the data structure but the contained datum is only alive while the node is active and not while the node sits in a free list. I implemented the nodes using raw storage and placement new:

template <typename T>
class raw_container {
  alignas(T) unsigned char space_[sizeof(T)];
public:
  T& data() noexcept {
    return reinterpret_cast<T&>(space_);
  }
  template <typename...Args>
  void construct(Args&&...args) {
    ::new(space_) T(std::forward<Args>(args)...);
  }
  void destruct() {
    data().~T();
  }
};

template <typename T>
struct list_node : public raw_container<T> {
  std::atomic<list_node*> next_;
};

which is all fine and dandy, but wastes a pointer-sized chunk of memory per node when T is empty: one byte for raw_storage<T>::space_, and sizeof(std::atomic<list_node*>) - 1 bytes of padding for alignment. It would be nice to take advantage of EBO and allocate the unused single-byte representation of raw_container<T> atop list_node::next_.

My best attempt at creating a raw_ebo_storage performs "manual" EBO:

template <typename T, typename = void>
struct alignas(T) raw_ebo_storage_base {
  unsigned char space_[sizeof(T)];
};

template <typename T>
struct alignas(T) raw_ebo_storage_base<
  T, std::enable_if_t<std::is_empty<T>::value>
> {};

template <typename T>
class raw_ebo_storage : private raw_ebo_storage_base<T> {
public:
  static_assert(std::is_standard_layout<raw_ebo_storage_base<T>>::value, "");
  static_assert(alignof(raw_ebo_storage_base<T>) % alignof(T) == 0, "");

  T& data() noexcept {
    return *static_cast<T*>(static_cast<void*>(
      static_cast<raw_ebo_storage_base<T>*>(this)
    ));
  }
};

which has the desired effects:

template <typename T>
struct alignas(T) empty {};
static_assert(std::is_empty<raw_ebo_storage<empty<char>>>::value, "Good!");
static_assert(std::is_empty<raw_ebo_storage<empty<double>>>::value, "Good!");
template <typename T>
struct foo : raw_ebo_storage<empty<T>> { T c; };
static_assert(sizeof(foo<char>) == 1, "Good!");
static_assert(sizeof(foo<double>) == sizeof(double), "Good!");

but also some undesirable effects, I assume due to violation of strict aliasing (3.10/10) although the meaning of "access the stored value of an object" is debatable for an empty type:

struct bar : raw_ebo_storage<empty<char>> { empty<char> e; };
static_assert(sizeof(bar) == 2, "NOT good: bar::e and bar::raw_ebo_storage::data() "
                                "are distinct objects of the same type with the "
                                "same address.");

This solution also potential for undefined behavior upon construction. At some point the program must construct the containee object within the raw storage with placement new:

struct A : raw_ebo_storage<empty<char>> { int i; };
static_assert(sizeof(A) == sizeof(int), "");
A a;
a.value = 42;
::new(&a.get()) empty<char>{};
static_assert(sizeof(empty<char>) > 0, "");

Recall that despite being empty, a complete object necessarily has non-zero size. In other words, an empty complete object has a value representation that consists of one or more padding bytes. new constructs complete objects, so a conforming implementation could set those padding bytes to arbitrary values at construction instead of leaving memory untouched as would be the case for constructing an empty base subobject. This would of course be catastrophic if those padding bytes overlay other live objects.

So the question is, is it possible to create a standard-compliant container class that uses raw storage/delayed initialization for the contained object and takes advantage of EBO to avoid wasting memory space for the representation of the contained object?

Solution 1:

I think you gave the answer yourself in your various observations:

You want raw memory and placement new. This requires to have at least one byte available, even if you want to construct an empty object via placement new.
You want zero bytes overhead for storing any empty objects.

These requirements are self-contradicting. The answer therefore is No, that is not possible.

You could change your requirements a bit more, though, by requiring the zero byte overhead only for empty, trivial types.

You could define a new class trait, e.g.

template <typename T>
struct constructor_and_destructor_are_empty : std::false_type
{
};

Then you specialize

template <typename T, typename = void>
class raw_container;

template <typename T>
class raw_container<
    T,
    std::enable_if_t<
        std::is_empty<T>::value and
        std::is_trivial<T>::value>>
{
public:
  T& data() noexcept
  {
    return reinterpret_cast<T&>(*this);
  }
  void construct()
  {
    // do nothing
  }
  void destruct()
  {
    // do nothing
  }
};

template <typename T>
struct list_node : public raw_container<T>
{
  std::atomic<list_node*> next_;
};

Then use it like this:

using node = list_node<empty<char>>;
static_assert(sizeof(node) == sizeof(std::atomic<node*>), "Good");

Of course, you still have

struct bar : raw_container<empty<char>> { empty<char> e; };
static_assert(sizeof(bar) == 1, "Yes, two objects sharing an address");

But that is normal for EBO:

struct ebo1 : empty<char>, empty<usigned char> {};
static_assert(sizeof(ebo1) == 1, "Two object in one place");
struct ebo2 : empty<char> { char c; };
static_assert(sizeof(ebo2) == 1, "Two object in one place");

But as long as you always use construct and destruct and no placement new on &data(), you're golden.

How to emulate EBO when using raw storage?

Solution 1:

Related

Recent Posts