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

79

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

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, чтобы не тратить пространство памяти для представления содержащегося объекта?

Кейси
источник
@Columbo Если тип контейнера является производным от содержащегося в нем типа, создание / уничтожение объекта-контейнера обязательно создает / уничтожает вложенный подобъект. Для строительства это означает, что вы либо теряете возможность предварительно выделять объекты-контейнеры, либо должны отложить их создание до тех пор, пока вы не будете готовы построить контейнер. Ничего страшного, он просто добавляет еще одну вещь для отслеживания - выделенные, но еще не созданные объекты-контейнеры. Однако уничтожение объекта-контейнера с мертвым подобъектом контейнера - более сложная проблема - как избежать деструктора базового класса?
Кейси
Ах, извините меня. Забыл, что отсроченное строительство / разрушение невозможно, и неявный вызов деструктора.
Columbo
`template <typename T> struct alignas (T) raw_ebo_storage_base <T, std :: enable_if_t <std :: is_empty <T> :: value>>: T {}; ? With maybe more tests on T`, чтобы убедиться, что он построен пустым ... или какой-то способ убедиться, что вы можете построить Tбез строительства T, предполагая, что T::T()есть побочные эффекты. Может быть, класс черт для непустого конструирования / уничтожения, Tкоторый говорит, как создать безвозвратно T?
Якк - Адам Неврамонт
Еще одна мысль: должен ли класс хранилища ebo взять список типов, которые нельзя рассматривать как пустые, потому что адрес класса хранилища ebo будет перекрываться с ним, если это так?
Якк - Адам Неврамонт
1
При запуске вы атомарно извлекаете элемент из бесплатного списка, создаете его и атомарно помещаете в список отслеживания. При разрыве вы будете атомарно удалять из списка отслеживания, вызывать деструктор, а затем атомарно вставлять в свободный список. Значит, при вызовах конструктора и деструктора атомарный указатель не используется и может быть свободно изменен, верно? Если да, то возникает вопрос: можете ли вы поместить атомарный указатель в space_массив и безопасно использовать его, пока он не находится в свободном списке? Тогда space_не будет T, но некоторая оболочка вокруг T и атомарного указателя.
Speed8ump

Ответы:

2

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

  1. Вам нужна необработанная память и новое размещение. Для этого необходимо иметь хотя бы один доступный байт , даже если вы хотите создать пустой объект путем размещения new.
  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(), вы золотой.

Румбурак
источник
Спасибо @Deduplicator за то, что рассказали мне о силе std::is_trivial:-)
Румбурак