dynamic_cast と独自実装動的 cast の比較

ふと。
`dynamic_cast` って遅いと言われているけどどれくらい遅いんだろうと思って調べてみた。

# 調べ方

## クラス階層

こんな階層でクラスをたくさん作った。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/6854/c0effa4a-7332-5d83-69fa-a8446ee14476.png)

## 実装内容

1. 上記のクラスで、派生クラスを持たないものをランダムに 100万個 選んで、その型のインスタンスへのポインタを `root` へのポインタ型を要素とする vector に突っ込む。
2. 100万回ループを回し、「要素が `mammal` なら、 `mammal_proc` を呼ぶ」「要素が `bird` なら、 `bird_proc` を呼ぶ」を実施する。
3. (2) に要した時間を測る

という感じ。「要素が `mammal` なら」の部分で `dynamic_cast` を使うものと、独自実装の `animal_cast` を使うかでどれだけ違うか調べる。

どこの馬の骨ともわからないクラスに対しても使える `dynamic_cast` と、 `root` の派生クラスでしか使えない `animal_cast` ではまあ条件が違うので公平とは言えないけれど、実用的には意味があるかなと思う。

### ソースコード

ちょっと長いけどこんな感じ。
邪悪なマクロで行数を減らしてみたけど。

```c++:c++17
#include <array>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>
#include <type_traits>
using namespace std;
using namespace std::chrono;

// define class
#define DERIVE(base, derived, num)                                             \
  class derived : public base {                                                \
    int derived_##member;                                                      \
                                                                               \
  public:                                                                      \
    static inline constexpr int tid = num;                                     \
    derived() : derived_##member(0) {}                                         \
    int m() const { return derived_##member; }                                 \
    int derived##_proc() const { return num; };                                \
    bool is_a(int t) const override { return t == tid || base::is_a(t); }      \
  };

class root {
public:
  virtual ~root() {}
  virtual bool is_a(int t) const { return false; }
};

DERIVE(root, vertebrate, __LINE__)
DERIVE(vertebrate, fish, __LINE__)
DERIVE(fish, amphibian, __LINE__)
DERIVE(fish, shark, __LINE__)
DERIVE(fish, tuna, __LINE__)
DERIVE(amphibian, reptile, __LINE__)
DERIVE(amphibian, newt, __LINE__)
DERIVE(amphibian, frog, __LINE__)
DERIVE(reptile, mammal, __LINE__)
DERIVE(reptile, crocodile, __LINE__)
DERIVE(reptile, snake, __LINE__)
DERIVE(mammal, monkey, __LINE__)
DERIVE(monkey, aye_aye, __LINE__)
DERIVE(monkey, tamarin, __LINE__)
DERIVE(monkey, hominidae, __LINE__)
DERIVE(hominidae, gorilla, __LINE__)
DERIVE(hominidae, human, __LINE__)
DERIVE(mammal, whale, __LINE__)
DERIVE(whale, blue_whale, __LINE__)
DERIVE(whale, narwhal, __LINE__)
DERIVE(whale, sperm_whale, __LINE__)
DERIVE(reptile, bird, __LINE__)
DERIVE(bird, penguin, __LINE__)
DERIVE(penguin, king_penguin, __LINE__)
DERIVE(penguin, magellanic_penguin, __LINE__)
DERIVE(penguin, galapagos_penguin, __LINE__)
DERIVE(bird, sparrow, __LINE__)

constexpr size_t COUNT = 1'000'000;

std::function<root *()> newAnimals[] = {
    []() -> root * { return new shark(); },
    []() -> root * { return new tuna(); },
    []() -> root * { return new newt(); },
    []() -> root * { return new frog(); },
    []() -> root * { return new crocodile(); },
    []() -> root * { return new snake(); },
    []() -> root * { return new aye_aye(); },
    []() -> root * { return new tamarin(); },
    []() -> root * { return new gorilla(); },
    []() -> root * { return new human(); },
    []() -> root * { return new blue_whale(); },
    []() -> root * { return new narwhal(); },
    []() -> root * { return new sperm_whale(); },
    []() -> root * { return new king_penguin(); },
    []() -> root * { return new magellanic_penguin(); },
    []() -> root * { return new galapagos_penguin(); },
    []() -> root * { return new sparrow(); },
};

constexpr size_t newAnimalsCount = sizeof(newAnimals) / sizeof(*newAnimals);

int dynamic_run(std::array<root *, COUNT> const &m) {
  int sum = 0;
  for (auto const &e : m) {
    if (auto p = dynamic_cast<mammal const *>(e)) {
      sum += p->mammal_proc();
    }
    if (auto p = dynamic_cast<bird const *>(e)) {
      sum += p->bird_proc();
    }
  }
  return sum;
}

template <typename cast> //
inline cast animal_cast(root *p) {
  if (p->is_a(std::remove_pointer<cast>::type::tid)) {
    return static_cast<cast>(p);
  }
  return nullptr;
}

template <typename cast> //
inline cast animal_cast(root const *p) {
  if (p->is_a(std::remove_pointer<cast>::type::tid)) {
    return static_cast<cast>(p);
  }
  return nullptr;
}

int static_run(std::array<root *, COUNT> const &m) {
  int sum = 0;
  for (auto const &e : m) {
    if (auto p = animal_cast<mammal const *>(e)) {
      sum += p->mammal_proc();
    }
    if (auto p = animal_cast<bird const *>(e)) {
      sum += p->bird_proc();
    }
  }
  return sum;
}

void run(char const *title, decltype(dynamic_run) runner,
         std::array<root *, COUNT> const &m, bool production) {
  auto start = high_resolution_clock::now();
  auto r = runner(m);
  auto end = high_resolution_clock::now();
  if (production) {
    std::cout << title
              << "\n"
                 "  res="
              << r
              << "\n"
                 "  "
              << duration_cast<microseconds>(end - start).count() * 1e-3
              << "ms\n";
  }
}

void test(int num) {
  std::array<root *, COUNT> m = {0};
  std::mt19937_64 rng(num);
  std::uniform_int_distribution<size_t> dist(0, newAnimalsCount - 1);
  for (auto &e : m) {
    e = newAnimals[dist(rng)]();
  }
  for (int i = 0; i < 3; ++i) {
    run("dynamic_cast", dynamic_run, m, 2 <= i);
    run("animal_cast", static_run, m, 2 <= i);
  }
}

int main(int argc, char const *argv[]) {
  test(argc < 2 ? 0 : std::atoi(argv[1]));
}
```

