Adding a unique_ptr to a class in a vector results in 3x speedup

Question

Background

I have a large graph (100k nodes), in which each node has to store a bit of information per outgoing edge. Instead of keeping this in a std::vector<bool>, I'm using dynamic_bitset from Boost 1.58 for the ability to perform bitwise operations. Each node also keeps a pointer to some polymorphic object. A minimal example looks like this,

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

Problem

Consider this simple benchmark program, which creates and destroys a graph:

#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;
}

Running under the time command, a typical result is

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

However, uncommenting the unique_ptr line gives something more like

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

Conclusion: making Node heavier by adding a std::unique_ptr data member causes std::vector to perform over 3x faster!

Question

Why is this happening, and what sort of gotcha is at work here?

Answer 1

Adding the unique_ptr data member makes Node a move-only type and the vector is forced to move the existing elements when growing its size. In your original example, the vector is copying the existing elements because the default move constructor definition is not noexcept (because the dynamic_bitset move constructor is not noexcept).

You should be able to reproduce the quicker result without adding the unique_ptr in one of the following two ways:

reserve room in the vector

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

or define your own noexcept move constructor for Node

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

Note that if you provide the above move constructor and dynamic_bitset's move constructor actually throws an exception, std::terminate will be called.