Acyclic Visitor19.10.2016 21:33

В этой статье мы рассмотрим один из вариантов реализации поведенческого шаблона проектирования Acyclic Visitor без ипользования RTTI.

Основным назначением поведенческого шаблона проектирования Visitor является введение абстрактной функциональности для иерархической структуры объектов.

Реализации шаблона можно условно разделить на две категории.

Cyclic Visitor. Основан на механизме перегрузки функций (Function overloading). Из-за циклической зависимости (посещаемой иерархии необходимо уточнение типа посетителя, посетителю необходимо уточнение всех классов в иерархии), область применения ограничевается только устойчивыми иерархиями (в которые редко добавляются новые классы).
Acyclic Visitor. Основан на механизме динамической идентификации типа данных (RTTI). Нет ограничений на посещаемые иерархии, но за счет использования динамической идентификации снижается производительность.

Типичная реализация Cyclic Visitor

struct entity;
struct geometry;
struct model;

struct visitor
{
    virtual bool visit(entity &) = 0;
    virtual bool visit(geometry &) = 0;
    virtual bool visit(model &) = 0;
};

struct entity
{
public:
    virtual ~entity() {}
    virtual void accept(visitor & obj) { obj.visit(*this); }
};

struct geometry : entity
{
public:
    void accept(visitor & obj) { obj.visit(*this); }
};

struct model : geometry
{
public:
    void accept(visitor & obj) { obj.visit(*this); }
};

struct test_visitor : visitor
{
public:
    void visit(entity & obj)
    {
        // something
    }

    void visit(geometry &  obj)
    {
        // something
    }

    void visit(model & obj)
    {
        // something
    }
};

Типичная реализация Acyclic Visitor с RTTI

template
struct visitor
{
    virtual void visit(_Visitable &) = 0;
};

struct visitor_base
{
    virtual ~visitor_base(){}
};

struct entity
{
public:
    virtual ~entity()
    {}

    virtual void accept(visitor_base & obj)
    {
        using entity_visitor = visitor;
        if(entity_visitor * ev = dynamic_cast(&obj))
            ev->visit(*this);
    }
};

struct geometry : entity
{
public:

    virtual void accept(visitor_base & obj)
    {
        using geometry_visitor = visitor;
        if(geometry_visitor * gv = dynamic_cast(&obj))
            gv->visit(*this);
    }
};

struct model : geometry
{
public:

    virtual void accept(visitor_base & obj)
    {
        using model_visitor = visitor;
        if(model_visitor * mv = dynamic_cast(&obj))
            mv->visit(*this);
    }
};

struct test_visitor : visitor_base,
                      visitor,
                      visitor,
                      visitor
{

public:
    void visit(entity & obj)
    {
        // something
    }

    void visit(geometry & obj)
    {
        // something
    }

    void visit(model & obj)
    {
        // something
    }
};

Производительность

Выполнение простой операции на массиве из трех миллионов элементов

Pattern	Time (ms)
Cyclic visitor	11.3
Acyclic visitor (RTTI)	220.4

Видно что посетитель c динамической идентификацией сильно уступает в производительности обычному шаблону. Нашей основной задачей будет сохранить ацикличность шаблона, но приблизить его производительность к варианту без RTTI.

Реализация

Основная идея заключается в том, что для набора посещаемых классов из иерархии, посетитель генерирует специальную таблицу позднего связывания (vtbl), содержащую методы-преобразователи, вызывающие соответствующие методы у посетителя, основываясь на уникальном идентификаторе типа посещаемого класса.

Итак, у нас есть две подзадачи

Получить уникальный идентификатор типа
Сгенерировать таблицу позднего связывания

Уникальный идентификатор типа

Для решения этой задачи мы воспользуемся маленькой header-only библиотекой CTTI. В качестве уникального идентификатора будем использовать хеш, посчитанный на основе уникального строкового имени типа.

