is_type, dynamic_cast, double dispatch и производительность

Как то раз я встретил реализацию шаблонного класса для хранения объектов разных типов, которая мне не понравилась. Если упростить ситуацию, то этот класс выглядит так:

struct val_base
{
    virtual ~val_base() = 0;
    template<typename T> bool is_type() const;
};
template <typename T> struct val : public val_base
{
    T value_;
};

Класс этот общего назначения и поэтому не представляется возможным определить сразу набор виртуальных функции для операций с его потомками. Поэтому используется функции is_type<T>  и работа с экземпляром класса выглядит таким образом

val_base * v;
...
if(v->is_type<int>())
{
   int val = static_cast<val<int> *>(v)->value_;
...
}
else if(v->is_type<double>())
{
   double val = static_cast<val<double> *>(v)->value_;
...
}
...

Реализована функция is_type<T>  так:

template<typename T> bool val_base::is_type() const 
{
      return dynamic_cast<const val<T>*>(this) != NULL;
}

Мне это не понравилось, так как были подозрения что эта реализация имеет серьёзные проблемы с производительностью. Во первых производятся множественные вызовы функции  is_type, во-вторых использование dynamic_cast  даже в этом простейшем случае может быть довольно накладным. Кроме того есть и другие причины не любить такой метод использования этого класса - довольно сложно сопровождать это решение в случае расширения списка хранимых типов, да и это просто некрасиво. Дальнейший текст посвящен измерению производительности различных методов работы с этим классом. Забегая вперед - метод работы, использующий is_type<T> реализованный с помощью  dynamic_cast, действительно самый медленный, более быстрые методы могут работать в 10 раз быстрее.  

Модельная задача

Тестирование производительности проводилось на компьютере с процессором Intel i5-2500k. Использовался компилятор MS VC++ 2010. Для проверки производительности создавался массив указателей на val_base - vector<unique_ptr<val_base> >. Размер массива - 100000 элементов. Массив заполнялся случайным образом объектами пяти типов - val<int>,  val<double>, val<bool>, val<float>, val<char>. Значение value_ каждого объекта также генерировалось случайным образом. Для моделирования простейшей работы с каждым элементом массива вызывалась функция do_count, которая подсчитывала число объектов каждого типа и сумму значений в объекте одного типа. Реализована она была с помощью is_type и if else конструкций, как на примере выше.
Для исходной реализации is_type<T> время прохода по массиву из 100000 элементов получилось 9.07 мсек.

Улучшаем is_type

В широко известном сборнике библиотек boost есть библиотека any. Класс any как раз позволяет хранить величины произвольного типа. Для определения типа хранимой величины используется сравнение std::type_info. Попытаемся использовать следующий вариант функции is_type:

template<typename T> bool val_base::is_type() const 
{
     return typeid( val<T>) == typeid(*this);
}

Действительно результат лучше - 6.56 мсек. Почти на 30% лучше!  Ну что ж, dynamic_cast кроме определения типа объекта также должен еще преобразовать указатель - вот и получается лишнее время.

А если список типов известен? 

И dynamic_cast и typeid используют в run-time информацию предоставляемую системой RTTI.  Если типы хранимых в val<T> объектов ничем не ограничены и могут быть любыми в run-time, то наверное альтернатив нет и повысить производительность не удастся. У нас же ситуация была другая - типы хранимых объектов известны на этапе компиляции. В нашем примере это 5 типов - int,  double, bool, float, char. Это позволяет нам пронумеровать типы и реализовать следующий вариант:

struct val_base
{
    virtual ~val_base();
    enum eType {kInt, kDouble, kBool, kFloat, kChar};
    virtual eType get_type() const = 0;
}
template <typename T> struct val : public val_base
{
    T value_;
    virtual eType get_type() const;
}

В этом случае функция do_count будет иметь следующую реализацию:

void do_count(const val_base * base)
{
    const val_base::eType t = base->get_type();
    switch (t)
    {
        case val_base::kInt:
        {
            ++c_int_;
            s_int_ += static_cast<const val<int> *>(base)->value_;
            break;
        }
        case val_base::kDouble:
        {
            ++c_double_;
            s_double_ += static_cast<const val<double> *>(base)->value_;
            break;
        }
        ......
    }
}

