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