Динамічний неоднорідний щільно упакований контейнер

Визначення 1. Однорідний контейнер – це контейнер, в якому зберігаються об'єкти суворо одного типу.
Визначення 2. Неоднорідний контейнер — це контейнер, в якому можуть зберігатися об'єкти різного типу.
Визначення 3. Статичний контейнер — це контейнер, склад якого повністю визначається на етапі компіляції.
Під складом в даному випадку розуміється кількість елементів та їх типи, але не самі значення цих елементів. Дійсно, бувають контейнери, у яких навіть значення елементів визначаються на етапі компіляції, але в даній моделі такі контейнери не розглядаються.
Визначення 4. Динамічний контейнер — це контейнер, склад якого частково або повністю визначається на етапі виконання.
За такої класифікації, очевидно, існують чотири види контейнерів:
  1. Статичні однорідні
    Зможете придумати приклад?Звичайний масив —
    int[n]
    .
  2. Статичні неоднорідні
    Приклади?Найбільш яскравий приклад такого контейнера — це кортеж. У мові C++ він реалізується класом
    std::tuple<...>
    .
  3. Динамічні однорідні
    Здогадалися?Правильно,
    std::vector < int>
    .
  4. Динамічні неоднорідні
    Ось про це вигляді контейнерів і піде мова в даній статті.


Зміст
  1. Динамічні неоднорідні контейнери
  2. Динамічний кортеж
  3. Зберігання даних
  4. Обробники
  5. Доступ до даних
  6. життя і безпеку винятків
  7. Інші проблеми
  8. Виміри продуктивності
  9. Посилання

Динамічні неоднорідні контейнери
Існує кілька технік отримання динамічного неоднорідного контейнера. Ось трійка, мабуть, найбільш поширених з них:
  1. Масив покажчиків на поліморфний клас
    Вибір трусабалбесабувалого оопэшника.
    struct base
    {
    virtual ~base() = default;
    ...
    };
    
    struct derived: base
    {
    ...
    };
    
    std::vector<std::unique_ptr<base>> v;

  2. Масив об'єднань
    Під об'єднанням може розумітися як мовна можливість
    union
    , так і бібліотечний клас типу
    boost::variant
    (C++17 з'явиться
    std::variant
    ).
  3. Масив довільних об'єктів з використанням стирання типу
    Наприклад,
    boost::any
    (C++17 з'явиться
    std::any
    ), в який можна покласти що завгодно.
У кожній з цих технік є свої переваги і недоліки, і ми їх обов'язково розглянемо.
А зараз настав час висвітлити пункт, який до цього моменту залишався в тіні, незважаючи на те, що він є частиною назви і суті) статті.
Визначення 5. Щільно упакований контейнер — це контейнер, елементи якого лежать в безперервній області пам'яті, і між ними немає пропусків (з точністю до вирівнювання).
Наприклад? Здогадайтеся
int[n]
,
std::vector < int>
,
std::tuple<...>
.
На жаль, не всякий щільно упакований контейнер є динамічним неоднорідним. А нам потрібен саме такий.
Але повернемося до переваг і недоліків перерахованих вище технік отримання динамічних неоднорідних контейнерів.

Масив покажчиків на поліморфний клас

Переваги:
  1. Відносна простота реалізації
    Спадкування, поліморфізм, всі справи. Ці речі (на щастя чи на жаль?) знає навіть новачок.
  2. Легко вводити нові сутності
    Не потрібно ніяких додаткових дій для того, щоб отримати можливість вставляти новий об'єкт в масив. Потрібно тільки створити нового спадкоємця базового класу.
    І не потрібно перекомпілювати код, що залежить від масиву покажчиків.
Недоліки:
  1. Залежність від ієрархії
    В масив можна скласти тільки об'єкти, успадковані від деякого базового класу.
  2. Надмірність коду
    Для кожного нового елемента потрібно створити новий клас в ієрархії. Тобто якщо я хочу складати в контейнер два типи чисел — цілі і плавучку, — то мені доведеться завести базовий клас "число" і два його відповідних спадкоємця.
  3. Нещільна упаковка
    У масиві лежать тільки покажчики, а самі об'єкти розкидані по пам'яті. Це, в загальному випадку, буде негативно впливати на роботу з кешем.

