9

プログラミング言語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

もう少し具体的にどこにどういう理由で時間がかかるのでしょうか?

5
  • 深い階層のデータ使ってる?ように私には見えなかった。
    – さささ
    Commented 2015年6月29日 18:30
  • 1
    上記の例だと、coutへの出力が(/dev/nullにリダイレクトしているとは言っても)重すぎるので、菱型継承のパフォーマンスへの影響が見えにくくなっているのではないでしょうか。試しにcoutへの出力をコメントアウトしてみたところ、私の環境では、菱型継承では5,000us程度なのに対し、線形継承では1,500us程度と、明確に差が出ました。
    – snak
    Commented 2015年6月29日 23:58
  • @さささ テストプログラムの方ですか? 後で簡単に階層数を変えられるようにテンプレートで再帰的にクラスを作って、書籍から引用したクラス階層になるように継承しているつもりです。 Visual C++ 2015 RCを入手したのでIDEでオブジェクトを見てみましたが、少なくとも線形継承の方は期待通りの階層になっているように見えます。菱形継承の方は仮想継承のせいかイメージしていたのと異なる見え方ですが。
    – alpha
    Commented 2015年6月30日 3:12
  • @snak coutへの出力を削る前の時間は、私の環境と同程度たったのでしょうか? もしそうなら差は3.5ミリ秒なので、削った処理分が双方共に速くなっただけで、クラス階層の違いによる差は結局3.5~4ミリ秒程ということになると思うのですが。 call_function<>()を1,000回呼び出して4ミリ秒程の差を、若干と捉えるか深刻なほど大きいと捉えるかという感覚の違いもあるかもしれません。
    – alpha
    Commented 2015年6月30日 6:31
  • @alpha C++の設計者が、どのぐらいを深刻と捉えていたか、についてはメンバ関数のデフォルトが仮想関数でない(可能な限りvtblを作りたくない)という設計が参考になるのではないでしょうか。C言語より遅くなる or メモリ使用量が増える という事を全く許容出来なかったようです。といっても私の書いていることは「C++の設計と進化」という本の内容の劣化コピーですので、正しいことが知りたければそちらを参照してください。面白い本ですよ。
    – Lighten
    Commented 2015年7月1日 4:11

2 件の回答 2

8

仮想継承(virtual inheritance)を利用すると、C++オブジェクトを表現する仮想関数テーブル(vtbl)が複雑になるため、追加の実行時オーバーヘッドを生じます。仮想継承をどのように実現するかはC++コンパイラに依存しますが、内部処理としては同程度の操作を要求するため、どのような処理系でも同じ傾向となるはずです。

線形継承では単純で直線的なvtbl構成で済むため、キャスト処理はほぼゼロ・オーバーヘッドで行えます。一方、仮想継承を用いた場合は複雑なvtbl構成となり、キャスト処理では間接参照やオフセット再計算など追加処理が必要となります。

仮想継承とvtblの関係は、下記記事の図示などを参考にください:

2

上手く説明できませんが…

「インターフェイスの検索と実装の検索で2回検索するから?でも1回(線形継承の場合)か2回(菱形継承の場合)の差で深刻なほど速度差があるものなのか…?」

の通りです。sizeof Interface<1>sizeof Interface<10> を見るとわかりますが、virtual継承をしている菱形継承の場合はサイズが8バイトずつ増加していきます。(もちろん実装依存です。)
線形継承の場合はサイズは変わりません。

3
  • Clang 3.5.2/GCC 4.9.2では8バイト固定だったので「?」となり、 、yohjpさんにご紹介頂いたメモリーレイアウト例通りなら8バイト(ポインター2つ分)ずつ増えるはずなので「???」となり理解できずにいましたが、Visual C++ 2015 RCでは8バイトずつ増えました。線形継承の方は3つの処理系全てで4バイトと固定だったので、メモリー使用量の違いについては理解できました。
    – alpha
    Commented 2015年7月2日 1:31
  • 1
    Clang/GCC(Itanium C++ ABI)とVisualC++とではメモリレイアウトが結構違いますから、オブジェクトサイズも違う結果となりますね。例えば Bringing Clang and LLVM to Visual C++ users 21ページ目以降で違いが説明されています。
    – yohjp
    Commented 2015年7月2日 3:47
  • 1
    Clang/GCCは、非静的メンバー変数を持たない場合は(-O0を指定しても)最適化されるようで8バイト固定になりますが、非静的メンバー変数を追加すると(メンバー変数分を除いて)8バイトずつ増えていきました。
    – alpha
    Commented 2015年7月2日 10:39

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。