Есть ли жизнь без 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 везде, ведь порой удобство написания кода может быть важнее выигрыша в производительности (особенно, если он только гипотетический).