靜態多態性與升壓變體單個訪問者VS多訪問者VS動態多態性

Question

我比較C++多態性下列方法的性能：

方法[1]。靜態多態性使用推進變體與每個方法的獨立訪問者 方法[2]。靜態多態性使用助推變體與單個訪問者使用方法重載調用不同的方法 方法[3]。普通的舊動態多態性

平臺： - 英特爾x86的64位紅帽現代的多核心處理器，32 GB RAM - 海灣合作委員會（GCC）4.8.1與-02優化 - 升壓1.6.0

一些研究結果：

• 方法[1]似乎有顯著跑贏方法[2]和[3]
• 方法[3]優於方法[2]的大部分時間

我的問題是，爲什麼方法[2]我使用訪客，但使用方法重載來調用正確的方法比虛擬方法的性能更差。我希望靜態多態性比動態多態性更好。據我所知，在方法[2]中傳遞的額外參數的一些代價是要調用要調用的類的哪個visit（）方法，以及可能由於方法重載而引起的更多分支？但是，不應該「牛逼這仍然跑贏大盤虛方法

代碼如下：？

// qcpptest.hpp 

#ifndef INCLUDED_QCPPTEST_H 
#define INCLUDED_QCPPTEST_H 

#include <boost/variant.hpp> 

class IShape { 
public: 
    virtual void rotate() = 0; 
    virtual void spin() = 0; 
}; 

class Square : public IShape { 
public: 
    void rotate() { 
    // std::cout << "Square:I am rotating" << std::endl; 
    } 
    void spin() { 
    // std::cout << "Square:I am spinning" << std::endl; 
    } 
}; 

class Circle : public IShape { 
public: 
    void rotate() { 
    // std::cout << "Circle:I am rotating" << std::endl; 
    } 
    void spin() { 
    // std::cout << "Circle:I am spinning" << std::endl; 
} 
}; 

// template variation 

// enum class M {ADD, DEL}; 
struct ADD {}; 
struct DEL {}; 

class TSquare { 
    int i; 
public: 
    void visit(const ADD& add) { 
     this->i++; 
    // std::cout << "TSquare:I am rotating" << std::endl; 
    } 
    void visit(const DEL& del) { 
     this->i++; 
    // std::cout << "TSquare:I am spinning" << std::endl; 
    } 

    void spin() { 
     this->i++; 
    // std::cout << "TSquare:I am rotating" << std::endl; 
} 
    void rotate() { 
     this->i++; 
    // std::cout << "TSquare:I am spinning" << std::endl; 
} 
}; 

class TCircle { 
    int i; 
public: 
    void visit(const ADD& add) { 
     this->i++; 
    // std::cout << "TCircle:I am rotating" << std::endl; 
    } 
    void visit(const DEL& del) { 
     this->i++; 
    // std::cout << "TCircle:I am spinning" << std::endl; 
    } 
    void spin() { 
     this->i++; 
     // std::cout << "TSquare:I am rotating" << std::endl; 
    } 
    void rotate() { 
    this->i++; 
     // std::cout << "TSquare:I am spinning" << std::endl; 
    } 
}; 

class MultiVisitor : public boost::static_visitor<void> { 
public: 
    template <typename T, typename U> 

    void operator()(T& t, const U& u) { 
    // std::cout << "visit" << std::endl; 
    t.visit(u); 
    } 
}; 

// separate visitors, single dispatch 

class RotateVisitor : public boost::static_visitor<void> { 
public: 
    template <class T> 
    void operator()(T& x) { 
    x.rotate(); 
    } 
}; 

class SpinVisitor : public boost::static_visitor<void> { 
public: 
    template <class T> 
    void operator()(T& x) { 
    x.spin(); 
    } 
}; 

#endif 

// qcpptest.cpp 

#include <iostream> 
#include "qcpptest.hpp" 
#include <vector> 
#include <boost/chrono.hpp> 

using MV = boost::variant<ADD, DEL>; 
// MV const add = M::ADD; 
// MV const del = M::DEL; 
static MV const add = ADD(); 
static MV const del = DEL(); 

void make_virtual_shapes(int iters) { 
    // std::cout << "make_virtual_shapes" << std::endl; 
    std::vector<IShape*> shapes; 
    shapes.push_back(new Square()); 
    shapes.push_back(new Circle()); 

    boost::chrono::high_resolution_clock::time_point start = 
     boost::chrono::high_resolution_clock::now(); 

    for (int i = 0; i < iters; i++) { 
    for (IShape* shape : shapes) { 
     shape->rotate(); 
     shape->spin(); 
    } 
    } 

    boost::chrono::nanoseconds nanos = 
     boost::chrono::high_resolution_clock::now() - start; 
    std::cout << "make_virtual_shapes took " << nanos.count() * 1e-6 
      << " millis\n"; 
} 

