Добавление unique_ptr в класс в векторе приводит к ускорению 3 раза

Фон

У меня есть большой граф (узлы 100k), в котором каждый node должен хранить бит информации на исходящий край. Вместо того, чтобы хранить это в std::vector<bool>, я использую dynamic_bitset из Boost 1.58 для возможности выполнять побитовые операции. Каждый node также сохраняет указатель на некоторый полиморфный объект. Минимальный пример выглядит так:

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 раз быстрее!

Вопрос

Почему это происходит, и какой вид работы здесь работает?

Ответы

Ответ 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))
{}

Обратите внимание, что если вы предоставили вышеперечисленный конструктор move и dynamic_bitset move constructor действительно выдает исключение, будет вызван std::terminate.