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

Проект

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

Комментарии (9)


  1. n0lavar
    13.10.2022 12:02
    +3

    Я не совсем понял, зачем прибивать гвоздями классы к их отражению в виде enum - разве что вам очень сильно хочется вынести это в constexpr
    В своей реализации я вынес этот "айди" класса в статический член, который генерирует новый айди для каждого класса, и делает это при запуске программы - автоматически, конечно
    В итоге всё работает только на виртуальных методах без хранимого объекта айдишника вообще, и при этом очень легко расширяемо - нужно только добавить макрос в класс, примерно как в qt


    1. fk0
      15.10.2022 17:18

      "На виртуальных методах"... Тогда проще RTTI?


      1. n0lavar
        15.10.2022 17:22

        Вы имеете в виду производительность? Нет. RTTI зачастую вообще реализуется через сравнение строк (названий классов), оверхед использования vtable по сравнению с этим - пыль.


        1. fk0
          16.10.2022 01:23

          Зачем сравнивать строки, чем это поможет? Для dynamic_cast нужно получить указатель на истиное начало класса в памяти, обладая указателем на какой-то базовый класс. И так же знать оффсеты производных классов относительно базового. И эта информация должна быть доступна в момент исполнения. Следовательно, она хранится в каких-то структурах, на которые в конечном счёте имеется ссылка из каждой таблицы виртуальных функций реализуемых данным классом. Как я понимаю. Остальное детали. Возможно в этом алгоритме и есть какая-то итерация по спискам, вызывающая замедление для 100500 раз переунаследованных классов, но уж сравнение строк точно ни за чем и типичном случае там алгоритмическая сложность не зашкаливающая.

          Речь скорей о динамических библиотеках, где проверить на совпадение типов через сравнение ссылок на std::type_info нельзя, и приходится сравнивать сами std::type_info по-значению, что заканчивается strcmp. Да, вот она плата за универсальность. В принципе такая-же проблема постигнет любой "самодельный RTTI" как дойдёт до динамических библиотек (нет возможности назначить какой-то числовой идентификатор известный в двух разных библиотеках, например, так как одна о другой может быть вовсе не в курсе).

          Но в любом случае, оно делается не какое-то безумное число раз, а как я понимаю, пробегает по списку реализуемых классом таблиц виртуальных функций и для каждой выполняет сравнение. Это единичные вызовы strcmp. И это тоже "пыль". Куда больший эффект дадут промахи кеша и то, что вызываемая из dynamic_cast функция не просматриваются компилятором в момент компиляции, что фактически ломает работу оптимизатора в этой точке.


          1. n0lavar
            16.10.2022 10:21

            Да, я имел в виду именно проблему с динамическими библиотеками

            Честно говоря, я сам не копал так глубоко, чтобы самостоятельно ковырять все компиляторы и пилить бенчмарки, но читал некоторые статьи, плюс видел, что на каждом моём месте работы (геймдев) была своя похожая замена RTTI, в т.ч. это UE.

            Конечно, возможно, что все эти люди и замеры неправы, а рандомный чел из инета - прав, но что то я сомневаюсь =)


  1. bfDeveloper
    13.10.2022 12:14
    +3

    Есть и другое решение вопроса производительности - кэш. Мы реализовали банальный map по typeid и это стало тоже в разы быстрее. Да, всё ещё требует rtti, зато работает с любыми наследованиями (множественным виртуальным), не требует модификации базового класса и тд. https://github.com/CrazyPandaLimited/panda-lib/blob/master/clib/src/panda/cast.h


  1. Antoshink
    14.10.2022 14:04

    Поиск красивых решений для конструкций, которые в чистом коде(да вообще в любом) в принципе не должны использоваться, это по нашему. Может проще реализовывать структуру объектов которая не требует кастовать.


  1. fk0
    15.10.2022 17:21

    Можно пойти немного дальше и носить в классе не enum, а референс на некую static const структуру описывающую свойства конкретного класса. Но фактически это получается таблица виртуальных функций сделанная вручную. И там могут быть конструкторы копирования, перемещения и т.п., информация и размере/выравнивании класса и т.п.

    Такой подход может дать какой-то прирост производительности, т.к. оптимизатор может заглянуть в каждую функцию, если конечно весь код в хедерах, и выбрать сразу нужную и заинлайнить.


  1. fk0
    15.10.2022 17:30

    Возможно вы боретесь с ветряными мельницами и стоило бы разобраться дальше. Во-первых из ваших же бенчмарков для крупных проектов следует, что избегание dynamic_cast ничего толком особо не ускоряет. А отказ от dynamic_cast ускоряет только ваш конкретный случай. И вполне возможном что дело в самом случае. Или в исключениях, т.к. dynamic_cast подразумевает последние. И непонятно каким образом они обрабатываются компилятором в вашем случае, насколько "бесплатно". Может вовсе и не бесплано.

    Или помимо dynamic_cast у вас меняется что-то ещё, например, происходит отказ от виртуальных функций, что существенно влияет на работу оптимизатора (который не может заглянуть в тело виртуальной функции).