c++ 具有std::变体性能的多态性

zdwk9cvp  于 2023-03-05  发布在  其他
关注(0)|答案(1)|浏览(155)

通过在std::variant中仔细观察__do_visit,我对std::variant多态方法的性能产生了好奇心
我编写了一个小型测试程序,比较旧式继承和std::variant继承

#include <variant>
#include <vector>
#include <iostream>
#include <string>
#include <chrono>

int i = 0;
// Polymorphism using variants
class circle
{
  public:
    void draw() const { i++; }
};

class line
{
  public:
    void draw() const { i++; }
};
using v_t  = std::variant<circle, line>;

void variant_way(const std::vector<v_t>& v)
{
  for (const auto &var : v)
    std::visit([](const auto& o) {
        o.draw();
        }, var);
}

// old school
class shape
{
  public:
    virtual void draw() const = 0;
    virtual ~shape() { }
};
class circle_in : public shape
{
  public:
    virtual void draw() const { i++; }
};

class line_in : public shape
{
  public:
   virtual void draw() const { i++; }
};

void inherit_way(const std::vector<shape*>& v)
{
  for (const auto var : v)
        var->draw();
}

// call and measure
template <typename F, typename D>
void run(F f, const D& data, std::string name)
{
  auto start = std::chrono::high_resolution_clock::now();
  f(data);
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
  std::cout << name << ": "<< elapsed.count() << std::endl;
}

int main()
{
  constexpr int howmany = 100000;
  {
    std::vector<v_t> v {howmany};
    run(variant_way, v, "variant");
  }
  {
    std::vector<shape*> v;
    for (int i = 0; i < howmany; i++)
      v.push_back(new circle_in());
    run(inherit_way, v, "inherit_way");
    // deallocate
  }
  return 0;
}

在我的机器(i7,16GB RAM)上,我得到了以下结果:

variant: 7487
inherit_way: 1302

我怀疑这个结果反映了std::variant方法在每次迭代时都会创建vtable,而继承方法只做一次。
这个解释对吗?
有没有办法减少开销?

htrmnn0y

htrmnn0y1#

这个问题有几点是错误的;从技术上讲,这不一定是一个答案,但我认为它提供了一些有益的思考。
首先,多态类和类型联合体(变体)中的类型都没有数据,因此这些类型的大小对于非OOP "plain old data"类型是1字节,对于OOPy类型是8字节。
至少要构造一个合理的示例,您必须实际上使类型保留一些数据;如果不是,那又有什么意义呢?你并不是在衡量你认为你在衡量的东西。
例如:在没有优化的情况下运行此示例,得到的结果与您在此处提供的结果相同。
但是突然用clang++ -std=c++20 -O3编译,结果却大大地偏向了std::variant

variant: 0
inherit_way: 167

我敢打赌,编译器足够聪明,能够看到,变体case只是一个元素向量,大小为1字节,但值永远不会改变,完全优化了它,因为POD类型的成员函数只是递增一个全局变量,它永远不会被读取,它实际上什么也不用做,所以结果是0。
下面是一个更好的"示例问题"--虽然同样是人为设计的问题,但它实际上花了时间来衡量我认为你实际上在追求什么。

#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <random>
#include <string>
#include <type_traits>
#include <variant>
#include <vector>

int i = 0;
using u64 = std::uint64_t;

static constexpr auto PI = 3.14;

// ignore this, if you don't understand it
template <class... T> constexpr bool always_false = false;

struct point {
  u64 x;
  u64 y;
};

// some imaginary call to an internal rendering function, returning pixels
// written
inline constexpr auto internal_circle_render(auto xrad, auto yrad) {
  return PI * xrad * yrad;
}

// some imaginary call to an internal rendering function, returning pixels
// written
inline constexpr auto internal_line_render(auto width, point p1, point p2) {
  return std::sqrt(std::pow((p2.x - p1.x), 2) + std::pow((p2.y - p1.y), 2)) *
         width;
}

// POD for the win
struct circle {
  u64 xrad;
  u64 yrad;
  point center;
};

struct line {
  point a;
  point b;
  u64 width;
};

template <typename T> constexpr inline auto render_shape(T &&shape) -> u64 {
  using type = std::decay_t<T>;
  if constexpr (std::is_same_v<type, line>) {
    return internal_line_render(shape.width, shape.a, shape.b);
  } else if constexpr (std::is_same_v<type, circle>) {
    return internal_circle_render(shape.xrad, shape.yrad);
  } else {
    static_assert(always_false<T>, "unknown type");
  }
}

using v_t = std::variant<circle, line>;
auto variant_way(const std::vector<v_t> &v) {
  auto total_pixels = 0;
  for (const auto &var : v)
    total_pixels += std::visit(
        [](const auto &shape) -> u64 { return render_shape(shape); }, var);
  return total_pixels;
}

