Jak emulować EBO podczas korzystania z surowego magazynu?


79

Mam komponent, którego używam podczas implementowania typów ogólnych niskiego poziomu, które przechowują obiekt dowolnego typu (może być typem klasy lub nie), który może być pusty, aby skorzystać z pustej optymalizacji podstawowej :

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

Ostatnio majstrowałem przy strukturach danych bez blokad i potrzebuję węzłów, które opcjonalnie zawierają dane na żywo. Po przydzieleniu węzły działają przez cały okres istnienia struktury danych, ale zawarte w niej dane są aktywne tylko wtedy, gdy węzeł jest aktywny, a nie wtedy, gdy węzeł znajduje się na wolnej liście. Zaimplementowałem węzły przy użyciu surowego przechowywania i umieszczania 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_;
};

co jest w porządku i eleganckie, ale marnuje porcję pamięci wielkości wskaźnika na węzeł, gdy Tjest pusty: jeden bajt dla raw_storage<T>::space_i sizeof(std::atomic<list_node*>) - 1bajty wypełnienia dla wyrównania. Byłoby miło skorzystać z EBO i przydzielić nieużywaną jednobajtową reprezentację na raw_container<T>szczycie list_node::next_.

Moja najlepsza próba stworzenia raw_ebo_storage„ręcznego” 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)
    ));
  }
};

który daje pożądane efekty:

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

ale także pewne niepożądane efekty, które zakładam z powodu naruszenia ścisłego aliasingu (3.10 / 10), chociaż znaczenie „dostępu do przechowywanej wartości obiektu” jest dyskusyjne dla pustego typu:

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

To rozwiązanie może również powodować niezdefiniowane zachowanie podczas budowy. W pewnym momencie program musi skonstruować obiekt Containee w surowym magazynie z umieszczeniem 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, "");

Przypomnij sobie, że pomimo tego, że jest pusty, kompletny obiekt musi mieć niezerowy rozmiar. Innymi słowy, pusty kompletny obiekt ma reprezentację wartości, która składa się z jednego lub więcej bajtów wypełniających.newkonstruuje kompletne obiekty, więc zgodna implementacja może ustawić te bajty wypełniające na dowolne wartości podczas konstruowania zamiast pozostawiać pamięć nietkniętą, jak w przypadku konstruowania pustego podstawowego podobiektu. Byłoby to oczywiście katastrofalne, gdyby te bajty wypełniające nakładały się na inne żywe obiekty.

Zatem pytanie brzmi, czy możliwe jest utworzenie klasy kontenera zgodnej ze standardami, która używa surowej pamięci / opóźnionej inicjalizacji dla zawartego obiektu i wykorzystuje EBO, aby uniknąć marnowania miejsca w pamięci na reprezentację zawartego obiektu?


@Columbo Jeśli typ kontenera pochodzi z typu zawartego, skonstruowanie / zniszczenie obiektu kontenera musi koniecznie skonstruować / zniszczyć zawarty podobiekt. W przypadku konstrukcji oznacza to, że tracisz możliwość wstępnego przydzielania obiektów kontenerów lub musisz opóźniać ich budowę, aż będziesz gotowy do skonstruowania kontenera. Nic wielkiego, po prostu dodaje kolejną rzecz do śledzenia - przydzielone, ale jeszcze nie zbudowane obiekty kontenerów. Zniszczenie obiektu kontenera z martwym podobiektem zawiera jednak trudniejszy problem - jak uniknąć destruktora klasy bazowej?
Casey

Ach, przepraszam. Zapomniałem, że opóźniona budowa / zniszczenie nie jest możliwa w ten sposób i niejawne wywołanie destruktora.
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 Aby upewnić się, że jest skonstruowany próżniowo ... lub w jakiś sposób, aby zapewnić, że możesz konstruować Tbez konstruowania T, zakładając, że T::T()ma skutki uboczne. Może klasa cech dla budowanych / niszczonych w sposób nieuzasadnionyT która mówi, jak bezmyślnie skonstruować T?
Yakk - Adam Nevraumont

Inna myśl: czy klasa pamięci ebo przyjmie listę typów, których nie wolno traktować jako pustych, ponieważ adres klasy pamięci ebo będzie się z nią nakładał, jeśli tak jest?
Yakk - Adam Nevraumont

1
Podczas wywoływania możesz atomowo pobrać element z bezpłatnej listy, skonstruować go i atomowo umieścić na liście śledzenia. Po rozerwaniu będziesz atomowo usuwać z listy śledzenia, wywoływać destruktor, a następnie atomowo wstawiać do listy wolnej. Więc przy wywołaniach konstruktora i destruktora atomowy wskaźnik nie jest używany i można go dowolnie modyfikować, prawda? Jeśli tak, pytanie będzie brzmiało: czy możesz umieścić wskaźnik atomowy w space_tablicy i bezpiecznie z niego korzystać, gdy nie jest on skonstruowany na liście wolnej? Wtedy space_nie będzie zawierał T, ale trochę opakowania wokół T i wskaźnika atomowego.
Speed8ump

Odpowiedzi:


2

Myślę, że sam udzieliłeś odpowiedzi w swoich różnych obserwacjach:

  1. Chcesz czystej pamięci i nowego miejsca. Wymaga to co najmniej jednego dostępnego bajtu , nawet jeśli chcesz skonstruować pusty obiekt poprzez umieszczenie nowego.
  2. Potrzebujesz zerowego narzutu na przechowywanie pustych obiektów.

Wymagania te są sprzeczne. Odpowiedź brzmi więc nie , to nie jest możliwe.

Możesz jednak nieco bardziej zmienić swoje wymagania, wymagając zerowego narzutu tylko dla pustych, trywialnych typów.

Możesz zdefiniować nową cechę klasową, np

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

Wtedy się specjalizujesz

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

Następnie użyj tego w ten sposób:

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

Oczywiście nadal masz

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

Ale to normalne w przypadku 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");

Ale tak długo, jak zawsze używać constructi destructa nie umieszczenie na nowy &data(), jesteś złoty.


Dzięki @Deduplicator za uświadomienie mi potęgi std::is_trivial:-)
Rumburak
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.