Type Trait std::is_relocatable

Перенос предложения: голоса +8, -2 Aвтор идеи: Andrey Davydov

В библиотеке folly (https://github.com/facebook/folly/blob/master/folly/docs/Traits.md) определен type trait IsRelocatable сигнализирующий, что соответствующий тип может быть перемещен с помощью memcpy + забывание старого объекта (т.е. для него не должен вызываться деструктор). Такое свойство полезно было бы, во-первых, стандартизировать, а во-вторых, использовать в стандартных контейнерах и алгоритмах.

Мотивация

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, variant, если 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. К примеру, определение 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
{
  // ...
};

}

yndx-antoshkka, 21 марта 2017, 16:09 Идея огонь!

Надо набрать больше примеров где это может дать

хороший прирост производительности в библиотеке (std::vector<std::shared_ptr>, std::deque, ещё больше примеров нужно!)

прирост производительности в ядре языка:

void foo(shared_ptr<int>& out)
auto s = make_shared<int>(42);
// ...
out = s; // не вызывать деструктор а требовать memcpy
}

Я пока попробую найти предыдущие обсуждения подобных идей.

Andrey Davydov, 22 марта 2017, 0:45 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, 22 марта 2017, 1:29 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;
}

yndx-antoshkka, 22 марта 2017, 13:08 Компилятор делать такое пока не обязан.

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

Итак, сможете перевести вашу идею на английский и описать её с кучей примеров на std-proposals@isocpp.org ? Если да - скиньте сюда ссылку на обсуждение.

Andrey Davydov, 27 марта 2017, 9:39 yndx-antoshkka, оказалось, что обсуждение такой идеи на std-proposals@isocpp.org уже было, правда в несколько неожиданном треде: https://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).

yndx-antoshkka, 27 марта 2017, 16:12 Andrey Davydov, предлагаю еще раз написать в рассылку про std::is_relocatable, так как прошлое ообсуждение закончилось ничем.

Ну и начинать писать proposal :)

Andrey Davydov, 28 марта 2017, 10:36 yndx-antoshkka, я создал обсуждение: https://groups.google.com/a/isocpp.org/d/msg/std-proposals/4Wwpi4EUGlg/or77NGalBwAJ Надеюсь, что мой кривой английский не станет непреодолимым препятствием и мне напишут что-нибудь конструктивное.

yndx-antoshkka, 5 апреля 2017, 13:17 Переписка получилась очень конструктивной:

выяснили, что компиляторы могут делать такую оптимизацию автоматически
нашли и сразу поправили недочёт оптимизации в GCC (7 версия с флагом -std=c++17 будет лучше оптимизировать деструкторы)

Отдельно от переписки:

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

Если тикеты примут и реализуют - предложенная в обсуждении оптимизация is_relocatable заработает на двух популярных компиляторах из коробки. Весь пользовательский код станет быстрее без каких-либо дополнительных телодвижений.

Antervis, 23 марта 2017, 7:09 А что станет с невалидным объектом после того, как из него будет сделан 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 дальше не используется?

Andrey Davydov, 23 марта 2017, 20:14 Antervis, я не предлагаю функцию std::relocate, которая бы заставляла компилятор не вызывать у объектов с automatic storage duration деструктор. В тех примерах, что я приводил -- буффер vector'а, optional, variant декструктор вызывается вручную, т.е. алгоритм перемещения элементов vector'а следующий: если объект relocatable, то побитно копируем память объекта на новое место и не вызываем деструктор на старом, иначе вызываем move- или copy- конструктор на новом месте и затем деструктор на старом месте. Т.е. никакого нового механизма со стороны компилятора для релокации не нужно и не предлагается.

cpp-ru / ideas

Type Trait std::is_relocatable #142

Мотивация

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