Масив об'єднань

Переваги:
  1. Незалежність від ієрархії
    В масив можна покласти будь-який тип, вказаний в об'єднанні.
  2. Об'єкти лежать в безперервній області пам'яті
    У масиві зберігається не дороговказ, а сам об'єкт.
Недоліки:
  1. Залежність від безлічі об'єктів, що входять в об'єднання
    При додаванні нового об'єкта в об'єднання потрібно перекомпілювати весь код, який явно залежить від нашого масиву об'єднань.
  2. Нещільна упаковка
    Так, об'єкти лежать в безперервній області пам'яті. Але нам хотілося б отримати щільну упаковку, а для цього необхідно, щоб між об'єктами не було порожнеч. А порожнечі можуть бути.
    Справа в тому, що розмір об'єднання дорівнює розміру найбільшого типу цього об'єднання. Наприклад, якщо в об'єднання входить два типи —
    X
    та
    char
    , причому
    sizeof(X) = 32
    , то кожний
    char
    буде займати 32 байта, хоча одного було б цілком достатньо.

Масив довільних об'єктів з використанням стирання типу

Переваги:
  1. Повна незалежність
    У будь-який момент в такий масив можна покласти будь-який тип, і не доведеться перекомпілювати нічого, що залежить від цього масиву.
Недоліки:
  1. Нещільна упаковка
    Як і у випадку з масивом покажчиків, об'єкти такого масиву розкидані по пам'яті (в загальному випадку це не так, тому що може використовуватися оптимізація малих об'єктів, але для досить великих об'єктів це завжди вірно).

Динамічний кортеж
Отже, жоден з перелічених вище підходів не передбачає щільною упакови. Тому потрібно розробити ще один підхід до створення динамічного неоднорідного контейнера, який, до всього іншого, забезпечить жадану щільну упаковку.
Для того, щоб це зробити, спочатку доведеться трохи краще розібратися з
any
. Робота з ним відбувається приблизно так:
int main ()
{
// Створення нової змінної з примірника довільного типу.
auto a = any(1);
assert(any_cast<int>(a) == 1);

// Доступ до значення.
any_cast<int>(a) = 42;
assert(any_cast<int>(a) == 42);

// Присвоєння значення нового типу в стару змінну.
a = std::string(u8"Привіт!");
assert(any_cast<std::string>(a) == std::string(u8"Привіт!"));
}

Як це працює?
АНе приймайте цей код занадто близько до серця, це схематична реалізація. За цією реалізацією слід звернутися до більш авторитетному джерелу.
#include <cassert>
#include <utility>

enum struct operation_t
{
clone,
destroy
};

using manager_t = void (*) (operation_t, const void *, void *&);

// Для кожного типу в момент його укладання в `any` створюється спеціальний обробник, який потім
// буде використовуватися для роботи з цим типом.
template < typename T>
void manage (operation_t todo, const void * source, void *& destination)
{
switch (todo)
{
case operation_t::clone:
{
destination = new T(*static_cast<const T *>(source));
break;
}
case operation_t::destroy:
{
assert(source == nullptr);
static_cast<T *>(destination)->~T();
break;
}
}
}