namespace detail {

using hash_type = std::uint64_t;

template
struct tag {};

template
inline constexpr hash_type get_hash()
{
    using tag_type = tag::type,
                         typename std::remove_cv<_Specific>::type>;
    return ctti::unnamed_type_id().hash();
}

} /* detail */

Исходя из того, что мы будем обрабатывать наши объекты полиморфно и точный тип объекта нам будет неизвестен, кажный класс в иерархии должен позаботиться о механизме получения своего уникального идентификатора. Мы добавим виртуальный метод возвращающий идентификатор.

template 
struct visitable
{
    using base_type = _Base;
};

// макрос для удобства
// добавляется в конкретный класс в иерархии
#define VISITABLE(Specific) \
static constexpr detail::hash_type hash__ = detail::get_hash(); \
virtual detail::hash_type get_hash() const \
{\
    return hash__; \
}

Пример

struct entity : visitable
{
public:
    VISITABLE(entity);

public:
    virtual ~entity() {}
};

struct geometry : entity
{
public:
    VISITABLE(geometry);
};

struct model : geometry
{
public:
    VISITABLE(model);
};

Генерация таблицы позднего связывания

В качестве контейнера для методов-преобразователей мы будем использовать стандартный ассоциативный контейнер map с уникальным идентификатором посещаемого типа в качестве ключа.

namespace detail {

template
struct vtbl_traits
{
    // базовый класс в иерархии.
    // также содержит иформацию о константности итерируемых объектов
    using base_type = _Base;
    // тип посетителя
    using visitor_type = _Visitor;
    // тип указателя на метод-преобразователь посетителя
    using function_type = void(visitor_type::*)(base_type &);
};

template
struct vtbl
{
    using base_type = typename _Traits::base_type;
    using function_type = typename _Traits::function_type;
    using visitor_type = typename _Traits::visitor_type;

    // добавить преобразователь для конкретного класса из иерархии
    template
    void put(function_type function)
    {
        vtbl_[get_hash()] = function;
    }

    // получить преобразователь для объекта на основе уникального идентификатора
    function_type get(const hash_type & hash) const
    {
        auto it = vtbl_.find(hash);
        return it != vtbl_.end() ? it->second : nullptr;
    }

private:

    std::map vtbl_;
};

} /* detail */

Далле нам нужно сгенерировать таблицу для списка классов, которые мы будем посещать

namespace detail
{

// _Traits свойства таблицы
// _Specifics список классов для посещения
template
struct vtbl_builder
{
    // тип таблицы
    using vtbl_type = vtbl<_Traits>;
    // тип посетителя
    using visitor_type = typename _Traits::visitor_type;
    // тип базового класа
    using base_type = typename _Traits::base_type;

    template
    struct targets {};

    vtbl_builder()
    {
        // начинаем заполнять таблицу
        put_thunk(targets<_Specifics...>());
    }

    const auto * get_vtbl() const { return &vtbl_; }

private:

    template
    void put_thunk(targets<_Specific, _Tail...>)
    {
        // проверяем имеет ли посетитель метод для обработки 
        // объекта с типом из списка классов.
        // добавляем константность если итерация идет по констанным объектам
        using specific_type = constancy_t;
        using is_put = typename has_visit_method::type;

        put_thunk(targets<_Specific, _Tail...>(), is_put());
    }

    // у посетителя есть метод для обработки класса из списка
    // добавляем преобразователь thunk и переходим к следующему типу
    template
    void put_thunk(targets<_Specific, _Tail...>, std::true_type)
    {
        vtbl_.template put<_Specific>(&visitor_type::template thunk);
        put_thunk(targets<_Tail...>());
    }

    // у посетителя нет метода для обработки класса из списка
    // ничего не добавляем, переходим к следующему типу
    template
    void put_thunk(targets<_Specific, _Tail...>, std::false_type)
    {
        put_thunk(targets<_Tail...>());
    }

    void put_thunk(targets<>) {}

private:

