Как эмулировать EBO при использовании сырого хранилища?

У меня есть компонент, который я использую при реализации универсальных типов низкого уровня, в которых хранится объект произвольного типа (может быть, а может и не быть типом класса), который может быть пустым, чтобы воспользоваться преимуществами оптимизация пустой базы :

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...>;

В последнее время я бездельничал со структурами данных без блокировки, и мне нужны узлы, которые по выбору содержат оперативные данные. После распределения узлы живут в течение всего жизненного цикла структуры данных, но содержащиеся данные остаются живыми, только когда узел активен, а не в то время, когда узел находится в свободном списке. Я реализовал узлы, используя сырое хранилище и размещение 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_;
};

, что хорошо и прекрасно, но тратит часть памяти размером с указатель на узел, когда T пусто: один байт для raw_storage<T>::space_ и sizeof(std::atomic<list_node*>) - 1 байты заполнения для выравнивание. Было бы неплохо воспользоваться преимуществами EBO и выделить неиспользуемое однобайтовое представление raw_container<T> поверх list_node::next_

Моя лучшая попытка создать raw_ebo_storage - выполнить 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)
    ));
  }
};

который имеет желаемый эффект:

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!");

, но и некоторые нежелательные эффекты, я предполагаю, что из-за нарушение строгой ступенчатости (3,10 /10), хотя смысл «доступ к сохраненному значению объекта» спорен для пустого типа:

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.");

Это решение также может привести к неопределенному поведению при создании. В какой-то момент программа должна создать объект-носитель внутри исходного хранилища с размещением 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, "");

Напомним, что, несмотря на то что объект пустой, он обязательно имеет ненулевой размер. Другими словами, пустой завершенный объект имеет представление значения, которое состоит из одного или нескольких байтов заполнения. new создает завершенные объекты, поэтому соответствующая реализация может установить эти байты заполнения на произвольные значения при построении, а не оставлять память нетронутой, как это было бы в случае для построения пустого базового подобъекта. Это, конечно, будет катастрофическим, если эти байты заполнения перекрывают другие живые объекты.

Таким образом, вопрос в том, возможно ли создать класс-совместимый контейнерный класс, который использует необработанную память /отложенную инициализацию для содержащегося объекта , а использует преимущества EBO, чтобы не тратить пространство памяти для представления содержавшегося объекта?

79 голосов | спросил Casey 2 72014vEurope/Moscow11bEurope/MoscowSun, 02 Nov 2014 22:17:53 +0300 2014, 22:17:53

1 ответ


0

Я думаю, что вы дали ответ сами в своих различных наблюдениях:

  1. Вам нужна необработанная память и новое размещение. Для этого необходимо, чтобы был доступен хотя бы один байт , даже если вы хотите создать пустой объект путем размещения нового.
  2. Вы хотите ноль байтов для хранения любых пустых объектов.

Эти требования противоречат друг другу. Поэтому ответ Нет , это невозможно.

Однако вы могли бы немного изменить свои требования, потребовав служебных данных нулевого байта только для пустых тривиальных типов.

Вы можете определить новую черту класса, например

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

Тогда ты специализируешься

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_;
};

Тогда используйте это так:

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

Конечно, у вас все еще есть

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

Но это нормально для 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");

Но если вы всегда используете construct и destruct и нет нового размещения в &data(), вы великолепны.

ответил Rumburak 31 Jpm1000000pmSun, 31 Jan 2016 23:05:45 +030016 2016, 23:05:45

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132