class any
{
public:
any ():
m_data(nullptr),
m_manager(nullptr)
{
}

any (const any & that):
m_manager(that.m_manager)
{
m_manager(operation_t::clone, that.m_data, this->m_data);
}

any & operator = (const any & that)
{
any(that).swap(*this);
return *this;
}

any (any && that):
m_data(that.m_data),
m_manager(that.m_manager)
{
that.m_manager = nullptr;
}

any & operator = (any && that)
{
any(std::move(that)).swap(*this);
return *this;
}

~any ()
{
clear();
}

// Тут відбувається те саме "стирання" типу.
// Тип об'єкта у цьому місці "забувається", і далі на етапі компіляції його дізнатися вже
// неможливо. Однак, завдяки збереженому обробникові, на етапі виконання буде
// відомо, як керувати "життям" об'єкта: його копіюванням і руйнуванням.
template < typename T>
any (T object):
m_data(new T(std::move(object))),
m_manager(&manage<T>)
{
}

template < typename T>
any & operator = (T && object)
{
any(std::forward<T>(object)).swap(*this);
return *this;
}

template < typename T>
friend const T & any_cast (const any & a);

template < typename T>
friend T & any_cast (any & a);

void clear ()
{
if (not empty())
{
m_manager(operation_t::destroy, nullptr, m_data);
m_manager = nullptr;
}
}

void swap (any & that)
{
std::swap(this->m_data, that.m_data);
std::swap(this->m_manager, that.m_manager);
}

bool empty () const
{
return m_manager == nullptr;
}

private:
void * m_data;
manager_t m_manager;
};

// Для того, щоб дістати значення, потрібно явно вказати його тип.
// Використання:
//
// `any_cast<int>(a) = 4;`
//
template < typename T>
const T & any_cast (const any & a)
{
return *static_cast<const T *>(a.m_data);
}

template < typename T>
T & any_cast (any & a)
{
return *static_cast<T *>(a.m_data);
}

Як ви вже зрозуміли, динамічний кортеж (ДК) буде розвитком ідеї з
any
. А саме:
  1. Як і у випадку з
    any
    , буде застосована техніка стирання типу: типи об'єктів будуть "забуватися", і для кожного об'єкта буде заведений "менеджер", який буде знати, як з цим об'єктом потрібно працювати.
  2. Самі об'єкти будуть покладені один за одним (з урахуванням вирівнювання) в безперервну область пам'яті.
Працювати він буде схожим на
any
:
// Створення початкового кортежу з довільного набору елементів.
auto t = dynamic_tuple(42, true, 'q');

// Індикація розміру.
assert(t.size() == 3);

// Доступ до елементів за індексом.
assert(t.get<int>(0) == 42);

...

// Додавання нових довільних елементів.
t.push_back(3.14);
t.push_back(std::string"qwe"));

...

// Модифікація наявних елементів.
t.get<int>(0) = 17;

Потрібно більше коду
Ну що ж, приступимо до найцікавішого.

Зберігання даних
Як випливає з визначення щільної упаковки, всі об'єкти зберігаються в єдиному безперервному шматку пам'яті. Це означає, що для кожного з них, крім обробників, потрібно зберігати його відступ від початку цього шматка пам'яті.
Відмінно, заведемо для цього спеціальну структурку:
struct object_info_t
{
std::size_t offset;
manager_t manage;
};

Далі, потрібно буде зберігати сам шматок пам'яті, його розмір, а також окремо потрібно буде пам'ятати сумарний обсяг, займаний об'єктами.
Отримуємо:
class dynamic_tuple
{
private:
using object_info_container_type = std::vector<object_info_t>;

... 

std::size_t m_capacity = 0;
std::unique_ptr<std::int8_t[]> m_data;

object_info_container_type m_objects;
std::size_t m_volume = 0;
};


Обробники
Поки що залишається невизначеним тип обробника
manager_t
.
Є два основних варіанти:
  1. Структура з "методами"
    Як ми вже знаємо
    any
    , для управління об'єктом, потрібно кілька операцій. У випадку з ДК це, як мінімум, копіювання, перенесення і руйнування. Для кожної з них потрібно завести поле в структурі:
    struct manager_t
    {
    using copier_type = void (*) (const void *, void *);
    using mover_type = void (*) (void *, void *);
    using destroyer_type = void (*) (void *);
    
    copier_type copy;
    mover_type move;
    destroyer_type destroy;
    };

  2. Вказівник на узагальнений обробник
    Можна зберігати тільки один покажчик на узагальнений обробник. В цьому випадку потрібно завести перерахування, що відповідає за вибір необхідної операції, а також привести до єдиного вигляду сигнатури всіх возмозных дій над об'єктом:
    enum struct operation_t
    {
    copy,
    move,
    destroy
    };
    
    using manager_t = void (*) (operation_t, const void *, void *);

