Type Trait std::is_relocatable

Andrey Davydov
Andrey Davydov

Мотивация

relocatable это естественное обобщение стандартного свойства trivially copyable. С одной стороны оно дает простор для оптимизаций, к примеру, позволяет свести такую операцию как realloc вектора из n элементов к одному memcpy вместо n вызовов move_if_noexcept + n вызовов деструктуров для перемещенных/скопированных элементов. С другой стороны множество relocatable типов значительно шире множества trivially copyable. Рассмотрим некоторые типы стандартной библиотеки, которые не являются trivially copyable но при этом являются relocatable.

  • shared_ptr: при побитовом копировании и невыполнении деструктора для старого экземпляра shared_ptr, значение счетчика ссылок, очевидно, не изменяется, что эквивалетно перемещению для shared_ptr.
  • unique_ptr<T, D>, если D -- relocatable (std::default_delete, являясь trivial copyable, является и relocatable). Если побитово скопировать pointer и deleter (в предположении, что для него это валидно) и не вызывать деструктор, то новый экземпляр, останется единственным владельцем указателя.
  • string и все стандартные контейнеры, по крайнер мере при использовании std::allocator (ровно те же рассуждения, что и для unique_ptr).
  • optional<T>, variant<Ts...>, если T и Ts... -- relocatable.

Формализация

Предалаю определить понятие relocatable types в [basic.types] p9 (где-то рядом с trivially copyable types) и relocatable class в [class] (где-то рядом с trivially copyable class).

Trivially copyable types, relocatable class types, arrays of such types and cv-qualified versions of these types are collectively called relocatable types.

Класс является relocatable если он или явно помечен как relocatable или все базовые классы и все нестатические члены данных являются relocatable, и класс имеет non-virtual, non-deleted не user-defined деструктор. Есть вопрос как лучше определить "явно помечен как relocatable", потому что, насколько я понимаю, пока что единственным прецендентом определить не выводимое компилятором свойство класса было ключевое слова final. Как вариант, можно ввести специальный класс std::relocatable_marker и проверять является ли он непосредственной базой нашего типа. Плюс, может быть полезной метафункция std::conditional_relocatable_marker<bool>. К примеру, определение unique_ptr может выглядеть следующим образом:

namespace std {

template<bool>
struct conditional_relocatable_marker;

template<>
struct conditional_relocatable_marker<true>
{
  using type = relocatable_marker;
};

template<>
struct conditional_relocatable_marker<false>
{
  struct dummy {};

  using type = dummy;
};

template<class T, class D>
class unique_ptr : typename conditional_relocatable_marker<is_relocatable_v<D>>::type
{
  // ...
};

}
6
рейтинг
10 комментариев
yndx-antoshkka
Идея огонь!

Надо набрать больше примеров где это может дать
* хороший прирост производительности в библиотеке (std::vector<std::shared_ptr<int>>, std::deque<std::string>, ещё больше примеров нужно!)
* прирост производительности в ядре языка:
void foo(shared_ptr<int>& out)
auto s = make_shared<int>(42);
// ...
out = s; // не вызывать деструктор а требовать memcpy
}

Я пока попробую найти предыдущие обсуждения подобных идей.
yndx-antoshkka
Andrey Davydov
yndx-antoshkka, из стандартных фукнций можно специализировать
(*) std::swap
(*) std::swap_ranges for contiguous ranges
как следствие можно выиграть в *sort*, inplace_merge, unique, rotate, remove*, partition, nth_element, make_heap, ...
То же работает, когда выполняется swap пустого и непустого optional'а и variant'ов с разными текущими значениями индексов.
А насчет ядра языка я не понял, разве можно требовать от компилятора выполнения таких оптимизаций? Ведь тогда уже сейчас можно потребовать для функции foo из твоего примера выполнять move assignment а не copy assignment. Неужели по стандарту компилятор обязан это делать?
Andrey Davydov
Andrey Davydov
yndx-antoshkka, можно в духе guaranteed copy elision потребовать оптимизацию для функции, возвращающей relocatable тип, если не выполнился copy elision. Это сработает, скажем, для такой функции.
std::vector<int> bar(bool c)
{
std::vector<int> xs = { 1, 2, 3}, ys = { 4, 5, 6 };
if (c)
return xs;
else
return ys;
}
Andrey Davydov
yndx-antoshkka
Компилятор делать такое пока не обязан.

