Делаем своп быстрее, проще в использовании и безопасным для исключений

Я не мог спать прошлой ночью и начал думать о std::swap. Вот знакомая версия C++98:

template <typename T>
void swap(T& a, T& b)
{
    T c(a);
    a = b;
    b = c;
}

Если определяемый пользователем класс Foo использует внешние ресурсы, это неэффективно. Обычная идиома состоит в том, чтобы предоставить метод void Foo::swap(Foo& other) и специализацию std::swap<Foo>. Обратите внимание, что это не работает с шаблонами классов, поскольку вы не можете частично специализировать шаблон функции, а перегрузка имен в пространстве имен std недопустима. Решение состоит в том, чтобы написать шаблонную функцию в своем собственном пространстве имен и полагаться на поиск, зависящий от аргумента, чтобы найти ее. Это критически зависит от того, будет ли клиент следовать «идиоме using std::swap» вместо прямого вызова std::swap. Очень хрупкий.

В C++0x, если Foo имеет определяемый пользователем конструктор перемещения и оператор присваивания перемещения, предоставление пользовательского метода swap и специализации std::swap<Foo> практически не дает выигрыша в производительности, поскольку версия std::swap для C++0x вместо этого использует эффективные перемещения. копий:

#include <utility>

template <typename T>
void swap(T& a, T& b)
{
    T c(std::move(a));
    a = std::move(b);
    b = std::move(c);
}

Отсутствие необходимости возиться с swap уже снимает с программиста большую нагрузку. Текущие компиляторы пока не генерируют конструкторы перемещения и операторы присваивания перемещения автоматически, но, насколько я знаю, это изменится. Единственная проблема, оставшаяся тогда, — безопасность исключений, потому что в целом операции перемещения разрешены для бросков, и это открывает целую банку червей. На вопрос «Каково именно состояние перемещенного объекта?» еще больше усложняет дело.

Тогда я подумал, какова именно семантика std::swap в C++0x, если все идет нормально? Каково состояние объектов до и после замены? Как правило, обмен с помощью операций перемещения не затрагивает внешние ресурсы, а только сами «плоские» представления объектов.

Так почему бы просто не написать шаблон swap, который делает именно это: меняет местами представления объектов?

#include <cstring>

template <typename T>
void swap(T& a, T& b)
{
    unsigned char c[sizeof(T)];

    memcpy( c, &a, sizeof(T));
    memcpy(&a, &b, sizeof(T));
    memcpy(&b,  c, sizeof(T));
}

Это настолько эффективно, насколько это возможно: он просто взрывает необработанную память. Это не требует никакого вмешательства со стороны пользователя: не нужно определять специальные методы подкачки или операции перемещения. Это означает, что он работает даже в C++98 (в котором, заметьте, нет ссылок на rvalue). Но что еще более важно, теперь мы можем забыть о проблемах с безопасностью исключений, потому что memcpy никогда не выдает ошибки.

Я вижу две потенциальные проблемы с этим подходом:

Во-первых, не все объекты предназначены для замены. Если разработчик класса скрывает конструктор копирования или оператор присваивания копии, попытка поменять местами объекты класса должна завершиться ошибкой во время компиляции. Мы можем просто ввести некоторый мертвый код, который проверяет, разрешены ли копирование и присваивание для типа:

template <typename T>
void swap(T& a, T& b)
{
    if (false)    // dead code, never executed
    {
        T c(a);   // copy-constructible?
        a = b;    // assignable?
    }

    unsigned char c[sizeof(T)];

    std::memcpy( c, &a, sizeof(T));
    std::memcpy(&a, &b, sizeof(T));
    std::memcpy(&b,  c, sizeof(T));
}

Любой приличный компилятор может тривиально избавиться от мертвого кода. (Возможно, есть лучшие способы проверить «соответствие свопа», но это не главное. Важно то, что это возможно).

Во-вторых, некоторые типы могут выполнять «необычные» действия в конструкторе копирования и операторе присваивания копии. Например, они могут уведомить наблюдателей о своем изменении. Я считаю это незначительной проблемой, потому что такие объекты, вероятно, не должны были обеспечивать операции копирования в первую очередь.

