Đa hình tĩnh với biến thể tăng khách truy cập đơn so với đa khách truy cập và đa hình động

Question

Tôi đang so sánh hiệu suất của các phương pháp đa hình C++ sau đây:

Phương pháp [1]. tính đa hình tĩnh sử dụng các biến thể tăng cường với khách truy cập riêng cho từng phương thức Phương pháp [2]. tính đa hình tĩnh sử dụng các biến thể tăng cường với một khách truy cập duy nhất gọi phương thức khác nhau bằng cách sử dụng phương thức nạp chồng Phương pháp [3]. Plain đa hình động cũ

Hệ điều hành: - Intel x86 64 bit Red Hat hiện đại xử lý đa lõi, 32 GB RAM - gcc (GCC) 4.8.1 với -O2 tối ưu hóa - Tăng 1.6.0

một số kết quả:

• Phương pháp [1] dường như có phương pháp làm tốt hơn đáng kể [2] và [3]
• Phương pháp [3] nhanh hơn so với phương pháp [2] hầu hết thời gian

Câu hỏi của tôi là, tại sao Phương pháp [2] nơi tôi đang sử dụng khách truy cập nhưng sử dụng phương thức nạp chồng để gọi phương thức đúng cho hiệu suất kém hơn các phương pháp ảo. Tôi mong đợi tính đa hình tĩnh để giá vé tốt hơn so với đa hình năng động. Tôi hiểu có một số chi phí của tham số bổ sung đang được thông qua trong phương pháp [2] để tìm ra phương thức visit() nào của lớp để gọi và có thể một số phân nhánh khác do quá tải phương thức? Nhưng shouldn "t này vẫn tốt hơn phương pháp ảo

Mã là dưới đây:?.

// 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

Cách 2 là cơ bản reimplementing cử động không hiệu quả Khi bạn có:

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

Đó là liên quan đến việc tìm kiếm lên đúng chức năng trong vtable và gọi nó.Không hiệu quả từ tra cứu đó.Nhưng khi bạn có:

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

Đó phát nổ gần thành (giả định một chức năng add<> viên mẫu mà chỉ là một reinterpret_cast mà không kiểm tra):

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 { 
    // ??? 
} 

Ở đây, chúng ta có một sự bùng nổ tổ hợp các chi nhánh (mà chúng ta không cần phải làm gì trong Phương pháp 1) nhưng chúng tôi thực sự phải kiểm tra mọi loại tĩnh có thể có của mỗi biến thể để tìm ra những gì chúng tôi phải làm (mà chúng tôi không phải thực hiện trong Phương pháp 3). Và những nhánh đó sẽ không thể dự đoán được vì bạn đang sử dụng một cái khác nhau mỗi lần, vì vậy bạn không thể dẫn đường bất kỳ loại mã nào mà không phải dừng lại.

Quá tải trên mv() là miễn phí - đó là tìm ra những gì chúng tôi đang gọi mv với điều đó là không. Cũng lưu ý rằng thời gian delta sẽ xảy ra dựa trên việc thay đổi một trong hai trục:

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

Phương pháp 1 trở nên đắt hơn khi thêm loại mới vì chúng tôi phải lặp lại rõ ràng trên tất cả các loại của chúng tôi. Thêm hoạt động mới là miễn phí vì nó không quan trọng hoạt động là gì.

Phương pháp 3 là miễn phí để thêm các loại mới và miễn phí để thêm hoạt động mới - thay đổi duy nhất là tăng trong vtable. Điều đó sẽ có một số hiệu ứng do kích thước đối tượng nhưng nhìn chung sẽ nhỏ hơn so với lặp lại tăng trên các loại.