Производительность изменения размера std::vector <std:: unique_ptr <T>>

Похоже, что общая концепция заключается в том, что std::unique_ptr не требует лишних затрат времени по сравнению с правильно используемыми владельцами необработанных указателей, достаточная оптимизация.

Но как насчет использования std::unique_ptr в составных структурах данных, в частности std::vector<std::unique_ptr<T>>? Например, изменение размера базовых данных вектора, которое может произойти во время push_back. Чтобы изолировать производительность, я петлю вокруг pop_back, shrink_to_fit, emplace_back:

#include <chrono>
#include <vector>
#include <memory>
#include <iostream>

constexpr size_t size = 1000000;
constexpr size_t repeat = 1000;
using my_clock = std::chrono::high_resolution_clock;

template<class T>
auto test(std::vector<T>& v) {
    v.reserve(size);
    for (size_t i = 0; i < size; i++) {
        v.emplace_back(new int());
    }
    auto t0 = my_clock::now();
    for (int i = 0; i < repeat; i++) {
        auto back = std::move(v.back());
        v.pop_back();
        v.shrink_to_fit();
        if (back == nullptr) throw "don't optimize me away";
        v.emplace_back(std::move(back));
    }
    return my_clock::now() - t0;
}

int main() {
    std::vector<std::unique_ptr<int>> v_u;
    std::vector<int*> v_p;

    auto millis_p = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_p));
    auto millis_u = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_u));
    std::cout << "raw pointer: " << millis_p.count() << " ms, unique_ptr: " << millis_u.count() << " ms\n";
    for (auto p : v_p) delete p; // I don't like memory leaks ;-)
}

Компиляция кода с помощью -O3 -o -march=native -std=c++14 -g с gcc 7.1.0, clang 3.8.0 и 17.0.4 на Linux на Intel Xeon E5-2690 v3 @2.6 ГГц (без турбо):

raw pointer: 2746 ms, unique_ptr: 5140 ms  (gcc)
raw pointer: 2667 ms, unique_ptr: 5529 ms  (clang)
raw pointer: 1448 ms, unique_ptr: 5374 ms  (intel)

Необработанная версия указателя тратит все это время на оптимизированный memmove (у Intel, похоже, намного лучше, чем clang и gcc). Код unique_ptr, по-видимому, сначала скопирует векторные данные из одного блока памяти в другой и назначает исходный нулевой - все в ужасно не оптимизированном цикле. И затем он снова перебирает исходный блок данных, чтобы узнать, отличен ли какой-либо из тех, которые были только нулевыми, и их необходимо удалить. Полную информацию о gory можно увидеть на godbolt. Вопрос заключается не в том, как скомпилированный код отличается, что довольно ясно. Вопрос: почему компилятор не может оптимизировать то, что обычно рассматривается как абстракция без лишних затрат.

Попытка понять, как компиляторы рассуждают об обработке std::unique_ptr, я искал немного больше на изолированном коде. Например:

void foo(std::unique_ptr<int>& a, std::unique_ptr<int>& b) {
  a.release();
  a = std::move(b);
}

или аналогичный

a.release();
a.reset(b.release());

ни один из компиляторов x86 похоже, не может оптимизировать бессмысленный if (ptr) delete ptr;. Компилятор Intel даже дает возможность удалить 28%. Удивительно, что проверка удаления последовательно опущена для:

auto tmp = b.release();
a.release();
a.reset(tmp);

Эти биты не являются основным аспектом этого вопроса, но все это заставляет меня чувствовать, что я чего-то не хватает.

Почему различные компиляторы не могут оптимизировать перераспределение в std::vector<std::unique_ptr<int>>? Есть ли что-нибудь в стандарте, которое предотвращает генерацию кода так же эффективно, как с необработанными указателями? Это проблема стандартной реализации библиотеки? Или компиляторы недостаточно недостаточно умны (пока)?

Что можно сделать, чтобы избежать влияния производительности по сравнению с использованием raw-указателей?

Примечание. Предположим, что T является полиморфным и дорогим для перемещения, поэтому std::vector<T> не является вариантом.

Ответы

Ответ 1

Утверждение, что unique_ptr выполняет, а также необработанный указатель после оптимизации в основном применяется только к основным операциям с одним указателем, таким как создание, разыменование, назначение одного указателя и удаление. Эти операции определяются достаточно просто, что оптимизирующий компилятор обычно может делать необходимые преобразования таким образом, чтобы полученный код был эквивалентен (или почти так) в производительности до исходной версии 0.