Недолік першого варіанту в тому, що для кожної дії потрібно введення нового поля. Відповідно, пам'ять, зайнята обробниками буде роздуватися в разі додавання нових обробників.
Недолік другого варіанту в тому, що сигнатури різних обробників різні, тому доводиться підганяти всі обробники під єдину сигнатуру, при цьому, в засисимости від запитаної операції, деякі аргументи можуть залишатися непотрібними, а іноді — о, боги — навіть доводиться викликати
const_cast
.
Виведіть дітей і вагітних від екранівнасправді, є і третій варіант: поліморфні обробники-класи. Але цей варіант нещадно відмітається як тормознутый.
Відповідно, недоліки одного з варіантів — це переваги іншого.
За підсумками довгих роздумів і зважувань переваг і недоліків, недоліки першого варіанту переважують, і вибір падає на менше зло — узагальнений обробник.
template < typename T>
void copy (const void *, void *); // См. розділ "Час життя і безпеку винятків".

template < typename T>
void move (void * source, void * destination)
{
new (destination) T(std::move(*static_cast<T *>(source)));
}

template < typename T>
void destroy (void * object)
{
static_cast<T *>(object)->~T();
}

template < typename T>
void manage (operation_t todo, const void * source, void * destination)
{
switch (todo)
{
case operation_t::copy:
{
copy<T>(source, destination);
break;
}
case operation_t::move:
{
move<T>(const_cast<void *>(source), destination);
break;
}
case operation_t::destroy:
{
assert(source == nullptr);
destroy<T>(destination);
break;
}
}
}


Доступ до даних
найпростіше, що можна сказати про ДК.
Тип запитуваних даних відомий на етапі компіляції, індекс відомий на етапі виконання, тому інтерфейс доступу до об'єкта напрошується сам собою:
template < typename T>
T & get (size_type index)
{
return *static_cast<T *>(static_cast<void *>(data() + offset_of(index)));
}

size_type offset_of (size_type index) const
{
return m_objects[index].offset;
}

Також, для більшої ефективності (див. графіки продуктивності доступу в кінці статті) можна визначити доступ до об'єкта щодо відступу:
template < typename T>
const T & get_by_offset (size_type offset) const
{
return *static_cast<const T *>(static_cast<const void *>(data() + offset));
}

Ну й індикатори за аналогією зі стандартними контейнерами:
size_type size () const
{
return m_objects.size();
}

std::size_t capacity () const
{
return m_capacity;
}

bool empty () const
{
return m_objects.empty();
}

Єдине, про що потрібно сказати окремо — це особливий індикатор, що повідомляє обсяг контейнера.
Під обсягом розуміється сумарна кількість пам'яті, займаний об'єктами, що перебувають у ДК.
std::size_t volume () const
{
return m_volume;
}


життя і безпеку винятків
Вкрай важливі завдання — спостереження за часом життя об'єктів і забезпечення безпеки винятків.
Оскільки об'єкти конструюються "вручну" за допомогою розміщує
new
, то вони, природно, і руйнуються "вручну" — явним викликом деструктора.
Це створює певні складнощі з копіюванням і перенесенням об'єктів при переаллокации. Тому доводиться реалізовувати відносно складні конструкції для копіювання і перенесення:
template < typename ForwardIterator>
void move (ForwardIterator first, ForwardIterator last, std::int8_t * source, std::int8_t * destination)
{
for (auto current = first; current != last; ++current)
{
try
{
// Пробуємо перенести всі об'єкти на нове місце.
current->manage(operation_t::move,
source + current->offset, destination + current->offset);
}
catch (...)
{
// Якщо не вийшло, то знищуємо те, що вже було перенесено.
destroy(first, current, destination);
throw;
}
}
destroy(first, last, source);
}

template < typename ForwardIterator>
void copy (ForwardIterator first, ForwardIterator last, const std::int8_t * source, std::int8_t * destination)
{
for (auto current = first; current != last; ++current)
{
try
{
// Пробуємо копіювати всі об'єкти в нове місце.
current->manage(operation_t::copy,
source + current->offset, destination + current->offset);
}
catch (...)
{
// Якщо щось пішло не так, то знищуємо все, що вже було скопійовано.
destroy(first, current, destination);
throw;
}
}
}


