Friday, December 28, 2018

c++ - 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 
class ebo_storage {
T item;
public:

constexpr ebo_storage() = default;

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


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

template
class ebo_storage<
T, Tag, std::enable_if_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
class compressed_pair : ebo_storage,
ebo_storage {
using first_t = ebo_storage;
using second_t = ebo_storage;
public:
T& first() { return first_t::get(); }
U& second() { return second_t::get(); }

// ...
};

template class tuple_;
template
class tuple_, Ts...> :
ebo_storage... {
// ...
};


template
using tuple = tuple_, 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 
class raw_container {
alignas(T) unsigned char space_[sizeof(T)];
public:

T& data() noexcept {
return reinterpret_cast(space_);
}
template
void construct(Args&&...args) {
::new(space_) T(std::forward(args)...);
}
void destruct() {
data().~T();
}

};

template
struct list_node : public raw_container {
std::atomic 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::space_, and sizeof(std::atomic) - 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 atop list_node::next_.




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



template 
struct alignas(T) raw_ebo_storage_base {
unsigned char space_[sizeof(T)];
};

template
struct alignas(T) raw_ebo_storage_base<
T, std::enable_if_t::value>

> {};

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

T& data() noexcept {
return *static_cast(static_cast(

static_cast*>(this)
));
}
};


which has the desired effects:



template 
struct alignas(T) empty {};

static_assert(std::is_empty>>::value, "Good!");
static_assert(std::is_empty>>::value, "Good!");
template
struct foo : raw_ebo_storage> { T c; };
static_assert(sizeof(foo) == 1, "Good!");
static_assert(sizeof(foo) == 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 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> { int i; };
static_assert(sizeof(A) == sizeof(int), "");

A a;
a.value = 42;
::new(&a.get()) empty{};
static_assert(sizeof(empty) > 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?

No comments:

Post a Comment

plot explanation - Why did Peaches&#39; mom hang on the tree? - Movies &amp; TV

In the middle of the movie Ice Age: Continental Drift Peaches' mom asked Peaches to go to sleep. Then, she hung on the tree. This parti...