Пожалуйста, дайте мне знать, что вы думаете об этом подходе к обмену. Будет ли это работать на практике? Вы бы использовали его? Можете ли вы определить типы библиотек, где это может сломаться? Вы видите дополнительные проблемы? Обсуждать!


person fredoverflow    schedule 02.02.2011    source источник
comment
Большинство существующих вариантов использования std::swap в любом случае будут иметь лучшие решения с использованием семантики перемещения.   -  person aschepler    schedule 02.02.2011
comment
Да переместите семантику и переместите конструкторы. См. это, stackoverflow.com/questions/4820643/   -  person Michael Smith    schedule 02.02.2011
comment
подумайте swap(*polymorphicPtr1,*polymorphicPtr2)... ваша функция подкачки также поменяет виртуальную таблицу обоих объектов... что вызовет хаос, если кто-то вызовет виртуальную функцию перед вызовом подкачки.   -  person smerlin    schedule 02.02.2011
comment
@smerlin: Но полиморфные объекты действительно не должны иметь конструкторов копирования или операторов присваивания, верно?   -  person fredoverflow    schedule 02.02.2011
comment
@FredOverflow: Да, но вопрос в том, можете ли вы написать статическое утверждение, чтобы проверить, является ли T полиморфным типом или нет. Потому что в противном случае кто-то БУДЕТ использовать его с полиморфными типами, несмотря на то, что это не очень хорошая привычка иметь операторы присваивания для полиморфных типов (imo: конструкторы-копии иногда в порядке).   -  person smerlin    schedule 02.02.2011
comment
@smerlin: На самом деле, да :) C++0x предоставляет черту типа std::is_polymorphic.   -  person fredoverflow    schedule 02.02.2011


Ответы (5)


Так почему бы просто не написать шаблон swap, который делает именно это: меняет местами представления объектов*?

Существует много способов, которыми объект после создания может сломаться при копировании байтов, в которых он находится. На самом деле, можно придумать бесконечное количество случаев, когда это не будет правильным. вещь - хотя на практике это может сработать в 98% всех случаев.

Это связано с тем, что основной проблемой всего этого является то, что в отличие от C, в C++ мы не должны обращаться с объектами так, как если бы они были простыми необработанными байтами. В конце концов, именно поэтому у нас есть строительство и разрушение: чтобы превратить необработанное хранилище в объекты, а объекты обратно в необработанное хранилище. После запуска конструктора память, в которой находится объект, представляет собой нечто большее, чем простое хранилище. Если вы относитесь к нему так, как будто это не так, вы сломаете некоторые типы.

Однако, по сути, движущиеся объекты не должны работать намного хуже, чем вы предполагали, потому что, как только вы начинаете рекурсивно встраивать вызовы std::move(), вы обычно в конечном итоге достигаете места, куда перемещаются встроенные модули. (И если для некоторых типов нужно перемещать что-то еще, вам лучше не возиться с их памятью самостоятельно!) Конечно, перемещение памяти единым блоком обычно происходит быстрее, чем одиночное перемещение (и маловероятно, что компилятор может обнаружить, что он может это сделать). оптимизировать отдельные движения до одного всеобъемлющего std::memcpy()), но это цена, которую мы платим за ту абстракцию, которую нам предлагают непрозрачные объекты. И это довольно мало, особенно если сравнивать с копированием, которое мы делали раньше.

Однако вы можете оптимизировать swap(), используя std::memcpy() для агрегированных типов.

