Acyclic Visitor

У цій статті ми розглянемо один з варіантів реалізації поведінкового шаблону проектування Acyclic Visitor без використання RTTI.

Основним призначенням поведінкового шаблону проектування Visitor є введення абстрактної функціональності для ієрархічної структури об'єктів.
Реалізації шаблону можна умовно розділити на дві категорії.
  • Cyclic Visitor. Заснований на механізмі перевантаження функцій (Function overloading). З-за циклічної залежності (відвідуваною ієрархії необхідно уточнення типу відвідувача, відвідувачеві необхідно уточнення всіх класів в ієрархії), сфера застосування обмежується тільки стійкими ієрархіями (які рідко додаються нові класи).
  • Acyclic Visitor. Заснований на механізмі динамічної ідентифікації типу даних (RTTI). Немає обмежень на відвідувані ієрархії, але за рахунок використання динамічної ідентифікації знижується продуктивність.
Типова реалізація Cyclic Visitor
struct entity;
struct geometry;
struct model;

struct visitor
{
віртуальний bool visit(entity &) = 0;
віртуальний bool visit(geometry &) = 0;
віртуальний 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 < typename _Visitable>
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<entity>;
if(entity_visitor * ev = dynamic_cast<entity_visitor*>(&obj))
ev->visit(*this);
}
};

struct geometry : entity
{
public:

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

struct model : geometry
{
public:

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

struct test_visitor : visitor_base,
visitor<entity>,
visitor<geometry>,
visitor<model>
{

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 < typename _Base, typename _Specific>
struct tag {};

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

} /* detail */

Виходячи з того, що ми будемо обробляти наші об'єкти поліморфно і точний тип об'єкта нам невідомий, кожний клас в ієрархії повинен подбати про механізм отримання свого унікального ідентифікатора. Ми додамо віртуальний метод повертає ідентифікатор.
template < typename _Base>
struct visitable
{
using base_type = _Base;
};

// макрос для зручності
// додається в конкретний клас в ієрархії
#define VISITABLE(Specific) \
static constexpr detail::hash_type hash__ = detail::get_hash<base_type, Specific>(); \
virtual detail::hash_type get_hash() const \
{\
return hash__; \
}

Приклад
struct entity : visitable<entity>
{
public:
VISITABLE(entity);

public:
virtual ~entity() {}
};

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

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

Генерація таблиці пізнього зв'язування

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

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

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

// додати перетворювач для конкретного класу з ієрархії
template < typename _Specific>
void put(function_type function)
{
vtbl_[get_hash<base_type, _Specific>()] = function;
}

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

private:

std::map<hash_type, function_type> vtbl_;
};

} /* detail */

Далле нам потрібно створити таблицю для списку класів, які ми будемо відвідувати
namespace detail
{

// _Traits властивості таблиці
// _Specifics список класів для відвідування
template < typename _Traits, typename... _Specifics>
struct vtbl_builder
{
// тип таблиці
using vtbl_type = vtbl<_Traits>;
// тип відвідувача
using visitor_type = typename _Traits::visitor_type;
// тип базового класу
using base_type = typename _Traits::base_type;

template < typename... _Targets>
struct targets {};

vtbl_builder()
{
// починаємо заповнювати таблицю
put_thunk(targets<_Specifics...>());
}

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

private:

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

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

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

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

void put_thunk(targets<>) {}

private:

vtbl_type vtbl_;
};

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

} /* detail */

Додаємо константность типу на основі константності іншої типу
template < typename _From, typename _To>
using constancy_t = typename std::conditional<std::is_const<_From>::value, 
const _To, _To>::type;

Перевіряємо наявність методу
template < typename _Visitor, typename _Specific>
struct has_visit_method
{
template < typename _Class, typename _Param>
static auto test(_Param * p) -> decltype(std::declval<_Class>().visit(*p),
std::true_type());
template < typename, typename>
static std::false_type test(...);

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

Нам залишилося визначити методи-перетворювачі і описати механізм обробки об'єкта
template < typename _Base>
struct visitor_traits
{ 
// тип базового об'єкта в ієрархії
using base_type = _Base;
};

// базовий клас для відвідувача
template < typename _Visitor, typename _Traits>
struct visitor
{
using visitor_type = _Visitor;
using traits_type = _Traits;

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

// метод обробки об'єкта
template < typename _Base>
void operator()(_Base & base)
{
// перевіряємо, що оброблюваний клас є нащадком 
// базового класу відвідуваною ієрархії.
static_assert(std::is_base_of<typename traits_type::base_type, _Base>::value, "");

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

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

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

Приклад
struct entity : visitable<entity>
{
public:
VISITABLE(entity);

public:
virtual ~entity() {}
};

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

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

template < typename _Visitor>
using visitor_entities = visitor<_Visitor, visitor_traits<entity>>;

struct test_visitor : visitor_entities<test_visitor>
{
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)
Спасибі!
Джерело: Хабрахабр

0 коментарів

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