    vtbl_type vtbl_;
};

// получаем указатель на таблицу для конкретного списка классов
template 
inline const auto * get_vtbl()
{
    static vtbl_builder<_Traits, typename std::remove_cv<_Specifics>::type...> builder;
    return builder.get_vtbl();
}

} /* detail */

Добавляем константность типу на основе константности другово типа

template
using constancy_t = typename std::conditional::value, 
                                              const _To, _To>::type;

Проверяем наличие метода

template
struct has_visit_method
{
    template
    static auto test(_Param * p) -> decltype(std::declval<_Class>().visit(*p),
                                             std::true_type());
    template
    static std::false_type test(...);

    using type = decltype(test<_Visitor, _Specific>(nullptr));
    static constexpr const bool value = std::is_same::value;
};

Нам осталось определить методы-преобразователи и описать механизм обработки объекта

template
struct visitor_traits
{ 
    // тип базового объекта в иерархии
    using base_type = _Base;
};

// базовый класс для посетителя
template
struct visitor
{
    using visitor_type = _Visitor;
    using traits_type  = _Traits;

    // метод-преобразователь, указатель на специализацию хранится в таблице
    template
    void thunk(_Base & base)
    {
        using specific_type = detail::constancy_t<_Base, _Specific>;
        static_cast(this)->visit(static_cast(base));
    }

    // метод обработки объекта
    template
    void operator()(_Base & base)
    {
        // проверяем, что обрабатываемый класс является потомком 
        // базового класса посещаемой иерархии.
        static_assert(std::is_base_of::value, "");

        // определяем свойства таблицы.
        // тип _Base используется для получение информации 
        // о константности итерируемых объектов
        using base_type = detail::constancy_t<_Base, typename traits_type::base_type>;
        using traits_type = detail::vtbl_traits;

        // получаем указатель на таблицу с преобразователями.
        // шаблонный метод get_vtbl определен в конкретном посетителе
        const auto * vtbl = static_cast(this)->template get_vtbl();
        // запрашиваем у обрабатываемго объекта уникальный идентификатор типа,
        // если для этого типа зарегистрирован обрабочик, вызываем
        if(auto thunk = vtbl->get(base.get_hash()))
            (static_cast(this)->*thunk)(base);
    }
};

// макрос для определения списка обрабатываемых объектов и инициализации таблицы
// добавляется в конкретный класс-посетитель
#define VISIT(...) \
template \
const auto * get_vtbl() const \
{ \
    return detail::get_vtbl<_Traits, __VA_ARGS__>(); \
}

Пример

struct entity : visitable
{
public:
    VISITABLE(entity);

public:
    virtual ~entity() {}
};

struct geometry : entity
{
public:
    VISITABLE(geometry);
};

struct model : geometry
{
public:
    VISITABLE(model);
};

template
using visitor_entities = visitor<_Visitor, visitor_traits>;

struct test_visitor : visitor_entities
{
public:

    VISIT(entity, geometry, model);

public:

    void visit(const entity & obj)
    {
        // something
    }

    void visit(const geometry & obj)
    {
        // something
    }

    void visit(const model & obj)
    {
        // something
    }
};

int main()
{
    const entity & ref_entity = entity();
    const entity & ref_model = model();
    const entity & ref_geometry = geometry();

    test_visitor test;

    test(ref_entity);
    test(ref_model);
    test(ref_geometry);
}

Производительность

Производительность на том же тесте с разными стандартными контейнерами для таблицы позднего связывания

Pattern	Time (ms)
Cyclic visitor	11.3
Acyclic visitor (RTTI)	220.4
Acyclic visitor with map	23.2
Acyclic visitor with unordered_map	44.5
Acyclic visitor with sort vector	31.1

Код проекта можно найти на GitHub.

Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!

Acyclic Visitor19.10.2016 21:33

Производительность

Реализация

Уникальный идентификатор типа

Генерация таблицы позднего связывания

Производительность

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