11891


[プログラミング言語C++ 第4版](http://www.amazon.co.jp/gp/product/4797375957)の「27.4.2
クラス階層の線形化」に、菱形継承は線形継承より遅いというような事が書かれています。

> 設計の第一歩目では、伝統的な多重継承による“ダイアモンド”型の階層だった：
[code]

>           Node <--       Expr <--       Stmt <--       Decl <--       Var
>            ^              ^              ^              ^              ^
>            |              |              |              |              |
>     impl::Node <-- impl::Expr <-- impl::Stmt <-- impl::Decl <-- impl::Var
>  
[/code]

>
>
> これでも動作したが、大きなメモリオーバヘッドが発生していた。仮想基底を移動するためのデータのために、ノードが大きくなりすぎていたからだ。さらに、各オブジェクトがもつ数多くの仮想基底への間接アクセスが多いので、プログラム動作の速度も深刻なほど低下していた（§21.3.5）。  
>  この解決策が、二つの階層を線形化することであった。それによって仮想基底が排除される：
[code]

>           Node <--       Expr <--       Stmt <--       Decl <--       Var
>                                                                        ^
>            +-----------------------------------------------------------+
>            |
>     impl::Node <-- impl::Expr <-- impl::Stmt <-- impl::Decl <-- impl::Var
>  
[/code]

中ほどに理由は書かれていますが、「21.3.5 仮想基底クラス」を読んでも、もう少し具体的にどこにどういう理由で時間がかかるのか理解できませんでした。  
（なんとなく「インターフェイスの検索と実装の検索で2回検索するから？でも1回（線形継承の場合）か2回（菱形継承の場合）の差で深刻なほど速度差があるものなのか…？」と思っていますが…）

一応以下のテストプログラムで、手元のClang 3.5.2では若干線形継承の方が速いことは確認できました。  
（手元のマシンでは`std::chrono::high_resolution_clock`でもミリ秒単位ぐらいでしか計測できませんでしたが、1000回`call_function()`をまわして4ミリ秒くらいの差しかありませんでした。）

[code]

    #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";
    }
    
[/code]

[code]

    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
    
[/code]

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


CC BY-SA 3.0
2015-06-29T02:55:23.237
11833
2015-08-24T04:41:29.450
2015-06-29T03:06:02.767
7291
7291
question
c++
菱形継承が線形継承より遅い理由は？


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

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

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


CC BY-SA 3.0
2015-06-29T23:20:57.223
11863
2015-06-29T23:20:57.223
4236
11833
answer


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

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

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

  * [Memory Layout for Multiple and Virtual Inheritance](http://www.phpcompiler.org/articles/virtualinheritance.html)
  * [Multiple Inheritance Considered Useful](http://www.drdobbs.com/cpp/multiple-inheritance-considered-useful/184402074)


CC BY-SA 3.0
2015-06-30T10:12:15.080
11891
2015-07-01T01:33:24.507
2015-07-01T01:33:24.507
49
49
11833
answer