Теперь расходы на выполнение - это вызов одной виртуальной функции и выполнение switch. Время выполнения сразу драматически уменьшилось - 1.37 мсек или всего 15% от исходного варианта!

Самый быстрое определение типа

Мы можем улучшить быстродействие предыдущего вариант, если будем хранить тип val<T> в каждом объекте класса. Это конечно увеличит размер каждого объекта, но в некоторых ситуациях это может быть и не так уж важно. Кроме того в случае если нам не нужно иметь виртуальных функций в интерфейсе класса, то размер объекта будет такой же или даже меньше. Реализация val_base и val<T> может быть такой:

struct val_base
{
    explicit val_base(eType my_type)
    : my_type_(my_type)
    {}
    enum eType {kInt, kDouble, kBool, kFloat, kChar};
    eType get_type() const { return my_type_;}
    const eType my_type_;
}
template <typename T> struct val : public val_base
{
    val();
    T value_;
};

Естественно, нужно будет позаботиться об автоматической инициализации базового класса val_base  в конструкторах  классов.
Время выполнения еще уменьшилось (мы исключили вызов виртуальной функции) - 0.83 мсек или более чем в 10 раз быстрее первоначального варианта. 

"Правильный" способ работы

Приведенные выше "быстрые" способы с явным перечислением возможных типов имеют несколько недостатков. Прежде всего у нас есть 2 сущности - тип классов-наследников и число-идентификатор, которое ему соответствует. Эти пары должны быть согласованы и обычно требуется какая-то дисциплина при программировании. Чаще всего в той или иной мере используют макросы для генерации этих пар. Вторая трудность - при расширении списка классов наследников нужно вручную проверить весть существующий код и добавить необходимые методы для обработки новых классов. Компилятор здесь совершенно не поможет - старый код успешно скомпилируется с новым набором классов. Для решения этой проблемы довольно часто используется методика visitor.  Существует довольно эффективный метод решения этой проблемы. Впервые я  с этим методом познакомился в книге  Джефф Элджер "C++ : библиотека программиста" . Там этот метод назывался "double dispatche", накладные расходы составляют два вызова виртуальной функции. В нашем случае реализация может быть следующей:

class visitor_base;    //forward declaration
struct val_base
{
    virtual void apply(visitor_base & ) = 0;
};
template <typename T> struct val : public val_base
{
    T value_;
    virtual void apply(visitor_base & );
};
// базовый класс визитора
struct visitor_base
{
    void virtual visit(val<int> &) = 0;
    void virtual visit(val<bool> &) = 0;
....
};
// реализация apply в классах наследниках
template <typename T> void val<T>::apply(visitor_base & v)
{
 v.visit(*this);
}

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

struct count_visitor : public visitor_base
{
......
    void virtual visit(val<int> & v) 
    {
        ++c_int_;
        s_int_ += v.value_;
    }
    void virtual visit(val<bool> & v ) 
    {
        ++c_bool_;
        s_bool_ += v.value_;
    }
......
};

После этого использование выглядит довольно просто:

val_base * data;
....
count_visitor v;
data->apply(v);

Затраты на обработку одного объекта класса val<T> составляют два виртуальных вызова функций apply и visit. Время выполнения нашего тестового набора составило 0.93 мсек, что как и ожидалось несколько больше чем "самый быстрый вариант", но все равно в 10 раз меньше исходного варианта с использованием is_type и dynamic_cast.

Не изобретаем велосипеды.

В библиотеке boost есть класс variant, который как раз предназначен для хранения величин различных типов. Список этих типов должен быть известен на этапе компиляции. Реализован интерфейс к данным через визитор (функция apply_visitor и класс static_visitor).   Время выполнения модельной задачи составило 1.15 мсек.

Заключение

 

Таким образом использование функции is_type реализованной с помощью dynamic_cast приводит к самим плохой производительности. Работа с типами переменных, список которых известен на этапе компиляции, позволяет улучшить производительность в 10 раз. Использование методики "визитор" дает хорошие результаты в плане производительности и решает часть проблем сопровождения. double dispatch показывеет один из лучших результатов по производительности.

 

Ну и конечно - не изобретайте велосипедов - используйте стандартные библиотеки! boost::any и  boost::variant в данном случае прекрасно решили бы поставленные задачи.