将unique_ptr添加到向量中的类会导致3倍的加速

Question

背景

我有一个大图(100k节点),其中每个节点必须存储每个传出边的一些信息.std::vector<bool>我没有将其保留在一个中,而是使用dynamic_bitsetBoost 1.58来执行按位操作.每个节点还保持指向某个多态对象的指针.一个最小的例子看起来像这样,

struct Node
{
    std::vector<size_t>     succ;
    boost::dynamic_bitset<> succ_flags;
    std::unique_ptr<Object> data;
};

问题

考虑这个简单的基准程序,它创建并销毁图表:

#include <vector>
#include <boost/dynamic_bitset.hpp>
#include <memory>

constexpr int N = 50000;

struct Node
{
    std::vector<size_t>     succ;
    boost::dynamic_bitset<> succ_flags;
  //std::unique_ptr<int>    data;

    Node(int i)
    {
        for (int j = i; j < N; j += i) succ.emplace_back(j);
        succ_flags.resize(succ.size());
    }
};

int main()
{
    std::vector<Node> nodes;
    for (int i = 1; i <= N; i++) nodes.emplace_back(i);
    return 0;
}

在time命令下运行,典型的结果是

real    0m0.055s
user    0m0.043s
sys     0m0.010s

但是,取消注释该unique_ptr行会更像

real    0m0.017s
user    0m0.010s
sys     0m0.003s

结论:Node通过添加std::unique_ptr数据成员使重量增加导致std::vector执行速度提高3倍以上!

题

为什么会发生这种情况,这里有什么样的问题？

Answer 1

添加unique_ptr数据成员Node将生成仅移动类型,并且vector在增大其大小时强制移动现有元素.在您的原始示例中,vector是复制现有元素,因为默认的移动构造函数定义不是noexcept(因为dynamic_bitset移动构造函数不是noexcept).

您应该能够在不添加unique_ptr以下两种方式之一的情况下重现更快的结果:

reserve 在房间里 vector

std::vector<Node> nodes;
nodes.reserve(N);

或定义自己的noexcept移动构造函数Node

Node(Node&& other) noexcept
: succ(std::move(other.succ))
, succ_flags(std::move(other.succ_flags))
{}

注意,如果你提供上面的移动构造函数并且dynamic_bitset移动构造函数实际抛出异常,std::terminate则会被调用.