Інші проблеми
Одна з найбільших проблем була з копіюванням. І, хоча я з нею і розібрався, сумніви все одно періодично виникають.
Поясню.
Припустимо, ми кладемо некопируемый об'єкт (скажімо,
std::unique_ptr
),
std::vector
. Ми це можемо зробити за допомогою переносу. Але якщо ми спробуємо скопіювати вектор, компілятор буде лаятися, тому що внутрішні елементи некопируемы.
У випадку з ДК все дещо інакше:
  1. В момент укладання елемента в ДК потрібно створити обробник копіювання. Якщо об'єкт некопируем, то обробник не може бути створено (помилка компіляції). При цьому ще невідомо, чи збираємося ми взагалі коли-небудь копіювати наш ДК.
  2. У момент власне копіювання ДК інформація про копируемости типу — через стирання типу — вже недоступна.
В даний час обрано наступне рішення проблеми:
  1. Якщо об'єкт копіюємо, то для нього створюється звичайний копіює обробник.
  2. Якщо об'єкт некопируем, то для нього створюється особливий обробник, який при спробі копіювання кидає виняток.
template < typename T>
auto copy (const void * source, void * destination)
->
std::enable_if_t
<
std::is_copy_constructible<T>::value
>
{
new (destination) T(*static_cast<const T *>(source));
}

template < typename T>
auto copy (const void *, void *)
->
std::enable_if_t
<
not std::is_copy_constructible<T>::value
>
{
auto type_name = boost::typeindex::ctti_type_index::type_id<T>().pretty_name();
throw std::runtime_error(u8"Об'єкт типу " + type_name + u8" некопируем");
}

Ще більш складна проблема виникає при порівнянні двох ДК на рівність. Можна було б обійтися тим ж способом, але, крім випадку з помилкою компілятора при спробі порівняти непорівнюване, є ще випадки, коли компілятор генерує не помилку, а попередження — наприклад, при виклику оператора рівності для чисел з плаваючою точкою. Тут, з одного боку, не можна кидати виняток, тому що користувач міг усвідомлювати свої дії та проводити порівняння навмисно. З іншого боку, хотілося б все-таки якось повідомити користувачеві про небезпечною операції.
Ця проблема залишається відкритою.

Виміри продуктивності
Оскільки основною метою було створити саме щільно упакований контейнер, щоб мати оптимальний час доступу до його елементів, у вимірах продуктивності порівнювалася швидкість доступу в ДК зі швидкістю доступу в масив покажчиків на "розкидані" по пам'яті об'єкти.
Застосовувалися дві схеми "розкиданості":
  1. Розрідженість
    Нехай
    N
    — розмір замеряемого масиву,
    S
    — показник розкиду.
    Тоді генерується масив покажчиків розміру
    N * S
    , а потім він проріджується так, що залишаються тільки елементи під номерами
    N * i
    ,
    i = 0, 1, 2, ...
    .
  2. Перемешанность
    Нехай
    N
    — розмір замеряемого масиву,
    S
    — показник розкиду.
    Тоді генерується масив розміру
    N * S
    , перемішується випадковим чином, а потім з нього вибираються перші
    N
    елементів, а останні викидаються.
А в якості точки відліку часу доступу був узятий
std::vector
.
Контейнери розміру 1010
Контейнери розміру 5050
Контейнери розміру 100100
Контейнери розміру 200200
Контейнери розміру 500500
Контейнери розміру 10001000
Графіки підтверджують очевидне:
  1. Швидкість доступу до елементів ДК ідентична швидкості доступу до елементів класу
    std::vector
    (одне складання покажчиків і одне розіменування).
  2. Доступ до елементів масиву покажчиків повільніше. Особливо це видно на великих масивах при показнику розкиду
    S > 1
    , коли дані перестають поміщатися в кеш.



Всі вихідні коди доступні у мене на гітхабі.
До змісту
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.