c++ - 具有 boost 变体的静态多态性单访问者与多访问者与动态多态性

Question

我正在比较以下 C++ 多态性方法的性能:

方法[1]。使用 boost 变体的静态多态性，每个方法都有一个单独的访问者方法[2]。使用 boost 变体的静态多态性，单个访问者使用方法重载调用不同的方法方法[3]。普通的旧动态多态性

平台:- Intel x86 64 位 Red Hat 现代多核处理器，32 GB RAM- gcc (GCC) 4.8.1 与 -O2 优化- boost 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();

这涉及在 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 的增加。由于对象大小，这会产生一些影响，但通常会小于对类型增加的迭代。