Одно место, которое разваливается, - это, в первую очередь, более оптимизированная языковая оптимизация на контейнерах на основе массивов, таких как std::vector, как вы отметили в своем тесте. Эти контейнеры обычно используют оптимизацию на уровне источника, которые зависят от свойств типа, которые необходимо определить во время компиляции, если тип можно безопасно скопировать с использованием байт-мутной копии, такой как memcpy, и делегировать такой метод, если это так, или иным образом вернуться к элементный цикл копирования.

Чтобы безопасно копировать с помощью memcpy, объект должен быть тривиально с возможностью копирования. Теперь std::unique_ptr не является тривиально скопируемым, так как в действительности он не выполняет некоторые из требований, таких как наличие только тривиальных или удаленных копий и перемещений конструкторов. Точный механизм зависит от стандартной библиотеки, но в целом реализация качества std::vector в конечном итоге вызовет специализированную форму чего-то вроде std::uninitialized_copy для тривиально-копируемых типов, которые просто делегируются memmove.

Типичные детали реализации довольно подвергнуты пыткам, но для libstc++ (используется gcc) вы можете видеть расхождение высокого уровня в std::uninitialized_copy:

 template<typename _InputIterator, typename _ForwardIterator>
 inline _ForwardIterator
 uninitialized_copy(_InputIterator __first, _InputIterator __last,
                    _ForwardIterator __result)
 {
        ...
   return std::__uninitialized_copy<__is_trivial(_ValueType1)
                                    && __is_trivial(_ValueType2)
                                    && __assignable>::
     __uninit_copy(__first, __last, __result);
 }

Отныне вы можете смириться с тем, что многие из методов std::vector "движение" здесь заканчиваются и что __uninitialized_copy<true>::__uinit_copy(...) в конечном итоге вызывает memmove, а версия <false> - или вы можете проследить код (но вы уже видели результат в своем тесте).

В конечном итоге вы получаете несколько циклов, которые выполняют требуемые шаги копирования для нетривиальных объектов, таких как вызов конструктора перемещения целевого объекта и последующее вызов деструктора всех исходных объектов. Это отдельные циклы, и даже современные компиляторы в значительной степени не смогут рассуждать о чем-то вроде "ОК, в первом цикле я переместил все целевые объекты, чтобы их член ptr был пустым, поэтому второй цикл - оп". Наконец, чтобы равняться скорости исходных указателей, не только компиляторы должны были оптимизировать эти две петли, они должны были бы иметь трансформацию, которая признает, что все это может быть заменено на memcpy или memmove 2.

Итак, один ответ на ваш вопрос заключается в том, что компиляторы просто недостаточно умен, чтобы сделать эту оптимизацию, но в значительной степени потому, что у "сырой" версии есть много информации о времени компиляции, чтобы полностью исключить необходимость этой оптимизации.

Loop Fusion

Как уже упоминалось, существующие реализации vector реализуют операцию типа resize в двух отдельных циклах (в дополнение к работе без цикла, например, распределению нового хранилища и освобождению старого хранилища):

  • Копирование исходных объектов во вновь назначенный целевой массив (концептуально используя что-то вроде размещения new, вызывающего конструктор перемещения).
  • Уничтожение исходных объектов в старой области.

Концептуально вы могли бы представить альтернативный способ: делать это все в одном цикле, копируя каждый элемент и сразу же уничтожая его. Возможно, что компилятор даже заметил, что две петли повторяются по одному и тому же набору значений и соединяют две петли в одну. [По-видимому], howevever, (https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html) gcc сегодня не делает никакого фьюжн-цикла, а также clang или icc, если вы считаете этот тест.

Итак, мы остаемся, пытаясь поместить петли вместе явно на исходном уровне.

Теперь двухпетковая реализация помогает сохранить контракт безопасности на исключение операции, не разрушая никаких исходных объектов, пока мы не узнаем, что строительная часть копии завершена, но также помогает оптимизировать копию и разрушение, когда мы имеем тривиальную -копируемые и тривиально разрушаемые объекты, соответственно. В частности, при выборе на основе простых признаков мы можем заменить копию на memmove, и цикл уничтожения может быть полностью исключен 3.

Таким образом, подход с двумя циклами помогает, когда эти оптимизации применяются, но на самом деле он болит в общем случае объектов, которые не являются ни тривиально скопируемыми, ни разрушаемыми. Это означает, что вам нужно пройти два прохода над объектами, и вы теряете возможность оптимизировать и исключить код между копией объекта и последующим уничтожением. В случае unique_ptr вы теряете способность компилятора распространять знания о том, что источник unique_ptr будет иметь NULL внутренний элемент ptr и, следовательно, пропустить тег if (ptr) delete ptr полностью 4.

Тривиально подвижный

