lundi 27 juillet 2015

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

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?

Aucun commentaire:

Enregistrer un commentaire