// old school
class shape {
public:
  shape() = default;
  virtual ~shape() = default;
  virtual u64 render_pixels() const = 0;
};

class circle_in : public shape {
public:
  circle_in(u64 xrad, u64 yrad, point center)
      : shape(), xrad(xrad), yrad(yrad), center(center) {}
  ~circle_in() override = default;

  virtual u64 render_pixels() const override {
    return internal_circle_render(xrad, yrad);
  }

private:
  u64 xrad;
  u64 yrad;
  point center;
};

class line_in : public shape {
public:
  line_in(point a, point b, u64 width) : shape(), a(a), b(b), width(width) {}
  ~line_in() override = default;

  virtual u64 render_pixels() const override {
    return internal_line_render(width, a, b);
  }

private:
  point a;
  point b;
  u64 width;
};

auto inherit_way(const std::vector<shape *> &v) {
  auto total_pixels = 0;
  for (const auto var : v)
    total_pixels += var->render_pixels();
  return total_pixels;
}

// call and measure
template <typename F, typename D>
void run(F f, const D &data, std::string name) {
  auto start = std::chrono::high_resolution_clock::now();
  auto pixels = f(data);
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed =
      std::chrono::duration_cast<std::chrono::microseconds>(end - start);
  std::cout << name << ": " << elapsed.count() << " " << pixels << " pixels "
            << std::endl;
}

constexpr auto howmany = 100000;

// contrived "random" data
inline std::vector<v_t> create_variant_data() {
  std::vector<v_t> data;
  data.reserve(howmany);
  for (u64 i = 0; i < howmany; i++) {
    switch (i % 2) {
    case 0: {
      const auto a = point{.x = 1 + i % 10, .y = 1 + i % 10};
      const auto b = point{.x = 2 + i % 20, .y = 2 + i % 20};
      data.emplace_back(line{.a = a, .b = b, .width = i % 25});
    } break;
    case 1: {
      data.emplace_back(
          circle{.xrad = i % 10, .yrad = i % 20, .center = {.x = i, .y = i}});
    } break;
    }
  }
  return data;
}

// contrived "random" data
inline std::vector<shape *> create_oop_data() {
  std::vector<shape *> data;
  data.reserve(howmany);
  for (u64 i = 0; i < howmany; i++) {
    switch (i % 2) {
    case 0: {
      const auto a = point{.x = 1 + i % 10, .y = 1 + i % 10};
      const auto b = point{.x = 2 + i % 20, .y = 2 + i % 20};
      data.push_back(new line_in{a, b, i % 25});
    } break;
    case 1: {
      data.push_back(new circle_in{i % 10, i % 20, {.x = i, .y = i}});
    } break;
    }
  }
  return data;
}

int main() {
  auto rng = std::default_random_engine{};
  {
    std::vector<v_t> v = create_variant_data();
    // we definitely want to shuffle, otherwise CPU predictors are going to
    // outsmart us and give us falsy results
    std::shuffle(v.begin(), v.end(), rng);
    run(variant_way, v, "variant");
  }
  {
    std::vector<shape *> v = create_oop_data();
    // we definitely want to shuffle, otherwise CPU predictors are going to
    // outsmart us and give us falsy results
    std::shuffle(v.begin(), v.end(), rng);
    run(inherit_way, v, "inherit_way");
  }
  return 0;
}

使用clang++ -std=c++20 -O3或gcc等效项编译该代码,现在会产生如下结果

variant: 478 14148000 pixels 
inherit_way: 933 14148000 pixels

其中inherit_way的波动速度比std::variant慢3.5倍。我怀疑这与shuffle最终的有利程度有关。然而,std::variant从未显示过这种大的波动。因此,公平地说,对于像这样简单的东西,std::variant的性能远远优于OOP。
但是在编写这样的"基准测试"时必须非常小心,因为即使在我的例子中,我也很确定我错过了大量的事情,这些事情最终导致了结果的误导。例如,如果不对保存数据的向量进行 Shuffle ,突然OOP版本以微小的优势获胜,这是由于(可能)CPU能够推测:嘿,每一个其他的虚拟调用间接都以极高的确定性到达这个特定的地址,但是现实世界中的数据最终是这样布局的(顺便说一句,如果你知道数据是这样布局的,你甚至不会在这里使用std::variant,只使用2个向量,一个保存line,一个保存circle)。
对于这个人为的例子,std::variant比OOP方法快得多的原因之一与间接有关。对于std::vector<shape*>的每个元素,至少有2个间接查找。一个用于元素的指针,一个用于虚拟表查找,而对于std::variant,每个元素在向量中连续地布局。使用缓存和"we"本质上只是对某个类型值执行switch操作,然后根据类型调用正确的函数,正如结果所示,这比虚拟调用快得多。

相关问题