Статический полиморфизм с возможностью выбора варианта одного посетителя против нескольких посетителей и динамического полиморфизма
Я сравниваю производительность следующих методов полиморфизма С++:
Метод [1]. статический полиморфизм с использованием вариантов форсирования с отдельным посетителем для каждого метода
Метод [2]. статический полиморфизм с использованием вариантов boost с одним посетителем, который вызывает другой метод с использованием перегрузки метода
Метод [3]. Обычный статический динамический полиморфизм
Платформа:
- Intel x86 64-бит Red Hat, современный многоядерный процессор, 32 ГБ оперативной памяти
- gcc (GCC) 4.8.1 с оптимизацией -O2
- Boost 1.6.0
Некоторые выводы:
- Метод [1], по-видимому, значительно превзошел методы [2] и [3]
- Метод [3] превосходит метод [2] в большинстве случаев
Мой вопрос в том, почему метод [2], где я использую посетителя, но используя перегрузку метода для вызова правильного метода, дает худшую производительность, чем виртуальные методы. Я ожидал бы, что статический полиморфизм будет лучше, чем динамический полиморфизм. Я понимаю, что есть некоторая стоимость дополнительного параметра, который передается в методе [2], чтобы определить, какой метод посещения() класса вызывает и, возможно, еще большее разветвление из-за перегрузки метода? Но разве это не превосходит виртуальные методы?
Код ниже:
// 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;
}
Ответы
Ответ 1
Метод 2 в основном неэффективно выполняет динамическую диспетчеризацию. Когда у вас есть:
shape->rotate();
shape->spin();
Это включает поиск правильной функции в vtable и ее вызов. Неэффективность этого поиска. Но когда у вас есть:
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 может добавлять новые типы и освобождать для добавления новых операций - единственное изменение - увеличение vtable. Это будет иметь некоторые эффекты из-за размера объекта, но обычно будет меньше, чем увеличенная итерация по типам.
