01.06.2016 09:35
izvolov 0 1 Источник

Динамический неоднородный плотно упакованный контейнер


Определение 1. Однородный контейнер – это такой контейнер, в котором хранятся объекты строго одного типа.


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


Определение 3. Статический контейнер — это контейнер, состав которого полностью определяется на этапе компиляции.


Под составом в данном случае понимается количество элементов и их типы, но не сами значения этих элементов. Действительно, бывают контейнеры, у которых даже значения элементов определяются на этапе компиляции, но в данной модели такие контейнеры не рассматриваются.

Определение 4. Динамический контейнер — это контейнер, состав которого частично или полностью определяется на этапе выполнения.


По такой классификации, очевидно, существуют четыре вида контейнеров:


  1. Статические однородные


    Сможете придумать пример?

    Обычный массив — int[n].


  2. Статические неоднородные


    Примеры?

    Наиболее яркий пример такого контейнера — это кортеж. В языке C++ он реализуется классом std::tuple<...>.


  3. Динамические однородные


    Догадались?

    Правильно, std::vector<int>.


  4. Динамические неоднородные


    Вот об этом виде контейнеров и пойдёт речь в данной статье.



Динамические неоднородные контейнеры


Существует несколько техник получения динамического неоднородного контейнера. Вот тройка, пожалуй, наиболее распространённых из них:


  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>
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, то они, естественно, и разрушаются "вручную", явным вызовом деструктора.
Это создаёт определённые сложности с копированием и переносом объектов при переаллокации. Поэтому приходится реализовывать относительно сложные конструкции для копирования и переноса:


inline void destroy (const object_info_t & object, std::int8_t * data)
{
    object.manage(operation_t::destroy, nullptr, data + object.offset);
}

template <typename InputIterator>
void destroy (InputIterator first, InputIterator last, std::int8_t * data)
{
    std::for_each(first, last,
        [data] (const auto & object)
        {
            destroy(object, data);
        });
}

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.


Графики подтверждают очевидное:


  1. Скорость доступа к элементам ДК идентична скорости доступа к элементам класса std::vector.
  2. Доступ к элементам массива указателей медленнее. Особенно это видно на больших массивах при показателе разброса S > 1.

...


картинки


...



Все исходные коды доступны у меня на гитхабе.

Поделиться с друзьями
-->

Комментарии (0)