Wie emuliere ich EBO bei Verwendung von Rohspeicher?

79

Ich habe eine Komponente, die ich verwende, wenn ich generische Typen auf niedriger Ebene implementiere, die ein Objekt eines beliebigen Typs speichern (kann ein Klassentyp sein oder nicht), das leer sein kann, um die Optimierung der leeren Basis zu nutzen :

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

In letzter Zeit habe ich mit sperrenfreien Datenstrukturen herumgespielt und brauche Knoten, die optional ein Live-Datum enthalten. Einmal zugewiesen, leben Knoten für die Lebensdauer der Datenstruktur, aber das enthaltene Datum lebt nur, während der Knoten aktiv ist und nicht, während sich der Knoten in einer freien Liste befindet. Ich habe die Knoten mithilfe von Rohspeicher und Platzierung implementiert 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_;
};

Das ist alles in Ordnung und gut, verschwendet aber einen zeigergroßen Speicherblock pro Knoten, wenn er Tleer ist: ein Byte für raw_storage<T>::space_und sizeof(std::atomic<list_node*>) - 1Byte Auffüllen für die Ausrichtung. Es wäre schön, EBO zu nutzen und die nicht verwendete Einzelbyte-Darstellung von raw_container<T>atop zuzuweisen list_node::next_.

Mein bester Versuch, ein raw_ebo_storage"manuelles" EBO zu erstellen :

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

welches die gewünschten Wirkungen hat:

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

aber auch einige unerwünschte Effekte, die ich aufgrund einer Verletzung des strengen Aliasing (3.10 / 10) annehme, obwohl die Bedeutung von "Zugriff auf den gespeicherten Wert eines Objekts" für einen leeren Typ umstritten ist:

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

Diese Lösung kann auch zu undefiniertem Verhalten beim Bau führen. Irgendwann muss das Programm das Containe-Objekt innerhalb des Rohspeichers mit Platzierung erstellen 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, "");

Denken Sie daran, dass ein vollständiges Objekt, obwohl es leer ist, notwendigerweise eine Größe ungleich Null hat. Mit anderen Worten, ein leeres vollständiges Objekt hat eine Wertdarstellung, die aus einem oder mehreren Füllbytes besteht. newKonstruiert vollständige Objekte, sodass eine konforme Implementierung diese Füllbytes bei der Erstellung auf beliebige Werte setzen kann, anstatt den Speicher unberührt zu lassen, wie dies beim Erstellen eines leeren Basis-Unterobjekts der Fall wäre. Dies wäre natürlich katastrophal, wenn diese Füllbytes andere lebende Objekte überlagern würden.

Die Frage ist also, ob es möglich ist, eine standardkonforme Containerklasse zu erstellen, die Rohspeicher / verzögerte Initialisierung für das enthaltene Objekt verwendet und EBO nutzt, um die Verschwendung von Speicherplatz für die Darstellung des enthaltenen Objekts zu vermeiden.

Casey
quelle
@Columbo Wenn der Containertyp vom enthaltenen Typ abgeleitet ist, wird beim Erstellen / Zerstören eines Containerobjekts notwendigerweise das enthaltene Unterobjekt erstellt / zerstört. Für den Bau bedeutet dies, dass Sie entweder die Fähigkeit verlieren, Containerobjekte vorab zuzuweisen, oder deren Bau verzögern müssen, bis Sie bereit sind, einen Container zu konstruieren. Keine große Sache, es fügt nur eine weitere Sache zum Verfolgen hinzu - zugewiesene, aber noch nicht konstruierte Containerobjekte. Das Zerstören eines Containerobjekts mit einem toten Unterobjekt ist jedoch ein schwierigeres Problem - wie vermeidet man den Destruktor der Basisklasse?
Casey
Ah, entschuldigen Sie mich dort. Ich habe vergessen, dass eine verzögerte Konstruktion / Zerstörung auf diese Weise nicht möglich ist, und den impliziten Destruktoraufruf.
Columbo
`template <typname 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`, um sicherzustellen, dass es leer gebaut ist ... oder um sicherzustellen, dass Sie Tohne Konstruktion konstruieren können T, vorausgesetzt, es T::T()hat Nebenwirkungen. Vielleicht eine Merkmalsklasse für nicht vakuumiert / zerstört T, die besagt, wie man eine vakuumiert konstruiert T?
Yakk - Adam Nevraumont
Ein anderer Gedanke: Hat die ebo-Speicherklasse eine Liste von Typen erstellt, die Sie nicht als leer behandeln dürfen, da sich die Adresse der ebo-Speicherklasse in diesem Fall überschneidet?
Yakk - Adam Nevraumont
1
Beim Aufrufen ziehen Sie ein Element atomar aus einer freien Liste, erstellen es und fügen es atomar in eine Verfolgungsliste ein. Beim Herunterfahren werden Sie atomar aus einer Tracking-Liste entfernt, einen Destruktor aufrufen und dann atomar in die freie Liste einfügen. Beim Konstruktor- und Destruktoraufruf wird der Atomzeiger also nicht verwendet und kann frei modifiziert werden, richtig? Wenn ja, lautet die Frage: Können Sie den Atomzeiger in das space_Array einfügen und sicher verwenden, solange er nicht in der freien Liste enthalten ist? Dann enthält space_es kein T, sondern einen Wrapper um T und den Atomzeiger.
Speed8ump

Antworten:

2

Ich denke, Sie haben die Antwort selbst in Ihren verschiedenen Beobachtungen gegeben:

  1. Sie möchten Rohspeicher und Platzierung neu. Dies setzt voraus, dass mindestens ein Byte verfügbar ist, auch wenn Sie ein leeres Objekt über die Platzierung new erstellen möchten.
  2. Sie möchten einen Overhead von null Byte zum Speichern leerer Objekte.

Diese Anforderungen widersprechen sich selbst. Die Antwort lautet daher Nein , das ist nicht möglich.

Sie können Ihre Anforderungen jedoch etwas weiter ändern, indem Sie den Null-Byte-Overhead nur für leere, triviale Typen benötigen.

Sie können ein neues Klassenmerkmal definieren, z

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

Dann spezialisieren Sie sich

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

Dann benutze es so:

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

Natürlich hast du noch

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

Aber das ist normal für 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");

Aber solange Sie immer verwenden constructund destructkeine Platzierung neu ist &data(), sind Sie golden.

Rumburak
quelle
Vielen Dank an @Deduplicator für die Aufmerksamkeit auf die Macht von std::is_trivial:-)
Rumburak