person sbi    schedule 02.02.2011
comment
s/praxis/practice/ ;-) Также было бы неплохо добавить ссылку на часто задаваемые вопросы по POD/aggregate. - person fredoverflow; 02.02.2011
comment
@Fred, мой словарь говорит, что практика - это совершенно правильное английское слово. Не так ли? Английский не мой родной язык, но мне любопытно. - person Sergei Tachenov; 02.02.2011
comment
@Sergey: Google имеет 27 700 000 результатов поиска на практике, но только 214 000 на практике ... - person fredoverflow; 02.02.2011
comment
Вы уверены в отсутствии слияния соседних ходов в один? Похоже на банальную оптимизацию. (Я предполагаю, что это может быть отброшено наличием неперемещенных данных, таких как указатели виртуальных таблиц) - person Matthieu M.; 02.02.2011
comment
Матье: Нет, я не уверен. Заметьте, я написал, что это маловероятно. - person sbi; 03.02.2011
comment
@sbi: я понимаю, о чем вы говорите, но мне также любопытно - вы привели фактический пример того, где memcpy объект ломается? Единственный экземпляр, о котором я знаю, относится к типам, которые содержат указатели на самих себя... что я еще не видел на практике. - person user541686; 24.07.2012
comment
@Mehrdad: я считаю побитовое копирование подозрительным каждый раз, когда у класса есть операция копирования/назначения. Конечно, подкачка не требует такого внимания, как собственно копирование, но все равно оставляет достаточно дел. В качестве реального примера рассмотрим объекты, чьи адреса где-то зарегистрированы, и где копирование и т. д. обновляет этот реестр. (В основном, каждый случай, когда объект упоминается сам по себе или какой-либо другой объект.) - person sbi; 25.07.2012
comment
@sbi: на самом деле мы обсуждали это здесь; не стесняйтесь публиковать там. Я понимаю, что если существует циклическая зависимость, и объекты обычно обновляют внешние ссылки обычным swap, тогда возникнут проблемы. .. но на практике единственная ситуация, о которой мы могли подумать, это итераторы, которые в любом случае будут признаны недействительными. См. этот пост для обсуждения. Итак, на практике мне кажется, что если вы знаете, что у вас нет автоматически обновляемых циклических зависимостей (которые не очень распространены), то все должно быть в порядке? - person user541686; 25.07.2012

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

class SomeClassWithBuffer {
  private:
    enum {
      BUFSIZE = 4096,
    };
    char buffer[BUFSIZE];
    char *currentPos; // meant to point to the current position in the buffer
  public:
    SomeClassWithBuffer();
    SomeClassWithBuffer(const SomeClassWithBuffer &that);
};

SomeClassWithBuffer::SomeClassWithBuffer():
  currentPos(buffer)
{
}

SomeClassWithBuffer::SomeClassWithBuffer(const SomeClassWithBuffer &that)
{
  memcpy(buffer, that.buffer, BUFSIZE);
  currentPos = buffer + (that.currentPos - that.buffer);
}

Теперь, если вы просто выполните memcpy(), куда укажет currentPos? Очевидно, на старое место. Это приведет к очень забавным ошибкам, когда каждый экземпляр фактически использует буфер другого.

person Sergei Tachenov    schedule 02.02.2011
comment
Честно говоря, создание копируемого и назначаемого объекта Reader кажется мне дизайнерской ошибкой. - person fredoverflow; 02.02.2011
comment
@Fred, это просто абстрактный пример. Вероятно, мне следовало бы назвать его SomeClassWithBuffer, но это не имеет значения. - person Sergei Tachenov; 02.02.2011
comment
@Matthieu, эта проблема была упомянута ОП, поэтому я не упомянул об этом. Вероятно, есть и другие проблемы, которые кажутся на первый взгляд. - person Sergei Tachenov; 02.02.2011
comment
Также буфер, который предлагает OP, может быть неправильно выровнен для T. - person Motti; 02.02.2011
comment
@Motti, я думаю, это не проблема, так как это только для временного хранения, а T обрабатывается как массив байтов, который идеально подходит для любого типа. - person Sergei Tachenov; 02.02.2011
comment
@FredOverflow: Не вам судить об этом. Это совершенно законно в языке, и вы не делаете никому никакой выгоды, делая это таким образом. - person Puppy; 02.02.2011
comment
Проголосовали: важные мелочи: каждый основанный на узле std::container как в libstdc++, так и в libc++ (libcxx.llvm.org) имеет дизайн, который иллюстрирует Сергей (и, таким образом, не работает с memcpy-swap). Это оптимизация встроенного конечного узла и одна из наиболее важных оптимизаций для контейнера на основе узла. Это включает как конструктор noexcept по умолчанию, так и конструктор перемещения noexcept. Имхо, это не становится намного более важным, чем это. Естественно, эти контейнеры могут создавать и создают свои собственные перегрузки подкачки. Но суть в том, что дизайн Сергея не редкость. - person Howard Hinnant; 20.05.2011