Добавление нового type trait - это proposalы которые касаются как групп занимающихся ядром языка, так и групп развивающих стандартную библиотеку. Нужно убедить сразу две группы, что такой type trait будет полезен. Поэтому и стоит поискать примеры как для стандартной библиотеки, так и для ядра языка.

Итак, сможете перевести вашу идею на английский и описать её с кучей примеров на std-proposals@isocpp.org ? Если да - скиньте сюда ссылку на обсуждение.
yndx-antoshkka
Andrey Davydov
yndx-antoshkka, оказалось, что обсуждение такой идеи на std-proposals@isocpp.org уже было, правда в несколько неожиданном треде: groups.google.com/a/isocpp.org/d/msg/std-proposals/Y6gjtmVyzBo/NyWaMPamzXEJ
Кроме того, выяснилось, что помимо Folly под разными именами свойство is_relocatable можно определять в BDE (IsBitwiseMoveable), EASTL (has_trivial_relocate), Qt (Q_MOVABLE_TYPE).
Andrey Davydov
yndx-antoshkka
Andrey Davydov, предлагаю еще раз написать в рассылку про std::is_relocatable, так как прошлое ообсуждение закончилось ничем.

Ну и начинать писать proposal :)
yndx-antoshkka
Andrey Davydov
yndx-antoshkka, я создал обсуждение: groups.google.com/a/isocpp.org/d/msg/std-proposals/4Wwpi4EUGlg/or77NGalBwAJ
Надеюсь, что мой кривой английский не станет непреодолимым препятствием и мне напишут что-нибудь конструктивное.
Andrey Davydov
yndx-antoshkka
Переписка получилась очень конструктивной:
* выяснили, что компиляторы могут делать такую оптимизацию автоматически
* нашли и сразу поправили недочёт оптимизации в GCC (7 версия с флагом -std=c++17 будет лучше оптимизировать деструкторы)

Отдельно от переписки:
- Завёл тикет на добавление аналогичной оптимизации деструкторов в CLANG: bugs.llvm.org//show_bug.cgi?id=32522
- Завёл тикеты на более агрессивные оптимизации смежных циклов, чтобы unitialized_move + destroy превращались в подобие memcpy для GCC gcc.gnu.org/bugzilla/show_bug.cgi?id=80317 и для CLANG bugs.llvm.org//show_bug.cgi?id=32523

Если тикеты примут и реализуют - предложенная в обсуждении оптимизация is_relocatable заработает на двух популярных компиляторах из коробки. Весь пользовательский код станет быстрее без каких-либо дополнительных телодвижений.
yndx-antoshkka
Antervis
А что станет с невалидным объектом после того, как из него будет сделан relocate? Деструктор вызывать, получается, нельзя, то есть relocate операция доступна либо только из временного объекта (причем у категории такого объекта требования строже rvalue); либо делать этот объект inaccessible, как-то так:

int x = 5;
y = std::relocate(x);
++x; // error - x is not defined

Но для подобных случаев компилятор может заменить код на вызов деструктора и конструктора прямо в целевом объекте.

Возможно, стоит начать с trivially_movable? Т.е. trait'a типа, для которого T a = std::move(b); может быть заменен на memcpy(&a,&b,sizeof(a)); new (&b) T(); где второй вызов может быть удален компилятором, если переменная b дальше не используется?
Antervis
Andrey Davydov
Antervis, я не предлагаю функцию std::relocate, которая бы заставляла компилятор не вызывать у объектов с automatic storage duration деструктор. В тех примерах, что я приводил -- буффер vector'а, optional, variant декструктор вызывается вручную, т.е. алгоритм перемещения элементов vector'а следующий: если объект relocatable, то побитно копируем память объекта на новое место и не вызываем деструктор на старом, иначе вызываем move- или copy- конструктор на новом месте и затем деструктор на старом месте. Т.е. никакого нового механизма со стороны компилятора для релокации не нужно и не предлагается.
Andrey Davydov
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).