Теперь можно спросить, можем ли мы применить те же методы оптимизации времени компиляции типа к случаю unique_ptr. Например, можно взглянуть на тривиально скопируемые требования и увидеть, что они, возможно, слишком строгие для общих операций перемещения в std::vector. Несомненно, unique_ptr, по-видимому, не может быть тривиально скопируемым, так как побитовая копия оставит как исходный, так и целевой объект за тот же указатель (и приведет к двойному удалению), но кажется, что он должен быть бит-мутным подвижным: если вы перемещаете unique_ptr из одной области памяти в другую, так что вы больше не рассматриваете источник как живой объект (и, следовательно, не будете называть его деструктор), он должен "просто работать", для типичного unique_ptr реализация.

К сожалению, такой концепции "тривиального движения" не существует, хотя вы можете попытаться опрокинуть свои собственные. Кажется, существует открытая дискуссия о том, является ли это UB или нет для объектов, которые могут быть скопированы по байтам и не зависят от их поведения конструктора или деструктора в ходе перемещения сценарий.

Вы всегда можете реализовать свою собственную тривиально подвижную концепцию, которая была бы похожа на (a) объект имеет тривиальный конструктор перемещения и (b), когда он используется в качестве исходного аргумента конструктора перемещения, объект остается в состоянии, когда это деструктор не имеет никакого эффекта. Обратите внимание, что такое определение в настоящее время в основном бесполезно, поскольку "тривиальный конструктор перемещения" (в основном, с использованием элементарной копии и ничего другого) не согласуется ни с одной модификацией исходного объекта. Так, например, тривиальный конструктор перемещения не может установить член ptr источника unique_ptr равным нулю. Таким образом, вам нужно будет прыгать, хотя некоторые дополнительные обручи, такие как введение концепции деструктивной операции перемещения, которая исключает исходный объект, а не в состоянии, но не заданном.

Вы можете найти более подробное обсуждение этого "тривиально движимого" на этот поток в группе обсуждений Usenet ISO С++. В частности, в связанном ответе рассматривается точная проблема векторов unique_ptr:

Получается много умных указателей (включая unique_ptr и shared_ptr) попадают во все три категории, и, применяя их, вы можете имеют векторы интеллектуальных указателей с нулевыми накладными расходами над сырыми указатели даже в не оптимизированных отладочных сборках.

См. также предложение relocator.

0 Хотя не-векторные примеры в конце вашего вопроса показывают, что это не всегда так. Здесь это связано с возможным псевдонимом, поскольку zneak объясняет в его ответ. Исходные указатели будут избегать многих из этих проблем с псевдонимом, поскольку им не хватает указателя на unique_ptr (например, вы передаете необработанный указатель по значению, а не структуру с указателем по ссылке) и часто можете полностью исключить проверку if (ptr) delete ptr.

2 Это на самом деле сложнее, чем вы думаете, потому что memmove, например, имеет тонко различную семантику, чем цикл копирования объекта, когда источник и место назначения перекрываются. Конечно, код типа высокого уровня типа, который работает для сырых точек, знает (по контракту), что нет совпадения, или поведение memmove является согласованным, даже если существует перекрытие, но доказывая одно и то же в каком-то более позднем произвольном прохождении оптимизации может быть намного сложнее.

3 Важно отметить, что эти оптимизации более или менее независимы. Например, многие объекты тривиально разрушаемы, так как при этом тривиально не копируются.

4 Хотя в мой тест ни gcc, ни clang не удалось подавить чек, даже при использовании __restrict__, по-видимому, из-за недостаточно мощного анализа псевдонимов, или, возможно, потому, что std::move каким-то образом разбивает "ограничивающий" квалификатор.

Ответ 2

У меня нет точного ответа на то, что кусает вас сзади с помощью векторов; похоже, что у BeeOnRope уже есть один для вас.

К счастью, я могу рассказать вам, что кусает вас в спину для вашего микро-примера, связанного с различными способами reset указателей: анализ псевдонимов. В частности, компиляторы не могут доказать (или не хотят делать вывод), что две ссылки unique_ptr не перекрываются. Они заставляют себя перезагрузить значение unique_ptr в случае, если первая запись изменила вторую. baz не страдает от этого, потому что компилятор может доказать, что ни один из параметров в хорошо сформированной программе не мог бы быть псевдонимом с tmp, который имеет локально автоматическое хранилище функций.

Вы можете проверить это с помощью добавления ключевого слова __restrict__ (что, как следует из двойного подчеркивания, не является стандартным С++), чтобы либо опорный параметр unique_ptr. Это ключевое слово сообщает компилятору, что ссылка является единственной ссылкой, через которую можно получить доступ к этой памяти, и, следовательно, нет никакого риска, что что-либо еще может быть с ней связано. Когда вы это сделаете, все три версии вашей функции будут скомпилированы с одним и тем же машинным кодом и не будут проверять необходимость удаления unique_ptr.