## animal_cast の実装方針

`animal_cast<cast_to*>(obj)` は、 `obj->is_a(cast_to::tid)` を呼んで型を判定している。

`someclass::is_a(int t)` は
* `t` が自分の型の IDと等しければ `true`
* そうでない場合、基底クラスの `is_a(t)` を返す
というもの。

この作戦なら、クラスの数がかなり多くてもうまくいく。ユニークな ID をふるのがやや面倒(上記実装では行番号を利用した)だと思う。

一方。
* 階層が深いと遅くなる
* テンプレートクラスの `tid` を定義するのが面倒
* 多重継承があり、同一クラスが基底クラスに複数ある場合には、このままじゃまずいかも
という問題がある。

クラスの数があまり多くないとわかっているのならビット列( `uint64_t` とか、 `std::bitset` とか)を使う作戦もある。そうすればもっと速くなりそうだけど、やや面倒かもしれない。

# 結果

出力はこんな感じ：

```text:clang++
dynamic_cast
  res=26968719
  62.675ms
animal_cast
  res=26968719
  16.898ms
```

```text:g++-9
dynamic_cast
  res=26983434
  100.508ms
animal_cast
  res=26983434
  19.291ms
```

表にすると以下の通り:

|処理系|dynamic_cast|animal_cast|比率|
|:--|:--|:--|:--|
|clang++|62.675ms|16.898ms|3.7倍|
|g++-9|100.508ms|19.291ms|5.2倍|

というわけで、 `animal_cast` が数倍速いという結果になった。

というわけで、`dynamic_cast` の時間が気になる場合、 `dynamic_cast` に相当する処理を自力で実装したほうがお得っぽい。