LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@Nabetani(鍋谷 武典)

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

Posted at

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

調べ方

クラス階層

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

image.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++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 とか)を使う作戦もある。そうすればもっと速くなりそうだけど、やや面倒かもしれない。

結果

出力はこんな感じ：

clang++
dynamic_cast
  res=26968719
  62.675ms
animal_cast
  res=26968719
  16.898ms
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 に相当する処理を自力で実装したほうがお得っぽい。

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?