Некоторые типы можно поменять местами, но нельзя скопировать. Уникальные интеллектуальные указатели, вероятно, лучший пример. Проверка на копируемость и присваиваемость неверна.

Если T не является типом POD, использование memcpy для копирования/перемещения является неопределенным поведением.


Обычная идиома состоит в том, чтобы предоставить метод void Foo::swap(Foo&other) и специализацию std::swap‹Foo>. Обратите внимание, что это не работает с шаблонами классов,…

Лучшей идиомой является своп, не являющийся членом, и требующий, чтобы пользователи вызывали своп без квалификации, поэтому применяется ADL. Это также работает с шаблонами:

struct NonTemplate {};
void swap(NonTemplate&, NonTemplate&);

template<class T>
struct Template {
  friend void swap(Template &a, Template &b) {
    using std::swap;
#define S(N) swap(a.N, b.N);
    S(each)
    S(data)
    S(member)
#undef S
  }
};

Ключом является использование объявления для std::swap в качестве запасного варианта. Дружба для обмена шаблона удобна для упрощения определения; своп для NonTemplate тоже может подойти, но это деталь реализации.

person Fred Nurk    schedule 02.02.2011

Я считаю это незначительной проблемой, потому что такие объекты, вероятно, не должны были обеспечивать операции копирования в первую очередь.

То есть, попросту говоря, куча неправильных вещей. Классы, которые уведомляют наблюдателей, и классы, которые не следует копировать, совершенно не связаны между собой. Как насчет shared_ptr? Это, очевидно, должно быть копируемым, но оно также, очевидно, уведомляет наблюдателя о подсчете ссылок. Это правда, что в этом случае счетчик ссылок остается таким же после подкачки, но это определенно не верно для всех типов, и это особенно неверно, если используется многопоточность, это неверно для случай обычной копии вместо замены и т. д. Это особенно неправильно для классов, которые можно перемещать или менять местами, но не копировать.

потому что в целом операции перемещения разрешены для броска

Наверняка нет. Практически невозможно гарантировать надежную защиту от исключений практически при любых обстоятельствах, связанных с ходами, когда ход может привести к срабатыванию. В определении C++0x стандартной библиотеки из памяти явно указано, что любой тип, используемый в любом стандартном контейнере, не должен вызываться при перемещении.

Это настолько эффективно, насколько это возможно

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

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

person Puppy    schedule 02.02.2011
comment
+1 за указание: ... В определении стандартной библиотеки С++ 0x из памяти явно указано, что любой тип, используемый в любом стандартном контейнере, не должен выбрасываться при перемещении. .... - person Martin Ba; 03.02.2011
comment
и я бы добавил еще +1 за ... и, что более важно, он все равно скомпилируется до этой операции ... - person Martin Ba; 03.02.2011

ваша swap версия вызовет хаос, если кто-то будет использовать ее с полиморфными типами.

учитывать:

Base *b_ptr = new Base();    // Base and Derived contain definitions
Base *d_ptr = new Derived(); // of a virtual function called vfunc()
yourmemcpyswap( *b_ptr, *d_ptr );
b_ptr->vfunc(); //now calls Derived::vfunc, while it should call Base::vfunc
d_ptr->vfunc(); //now calls Base::vfunc while it should call Derived::vfunc
//...

это неправильно, потому что теперь b содержит виртуальную таблицу типа Derived, поэтому Derived::vfunc вызывается для объекта, который не имеет типа Derived.

Обычный std::swap меняет местами только элементы данных Base, поэтому с std::swap все в порядке.

person smerlin    schedule 02.02.2011
comment
Замена только членов данных Base может нарушить инварианты объекта Derived. Это одна из причин, по которой не имеет особого смысла иметь оператор присваивания для полиморфных объектов. Обратите внимание, что Бьерн Страуструп считает исторической случайностью тот факт, что оператор присваивания предоставляется по умолчанию для каждого определяемого пользователем класса. - person fredoverflow; 02.02.2011