Есть ли жизнь без RTTI: пишем свой dynamic_cast

В современном С++ осталось не так много вещей, которые не подходят под парадигму «Не плати за то, что не используешь». Одна из них – 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 плох тем, что:

• Не работает на полиморфных типах.

• Не работает с флагом -fno-rtti.

• Для работы требуется ABI-специфичная информация о типах.

• «Сужающие» преобразования работают через просмотр vtable, а это медленная операция.

Одним из решений проблемы может быть использование паттерна проектирования «посетитель» (визитор). Оно избавит от необходимости производить 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);   } } 

Из плюсов данного подхода можно отметить:

• Полиморфность классов теперь необязательна.

• Код может компилироваться без RTTI.

• Мы сами контролируем размер информации о типе. У класса известны накладные расходы – это размер перечисления.

• Быстрая проверка и преобразование через static_cast в теории быстрее, чем преобразование через dynamic_cast.

Однако, стоит отметить и минусы:

• Мы пишем больше кода.

• При множественном наследовании логика проверок будет не такой простой.

• static_cast не умеет работать с виртуальным наследованием и код не скомпилируется. Но много ли людей использует виртуальное наследование в 2022 году?

Посмотрев на код, можно задаться вопросом «А где здесь аналог dynamic_cast«? Конечно, писать проверки именно таким образом не очень удобно. Чтоб исправить это, добавим немного абстракций. Рассмотрим, как это реализовано у нас в PVS-Studio и в LLVM.

Наводим красоту. Подход в PVS-Studio

Вернёмся к нашему примеру:

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);     }   } } 

Теперь рассмотрим альтернативный способ.

Наводим красоту. Подход в LLVM

Вернёмся к нашей структуре 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):

1. Определяем структуру Stmt_RTTI, от которой будут наследоваться структуры IfStmt_RTTI и ForStmt_RTTI. Их мы впоследствии будем преобразовывать при помощи dynamic_cast.

2. Определяем структуру Stmt_WithEnum, от которого будут наследоваться IfStmt_WithEnum и ForStmt_WithEnum. Их мы будем преобразовывать при помощи проверки функцией IsA, реализованной двумя вышеописанными способами, и преобразованием при помощи static_cast.

3. Формируем вектор из 1’000’000 умных указателей на тип Stmt_RTTI / Stmt_WithEnum, инициализируем их псевдослучайно наследниками.

4. Итерируемся по вектору и делаем преобразование к одному из дочерних типов.

Код бенчмарка:

#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 медленнее двух предложенных способов в несколько раз.

Однако давайте пока не будем торопиться с выводами и посмотрим, как себя поведёт PVS-Studio на реальных проектах.

Реальный бенчмарк

Конечно, хочется ответить на вопрос: а даёт ли это хоть сколько-нибудь производительности анализатору? Очевидно, что большую часть времени анализатор проводит далеко не в функциях преобразования указателей, а, например, в диагностических правилах.

• Для замера я поменял наши оптимизированные операции преобразования только в функции, которая производит преобразования между узлами дерева и её специализациях. Стоит отметить, что это не единственная сущность, несущая в себе подобную функциональность.

Замеры мы будем проводить на SelfTester – это наша собственная утилита, которая берёт пул из 123 тестовых проектов и выполняет их анализ при помощи PVS-Studio. Утилита одновременно запускает анализ 4-х проектов, каждый проект проверяется в 8 потоков. В качестве тестовых проектов мы используем реальные проекты с открытым исходным кодом. В результате для каждого проекта генерируется лог предупреждений анализатора. Этот лог сравнивается с эталонным логом для этого же проекта. В ходе сравнения логов SelfTester создаёт журнал сравнения логов в удобном для восприятия разработчиком виде.

Запуск происходил на машине следующей конфигурации:

• процессор Intel Core i7-9700k;

• 32 ГБ RAM;

• Samsung SSD 970 EVO Plus 500GB в качестве системного диска;

• WDC WD10EZEX-22MFCA0, тут располагается SelfTester.

Для бенчмарка мы будем запускать анализ на проектах дважды. Первый запуск был с ядром, в котором наш аналог dyn_cast был изменён на dynamic_cast. Второй запуск – с нашим оптимизированным способом. Оба запуска производились на последней актуальной версии ядра PVS-Studio.

Результаты замеров на 15 проектах из пула:

Попробуем немного исключить статистическую погрешность и повторим эксперимент:

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

Итоги

В результате действительно можно сказать, что для некоторых проектов отказ от RTTI может дать существенный выигрыш в производительности. Не зря Clang собирается с -fno-rtti. Однако не стоит совсем уж зацикливаться на этом и воевать с RTTI везде, ведь порой удобство написания кода может быть важнее выигрыша в производительности (особенно, если он только гипотетический).