菱形継承が線形継承より遅い理由は?
プログラミング言語C++ 第4版の「27.4.2 クラス階層の線形化」に、菱形継承は線形継承より遅いというような事が書かれています。
設計の第一歩目では、伝統的な多重継承による“ダイアモンド”型の階層だった:
Node <-- Expr <-- Stmt <-- Decl <-- Var ^ ^ ^ ^ ^ | | | | | impl::Node <-- impl::Expr <-- impl::Stmt <-- impl::Decl <-- impl::Var
これでも動作したが、大きなメモリオーバヘッドが発生していた。仮想基底を移動するためのデータのために、ノードが大きくなりすぎていたからだ。さらに、各オブジェクトがもつ数多くの仮想基底への間接アクセスが多いので、プログラム動作の速度も深刻なほど低下していた(§21.3.5)。
この解決策が、二つの階層を線形化することであった。それによって仮想基底が排除される:Node <-- Expr <-- Stmt <-- Decl <-- Var ^ +-----------------------------------------------------------+ | impl::Node <-- impl::Expr <-- impl::Stmt <-- impl::Decl <-- impl::Var
中ほどに理由は書かれていますが、「21.3.5 仮想基底クラス」を読んでも、もう少し具体的にどこにどういう理由で時間がかかるのか理解できませんでした。
(なんとなく「インターフェイスの検索と実装の検索で2回検索するから?でも1回(線形継承の場合)か2回(菱形継承の場合)の差で深刻なほど速度差があるものなのか…?」と思っていますが…)
一応以下のテストプログラムで、手元のClang 3.5.2では若干線形継承の方が速いことは確認できました。
(手元のマシンではstd::chrono::high_resolution_clock
でもミリ秒単位ぐらいでしか計測できませんでしたが、1000回call_function()
をまわして4ミリ秒くらいの差しかありませんでした。)
#include <chrono>
#include <iomanip>
#include <iostream>
#include <memory>
#include <string>
#include <type_traits>
#include <sstream>
using namespace std;
using namespace std::chrono;
#ifdef DIAMOND_INHERITANCE
// 菱形継承
template<size_t N>
struct Interface: virtual Interface<N - 1>
{
using Interface<N - 1>::function;
virtual void function() = 0;
virtual void function(integral_constant<size_t, N>) = 0;
};
template<>
struct Interface<1>
{
virtual ~Interface() = default;
virtual void function() = 0;
virtual void function(integral_constant<size_t, 1>) = 0;
};
template<size_t N>
struct Implementation: virtual Interface<N>, Implementation<N - 1>
{
using Implementation<N - 1>::function;
void function() override {
cout << "Implementation<N>::function(): N = " << N << "\n";
}
void function(integral_constant<size_t, N>) override {
cout << "Implementation<N>::function(integral_constant<size_t, N>): N = " << N << "\n";
}
};
template<>
struct Implementation<1>: virtual Interface<1>
{
void function() override {
cout << "Implementation<N>::function(): N = " << 1 << "\n";
}
void function(integral_constant<size_t, 1>) override {
cout << "Implementation<N>::function(integral_constant<size_t, N>): N = " << 1 << "\n";
}
};
#else
// 線形継承
template<size_t N>
struct Interface: Interface<N - 1>
{
using Interface<N - 1>::function;
virtual void function() = 0;
virtual void function(integral_constant<size_t, N>) = 0;
};
template<>
struct Interface<1>
{
virtual ~Interface() = default;
virtual void function() = 0;
virtual void function(integral_constant<size_t, 1>) = 0;
};
template<size_t N, size_t MAX_N>
struct Implementation: Implementation<N - 1, MAX_N>
{
using Implementation<N - 1, MAX_N>::function;
void function() override {
cout << "Implementation<N>::function(): N = " << N << "\n";
}
void function(integral_constant<size_t, N>) override {
cout << "Implementation<N>::function(integral_constant<size_t, N>): N = " << N << "\n";
}
};
template<size_t MAX_N>
struct Implementation<1, MAX_N>: Interface<MAX_N>
{
using Interface<MAX_N>::function;
void function() override {
cout << "Implementation<N>::function(): N = " << 1 << "\n";
}
void function(integral_constant<size_t, 1>) override {
cout << "Implementation<N>::function(integral_constant<size_t, N>): N = " << 1 << "\n";
}
};
#endif
template<size_t N>
void call_function(Interface<1> *obj)
{
obj->function();
dynamic_cast<Interface<N> *>(obj)->function(integral_constant<size_t, N>{});
if ( N > 1 ) call_function<N - 1>(obj);
}
template<>
void call_function<0>(Interface<1> *obj) {}
int main(int argc, char *argv[])
{
if ( argc < 2 ) return 1;
istringstream is{argv[1]};
size_t loop;
is >> loop;
constexpr std::size_t n{10};
unique_ptr<Interface<1>> obj{
#ifdef DIAMOND_INHERITANCE
new Implementation<n>
#else
new Implementation<n, n>
#endif
};
using clock = high_resolution_clock;
const auto tp1 = clock::now();
for ( std::size_t i{0}; i < loop; ++i ) {
call_function<n>(obj.get());
}
const auto tp2 = clock::now();
cerr << duration_cast<microseconds>(tp2 - tp1).count() << "us\n";
}
clang++ -Wall -std=c++11 test_inheritance.cpp -DDIAMOND_INHERITANCE
./a.out 1000 > /dev/null
20001us
clang++ -Wall -std=c++11 test_inheritance.cpp
./a.out 1000 > /dev/null
16001us
もう少し具体的にどこにどういう理由で時間がかかるのでしょうか?