void make_template_shapes(int iters) { 
    // std::cout << "make_template_shapes" << std::endl; 
    using TShapes = boost::variant<TSquare, TCircle>; 
    // using MV = boost::variant<M>; 

    // xyz 
    std::vector<TShapes> tshapes; 
    tshapes.push_back(TSquare()); 
    tshapes.push_back(TCircle()); 
    MultiVisitor mv; 

    boost::chrono::high_resolution_clock::time_point start = 
     boost::chrono::high_resolution_clock::now(); 

    for (int i = 0; i < iters; i++) { 
    for (TShapes& shape : tshapes) { 
     boost::apply_visitor(mv, shape, add); 
     boost::apply_visitor(mv, shape, del); 
     // boost::apply_visitor(sv, shape); 
    } 
    } 
    boost::chrono::nanoseconds nanos = 
     boost::chrono::high_resolution_clock::now() - start; 
    std::cout << "make_template_shapes took " << nanos.count() * 1e-6 
      << " millis\n"; 
} 

void make_template_shapes_single(int iters) { 
    // std::cout << "make_template_shapes_single" << std::endl; 
    using TShapes = boost::variant<TSquare, TCircle>; 
    // xyz 
    std::vector<TShapes> tshapes; 
    tshapes.push_back(TSquare()); 
    tshapes.push_back(TCircle()); 
    SpinVisitor sv; 
    RotateVisitor rv; 

    boost::chrono::high_resolution_clock::time_point start = 
     boost::chrono::high_resolution_clock::now(); 

    for (int i = 0; i < iters; i++) { 
    for (TShapes& shape : tshapes) { 
     boost::apply_visitor(rv, shape); 
     boost::apply_visitor(sv, shape); 
    } 
    } 
    boost::chrono::nanoseconds nanos = 
     boost::chrono::high_resolution_clock::now() - start; 
    std::cout << "make_template_shapes_single took " << nanos.count() * 1e-6 
      << " millis\n"; 
} 

int main(int argc, const char* argv[]) { 
    std::cout << "Hello, cmake" << std::endl; 

    int iters = atoi(argv[1]); 

    make_virtual_shapes(iters); 
    make_template_shapes(iters); 
    make_template_shapes_single(iters); 

    return 0; 
} 

Answer 1

方法2基本上是重新實現動態調度低效當你有：

shape->rotate(); 
shape->spin(); 

這涉及仰視但是當你有：

boost::apply_visitor(mv, shape, add); 

，大約爆炸後（假設add<>成員函數模板，這僅僅是一個reinterpret_cast不檢查）：

if (shape.which() == 0) { 
    if (add.which() == 0) { 
     mv(shape.as<TSquare&>(), add.as<ADD&>()); 
    } 
    else if (add.which() == 1) { 
     mv(shape.as<TSquare&>(), add.as<DEL&>()); 
    } 
    else { 
     // ??? 
    } 
} 
else if (shape.which() == 1) { 
    if (add.which() == 0) { 
     mv(shape.as<TCircle&>(), add.as<ADD&>()); 
    } 
    else if (add.which() == 1) { 
     mv(shape.as<TCircle&>(), add.as<DEL&>()); 
    } 
    else { 
     // ??? 
    } 
} 
else { 
    // ??? 
} 

在這裏，我們有分支機構（我們沒有方法1做一個組合爆炸），但我們實際上必須檢查每個變體的每種可能的靜態類型，以找出我們必須做的事情（我們在方法3中不必做）。而且這些分支不能被預測，因爲你每次都採用不同的分支，所以你不能通過任何類型的代碼來實現暫停。

mv()上的超載是免費的 - 這是搞清楚我們叫mv而不是。還需要注意的是，會發生基於改變或者兩軸的增量時間：

+---------------+----------------+----------------+----------+ 
|    | Method 1 | Method 2 | Method 3 | 
+---------------+----------------+----------------+----------+ 
| New Type | More Expensive | More Expensive | Free | 
| New Operation |  Free  | More Expensive | Free* | 
+---------------+----------------+----------------+----------+ 

方法1成爲上增加新的類型，因爲我們必須明確地遍歷所有的類型更加昂貴。添加新操作是免費的，因爲操作無關緊要。

方法3可以自由添加新類型並且freeish添加新操作 - 唯一的變化是增加vtable。這會由於對象大小而產生一些效果，但通常會小於類型上增加的迭代。