В современном С++ осталось не так много вещей, которые не подходят под парадигму "Не плати за то, что не используешь". Одна из них – dynamic_cast. В рамках данной статьи мы разберёмся, что с ним не так, а когда поймём – попробуем предложить альтернативу.
Давайте вспомним немного азов языка C++. Если вам покажется скучной эта часть, вы всегда можете перейти к следующей главе.
Итак, представим, что у нас есть следующая иерархия классов:
struct Shape
{
virtual void Draw() const = 0;
};
struct Circle : Shape
{
void Draw() const override;
};
struct Triangle : Shape
{
void Draw() const override;
};
struct Rectangle : Shape
{
void Draw() const override;
};Согласно объектно-ориентированной парадигме мы без каких-либо проблем можем производить "расширяющие" преобразования (upcasting) из указателя на объект дочернего класса к указателю на объект базового класса:
#include <memory>
void foo(const Shape *);
void bar()
{
std::unique_ptr<Shape> circle = std::make_unique<Circle>();
std::unique_ptr<Shape> triangle = std::make_unique<Triangle>();
std::unique_ptr<Shape> rect = std::make_unique<Rectangle>();
foo(circle.get());
foo(triangle.get());
foo(rect.get());
}Т.к. производные классы Circle, Triangle и Rectangle гарантированно содержат в себе инстанс базового класса Shape, компилятор без каких-либо накладных расходов может сделать такое преобразование.
А что, если мы теперь захотим преобразовать указатель на базовый класс в указатель на производный? Под указателем на Shape может скрываться любой производный от него класс. Нужно как-то на этапе исполнения программы понять, что же в реальности хранится под указателем. Тут на сцену и выходит механизм динамической идентификации типа данных (runtime type identification, сокр. RTTI).
RTTI – это специальный механизм, который позволяет определить тип данных переменной во время выполнения программы. Механизм RTTI применяется всякий раз, когда вы используете операторы dynamic_cast и typeid. Стандарт C++ не определяет, как именно реализуется RTTI, и вся ответственность перекладывается на двоичный интерфейс приложений (application binary interface, сокр. ABI). В большинстве компиляторов информация хранится в виртуальной таблице (vtable). Если вам интересны детали, то в качестве одного из примеров можно ознакомиться с имплементацией на платформе x86_64.
Чтобы корректно произвести "сужающие" преобразования (downcasting) из указателя на объект базового класса к указателю на объект дочернего класса, воспользуемся оператором dynamic_cast:
void Visit(const Shape *ptr)
{
if (auto circle = dynamic_cast<const Circle *>(ptr))
{
// do smth with circle
}
else if (auto triangle = dynamic_cast<const Triangle *>(ptr))
{
// do smth with triangle
}
else if (auto rect = dynamic_cast<const Rectangle *>(ptr))
{
// do smth with rect
}
}Конечно, dynamic_cast в пользовательском коде встречается не так часто, typeid используют еще реже. Кто-то считает, что использование таких операторов – симптом плохого дизайна приложения. Однако как обстоят дела в приложениях, в которых такие операции – вынужденная мера, и их число может измеряться миллионами? Настолько ли это медленно – слазить в vtable? Об этом мы и поговорим.
Статические анализаторы, как и компиляторы, работают с исходным кодом через его промежуточное представление. Одно из них – абстрактное синтаксическое дерево (AST). В нём узлы выступают в роли различных языковых конструкций.
Удобный способ реализовать AST в коде – иерархия классов. Например, у компилятора Clang узлы дерева наследуются от таких классов, как Decl (интерфейс для объявлений функций и типов) и Stmt (интерфейс для конструкций).
Рассмотрим пример. Допустим, у нас есть следующий синтетический блок кода:
{
for (size_t i = 0; i < 10; ++i) ;
if (true) ;
}Согласно грамматикам языков C и C++, это составная конструкция (блок), содержащая цикл for и ветвление if. Если попробовать реализовать это в объектно-ориентированной парадигме, у нас будут следующие сущности:
// Base class for all type of statements
struct Stmt { /* .... */ };
// Base class for all type of expressions
struct Expr { /* .... */ };
// Base class for all types of declarations
struct Decl { /* .... */ };
struct IfStmt : Stmt
{
const Expr& GetCondition() const noexcept;
const Stmt& GetBody() const noexcept;
const Stmt* GetElse() const noexcept;
// ....
};
struct ForStmt : Stmt
{
const Decl* GetInit() const noexcept;
const Expr* GetCondition() const noexcept;
const Expr* GetPostBodyExpr() const noexcept;
const Stmt& GetBody() const noexcept;
// ....
};
using StatementList = ....;
struct CompoundStmt : Stmt
{
auto begin() const noexcept { return stmts.begin(); }
auto end() const noexcept { return stmts.end(); }
private:
StatementList stmts;
// ....
};Мы будем класть все конструкции внутри блока в некоторый контейнер, например std::vector. Так как возможных конструкций в языках ни одна и даже не две, будем работать с ними через указатели на базовый класс Stmt. Теперь мы можем перебрать все конструкции:
void foo(const CompoundStmt *compStmt)
{
for (auto stmt : compStmt)
{
// do smth
}
}И последнее, что мы хотим сделать, это позвать для каждого специализированного узла свою кастомную логику:
void Visit(const IfStmt &);
void Visit(const ForStmt &);И здесь мы как раз сталкиваемся с проблемой – необходимо узнать на этапе работы программы, какая именно конструкция лежит под указателем на Stmt, и позвать нужную перегрузку:
void foo(const Stmt *stmt)
{
for (auto stmt : compStmt)
{
if (auto ifStmt = dynamic_cast<const IfStmt *>(stmt))
{
Visit(*ifStmt);
}
else if (auto forStmt = dynamic_cast<const ForStmt *>(stmt))
{
Visit(*forStmt);
}
}
}Однако есть маленькая деталь, из-за которой код выше может не скомпилироваться. Если базовый класс Stmt не полиморфен, то магия dynamic_cast работать не будет. Чтобы исправить проблему, нужно добавить хотя бы одну виртуальную функцию. Например, так:
struct Stmt { virtual void Dummy(); /* .... */ };Теперь всё хорошо и код будет работать в большинстве случаев. Пока не окажется, что в проекте по разным объективным причинам выключен RTTI. Например, в компиляторах GCC/Clang это можно сделать, передав флаг -fno-rtti (GCC, Clang), в MSVC – посредством /GR-. Стоит отметить, что выключение RTTI не задевает механизм исключений и динамическую диспетчеризацию.
Кстати, пока готовил статью, нашёл интересный опрос на isocpp.org. В нём из 2058 респондентов 14% ответили, что они частично отключают RTTI на своих программах, а 18% отключают его полностью.
Подытожим, dynamic_cast плох тем, что:
Одним из решений проблемы может быть использование паттерна проектирования "посетитель" (визитор). Оно избавит от необходимости производить dynamic_cast ценой одного-двух вызовов виртуальной функции. Однако давайте посмотрим, как можно поступить иначе.
Рецепт лечения на самом деле прост. Мы внедрим в родительский класс поле с информацией о типе и будем сами проверять её. Это может выглядеть так:
struct Stmt
{
enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, .... };
const Type m_kind;
Stmt(Type kind) : m_kind { kind } { /* .... */ }
/* .... */
};
struct IfStmt : Stmt
{
IfStmt() : Stmt { Stmt::Type::IfStmt } { /* .... */ }
/* .... */
};
struct ForStmt : Stmt
{
ForStmt() : Stmt { Stmt::Type::ForStmt } { /* .... */ }
/* .... */
};Тогда при создании объекта дочернего класса мы записываем его тип в поле m_kind. Теперь мы можем проверять тип следующим образом:
void foo(const Stmt *stmt)
{
if (stmt->m_kind == Stmt::Type::IfStmt)
{
auto ifStmt = static_cast<const IfStmt *>(stmt)
Visit(*ifStmt);
}
else if (stmt->m_kind == Stmt::Type::ForStmt)
{
auto forStmt = static_cast<const ForStmt *>(stmt)
Visit(*forStmt);
}
}Из плюсов данного подхода можно отметить:
Однако стоит отметить и минусы:
Посмотрев на код, можно задаться вопросом: "А где здесь аналог dynamic_cast"? Конечно, писать проверки именно таким образом не очень удобно. Чтоб исправить это, добавим немного абстракций. Рассмотрим, как это реализовано у нас в PVS-Studio и в LLVM.
Вернёмся к нашему примеру:
struct Stmt
{
enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, .... };
Stmt(Type kind) : m_kind { kind } { /* .... */ }
Type Kind() const { return m_kind; }
private:
const Type m_kind;
/* .... */
};Реализуем шаблон функции IsA, который будет принимать указатель наш объект и предполагаемый тип. Внутри она будет выполнять проверку на нулевой указатель и на нужный kind.
template <typename T, typename Kind>
bool IsA(T *p, Kind kind) noexcept
{
return p && p->Kind() == kind;
}Далее реализуем пару шаблонов структур без определения:
template <Stmt::Type K>
struct type_from_kind;
template <typename T>
struct kind_from_type;Они нужны для того, чтобы потом специализировать их для каждого производного класса. Таким образом, мы свяжем тип узла дерева и константу перечисления, находящуюся внутри класса.
template <> struct type_from_kind<Stmt::IfStmt>
{
using type = IfStmt;
};
template <> struct kind_from_type<IfStmt>
{
static constexpr auto value = Stmt::Type::IfStmt;
};Конечно, писать такие специализации для каждого класса не очень приятно. Тут нам на помощь может прийти "макросная магия":
#define MAKE_STMT_TRAITS(t, k) \
template <> struct type_from_kind<k> \
{ \
using type = t; \
}; \
template <> struct kind_from_type<t> \
{ \
static constexpr auto value = k; \
};Тогда определение дочерних классов будет выглядеть так:
struct IfStmt : Stmt { /* .... */ };
MAKE_STMT_TRAITS(IfStmt, Stmt::IfStmt)
struct ForStmt : Stmt { /* .... */ };
MAKE_STMT_TRAITS(ForStmt, Stmt::ForStmt)Теперь можно реализовать свой dyn_cast, инкапсулирующий static_cast c проверкой на нужный тип через функцию IsA:
template <typename To, typename From>
requires std::is_pointer_v<To> && std::convertible_to<From, To>
auto dyn_cast(From *p) noexcept
{
using ResultType = std::remove_cvref_t<std::remove_pointer_t<To>>;
return IsA(p, kind_from_type<ResultType>::value)
? static_cast<To>(p)
: nullptr;
}Благодаря такому подходу можно добиться согласованности со способом, когда мы просто писали dynamic_cast:
void foo(const Stmt *stmt)
{
for (auto stmt : compStmt)
{
if (auto ifStmt = dyn_cast<const IfStmt *>(stmt))
{
Visit(*ifStmt);
}
else if (auto forStmt = dyn_cast<const ForStmt *>(stmt))
{
Visit(*forStmt);
}
}
}Теперь рассмотрим альтернативный способ.
Вернёмся к нашей структуре Stmt:
struct Stmt
{
enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, .... };
Stmt(Type kind) : m_kind { kind } { /* .... */ }
Type Kind() const { return m_kind; }
private:
const Type m_kind;
/* .... */
};В каждый класс-наследник мы внедряем статическую функцию-член classof. Она принимает указатель на базовый класс и проверяет его на совпадение с kind дочернего класса:
struct IfStmt : Stmt
{
static bool classof(const Stmt *stmt) noexcept
{
return stmt->Kind() == Stmt::Type::IfStmt;
}
/* .... */
};
struct ForStmt : Stmt
{
static bool classof(const Stmt *stmt) noexcept
{
return stmt->Kind() == Stmt::Type::ForStmt;
}
/* .... */
};Далее в функции IsA нужно просто позвать classof из типа, который нам передали первым шаблонным параметром:
template <typename To, typename From>
bool IsA(From *p) noexcept
{
using ResultType = std::remove_cvref_t<
std::remove_pointer_t< std::remove_cv_ref_t<To> >
>;
return ResultType::classof(p);
}Тогда наш dyn_cast будет выполнять такую же проверку IsA, как и в первом способе, и в зависимости от того, совпал тип или нет, делать static_cast к нужному типу или возвращать нулевой указатель:
template <typename To, typename From>
requires std::is_pointer_v<To> && std::convertible_to<From *, To>
auto dyn_cast(From *p) noexcept
{
using res_type = std::remove_cv_t <
std::remove_pointer_t< std::remove_cvref_t<To> >
>;
return IsA<res_type>(p) ? static_cast<To>(p) : nullptr;
}Когда я рассказывал про бенчмарки на конференции, я привёл только синтетические тесты. Было подозрение, что этого недостаточно, это же отметил и один из коллег. Был разговор о том, что, не зная, сколько именно производительности даёт описанный способ, не стоит переписывать на него код. В этой статье я исправляюсь и привожу статистику, на сколько замедлится ядро анализатора, если вернуть dynamic_cast.
Синтетический бенчмарк выглядит следующим образом (ссылка на Quick C++ Benchmark):
#include <memory>
#include <vector>
#include <random>
struct Stmt_RTTI { virtual ~Stmt_RTTI() = default; };
struct IfStmt_RTTI : Stmt_RTTI { };
struct ForStmt_RTTI : Stmt_RTTI { };
struct Stmt_WithEnum
{
enum Type { IfStmt, ForStmt, DoStmt, WhileStmt };
Stmt_WithEnum(Type kind) : m_kind { kind } { }
virtual ~Stmt_WithEnum() = default;
Type Kind() const { return m_kind; }
private:
const Type m_kind;
};
namespace Solution1
{
template <Stmt_WithEnum::Type K>
struct type_from_kind;
template <typename T>
struct kind_from_type;
#define MAKE_STMT_TRAITS(t, k) \
template <> struct Solution1::type_from_kind<k> \
{ \
using type = t; \
}; \
template <> struct Solution1::kind_from_type<t> \
{ \
static constexpr auto value = k; \
};
template <typename T, typename Kind, typename ...Kinds>
bool IsA(T stmt, Kind kind, Kinds ...kinds) noexcept
{
return stmt &&
((stmt->Kind() == kind) || ... || (stmt->Kind() == kinds));
}
template <typename To, typename From>
requires std::is_pointer_v<To>
&& requires { static_cast<To>(std::declval<From *>()); }
auto dyn_cast(From *p) noexcept
{
using ResultType = std::remove_cvref_t<
std::remove_pointer_t< std::remove_cvref_t<To> >
>;
return IsA(p, kind_from_type<ResultType>::value)
? static_cast<To>(p)
: nullptr;
}
}
struct IfStmt_WithEnum : Stmt_WithEnum
{
IfStmt_WithEnum() : Stmt_WithEnum { Stmt_WithEnum::IfStmt } {}
static bool classof(const Stmt_WithEnum *p) noexcept
{
return p && p->Kind() == Stmt_WithEnum::IfStmt;
}
};
MAKE_STMT_TRAITS(IfStmt_WithEnum, Stmt_WithEnum::IfStmt)
struct ForStmt_WithEnum : Stmt_WithEnum
{
ForStmt_WithEnum() : Stmt_WithEnum { Stmt_WithEnum::ForStmt } {}
static bool classof(const Stmt_WithEnum *p) noexcept
{
return p && p->Kind() == Stmt_WithEnum::ForStmt;
}
};
MAKE_STMT_TRAITS(ForStmt_WithEnum, Stmt_WithEnum::ForStmt)
namespace Solution2
{
template <typename To, typename From>
bool IsA(From *p) noexcept
{
using ResultType = std::remove_cvref_t<
std::remove_pointer_t< std::remove_cvref_t<To> >
>;
return ResultType::classof(p);
}
template <typename To, typename From>
requires std::is_pointer_v<To>
&& requires { static_cast<To>(std::declval<From *>()); }
auto dyn_cast(From *p) noexcept
{
using ResultType = std::remove_cvref_t<
std::remove_pointer_t< std::remove_cvref_t<To> >
>;
return IsA<ResultType>(p) ? static_cast<To>(p) : nullptr;
}
}
std::unique_ptr<Stmt_RTTI> factory_1()
{
static std::mt19937_64 Generator { 0 };
std::uniform_int_distribution d { 0, 1 };
switch (d(Generator))
{
case 0:
return std::make_unique<IfStmt_RTTI>();
case 1:
return std::make_unique<ForStmt_RTTI>();
}
std::terminate();
}
std::unique_ptr<Stmt_WithEnum> factory_2()
{
static std::mt19937_64 Generator { 0 };
std::uniform_int_distribution d { 0, 1 };
switch (d(Generator))
{
case 0:
return std::make_unique<IfStmt_WithEnum>();
case 1:
return std::make_unique<ForStmt_WithEnum>();
}
std::terminate();
}
static void StmtRTTI_Benchmark(benchmark::State& state) {
std::vector<std::unique_ptr<Stmt_RTTI>> vec;
const auto size = 1'000'000u;
vec.reserve(size);
for (size_t i = 0; i < size; ++i)
{
vec.push_back(factory_1());
}
// Code inside this loop is measured repeatedly
for (auto _ : state)
{
for (const auto &stmt : vec)
{
if (auto ifStmt = dynamic_cast<const IfStmt_RTTI *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(ifStmt);
}
else if (auto forStmt = dynamic_cast<const ForStmt_RTTI *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(forStmt);
}
}
}
}
// Register the function as a benchmark
BENCHMARK(StmtRTTI_Benchmark);
static void StmtWithEnum_Benchmark_1(benchmark::State& state) {
std::vector<std::unique_ptr<Stmt_WithEnum>> vec;
const auto size = 1'000'000u;
vec.reserve(size);
for (size_t i = 0; i < size; ++i)
{
vec.push_back(factory_2());
}
// Code inside this loop is measured repeatedly
for (auto _ : state)
{
for (const auto &stmt : vec)
{
if (auto ifStmt =
Solution1::dyn_cast<const IfStmt_WithEnum *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(ifStmt);
}
else if (auto forStmt =
Solution1::dyn_cast<const ForStmt_WithEnum *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(forStmt);
}
}
}
}
BENCHMARK(StmtWithEnum_Benchmark_1);
static void StmtWithEnum_Benchmark_2(benchmark::State& state)
{
std::vector<std::unique_ptr<Stmt_WithEnum>> vec;
const auto size = 1'000'000u;
vec.reserve(size);
for (size_t i = 0; i < size; ++i)
{
vec.push_back(factory_2());
}
// Code inside this loop is measured repeatedly
for (auto _ : state)
{
for (const auto &stmt : vec)
{
if (auto ifStmt = Solution2::dyn_cast<
const IfStmt_WithEnum *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(ifStmt);
}
else if (auto forStmt =
Solution2::dyn_cast<const ForStmt_WithEnum *>(stmt.get()))
{
// Make sure the variable is not optimized away by compiler
benchmark::DoNotOptimize(forStmt);
}
}
}
}
BENCHMARK(StmtWithEnum_Benchmark_2);Результаты:
Как можно заметить, способ с dynamic_cast медленнее двух предложенных способов в 3-4 раза.
Однако давайте пока не будем торопиться с выводами и посмотрим, как себя поведёт PVS-Studio на реальных проектах.
Конечно, хочется ответить на вопрос: а даёт ли это хоть сколько-нибудь производительности анализатору? Очевидно, что большую часть времени анализатор проводит далеко не в функциях преобразования указателей, а, например, в диагностических правилах.
Замеры мы будем проводить на SelfTester – это наша собственная утилита, которая берёт пул из 123 тестовых проектов и выполняет их анализ при помощи PVS-Studio. Утилита одновременно запускает анализ 4-х проектов, каждый проект проверяется в 8 потоков. В качестве тестовых проектов мы используем реальные проекты с открытым исходным кодом. В результате для каждого проекта генерируется лог предупреждений анализатора. Этот лог сравнивается с эталонным логом для этого же проекта. В ходе сравнения логов SelfTester создаёт журнал сравнения логов в удобном для восприятия разработчиком виде.
Запуск происходил на машине следующей конфигурации:
Для бенчмарка мы будем запускать анализ на проектах дважды. Первый запуск был с ядром, в котором наш аналог dyn_cast был изменён на dynamic_cast. Второй запуск – с нашим оптимизированным способом. Оба запуска производились на последней актуальной версии ядра PVS-Studio.
Результаты замеров на 15 проектах из пула:
|
Проект |
Размер проекта, KLOC |
Время: dynamic_cast |
Время: проверка + static_cast |
|---|---|---|---|
|
SObjectizer |
17.2 |
0:01:10 |
0:00:56 |
|
StrongDC |
102 |
0:00:46 |
0:00:41 |
|
Notepad++ |
111 |
0:02:48 |
0:02:55 |
|
WinMerge |
172 |
0:11:02 |
0:09:48 |
|
db_10 |
213 |
0:36:58 |
0:32:20 |
|
pcsx2 |
302 |
0:04:44 |
0:04:57 |
|
dosbox |
302 |
0:05:54 |
0:04:12 |
|
CamStudio |
327 |
0:09:49 |
0:08:34 |
|
Shareaza |
400 |
0:40:32 |
0:36:17 |
|
mpc-hc |
872 |
0:40:46 |
0:34:30 |
|
QtParts |
1361 |
0:03:31 |
0:02:35 |
|
miranda32 |
1811 |
0:32:03 |
0:27:07 |
|
awesome-hpp |
2196 |
0:12:01 |
0:11:37 |
|
ffdshow |
2213 |
0:36:23 |
0:34:08 |
|
Freeswitch |
3690 |
0:37:33 |
0:33:30 |
Попробуем немного исключить статистическую погрешность и повторим эксперимент:
|
Проект |
Размер проекта, KLOC |
Время: dynamic_cast |
Время: проверка + static_cast |
|---|---|---|---|
|
SObjectizer |
17.2 |
0:01:04 |
0:00:51 |
|
StrongDC |
102 |
0:00:49 |
0:00:47 |
|
Notepad++ |
111 |
0:03:11 |
0:02:58 |
|
WinMerge |
172 |
0:11:23 |
0:09:44 |
|
db_10 |
213 |
0:37:38 |
0:32:50 |
|
pcsx2 |
302 |
0:04:49 |
0:04:35 |
|
dosbox |
302 |
0:06:05 |
0:05:20 |
|
CamStudio |
327 |
0:10:19 |
0:09:15 |
|
Shareaza |
400 |
0:40:48 |
0:36:39 |
|
mpc-hc |
872 |
0:37:37 |
0:34:18 |
|
QtParts |
1361 |
0:03:52 |
0:03:05 |
|
miranda32 |
1811 |
0:33:04 |
0:31:28 |
|
awesome-hpp |
2196 |
0:12:09 |
0:11:18 |
|
ffdshow |
2213 |
0:39:32 |
0:36:04 |
|
Freeswitch |
3690 |
0:36:54 |
0:32:16 |
Из бенчмарков заметно, что чем больше размер проекта, тем сильнее влияние dynamic_cast на итоговое время его анализа. А для небольших проектов, которые быстро анализируются, правка не так существенна.
В результате действительно можно сказать, что для некоторых проектов отказ от RTTI может дать существенный выигрыш в производительности. Не зря Clang собирается с -fno-rtti. Однако не стоит совсем уж зацикливаться на этом и воевать с RTTI везде, ведь порой удобство написания кода может быть важнее выигрыша в производительности (особенно, если он только гипотетический).
