Std:: swap vs std:: exchange vs swap operator

Реализация std::swap может выглядеть так:

template <class T> void swap (T& a, T& b)
{
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}
template <class T, size_t N> void swap (T (&a)[N], T (&b)[N])
{
  for (size_t i = 0; i<N; ++i) swap (a[i],b[i]);
}

Реализация std::exchange n3668 может выглядеть так:

 template< typename T, typename U = T >
   T exchange( T & obj, U && new_val )
   {
     T old_val = std::move(obj);
     obj = std::forward<U>(new_val);
     return old_val;
   }

В нем говорится:

Для примитивных типов это эквивалентно очевидной реализации, а для более сложных типов это определение

  • Предотвращает копирование старого значения, когда этот тип определяет конструктор перемещения
  • Принимает любой тип в качестве нового значения, используя любой оператор присваивания преобразования
  • Предотвращает копирование нового значения, если оно временно или перемещено.

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

n3746 также предлагает встроенный оператор свопинга, который выглядит следующим образом:

inline C& C::operator :=: (C&& y) &  { see below; return *this; } 
inline C& C::operator :=: (C& y)  &  { return *this :=: std::move(y); }

Из того, что я собираю, предложения хотели бы, чтобы все три из этих вариантов жили бок о бок, а не заменяли друг друга. Почему необходимо иметь три разных способа обмена объектами?

Ответы

Ответ 1

std:: swap vs std:: exchange

swap(x, y) и exchange(x, y) - это не одно и то же. exchange(x, y) никогда не присваивает новое значение y. Вы можете сделать это, если вы используете его следующим образом: y = exchange(x, y). Но это не основной вариант использования для exchange(x, y). N3668 включает в себя утверждение:

Выгода не огромна, но и стоимость спецификации отсутствует.

(в отношении стандартизации exchange).

N3668 был проголосован в рабочем проекте С++ 1y на бристольской встрече в апреле 2013 года. В протоколе собрания указано, что некоторая дискуссия о лучшем названии этой функции в Рабочей группе по библиотеке и что в конечном итоге не было возражений против ее официального голосования в полном составе. Официальное голосование решительно высказалось за то, чтобы включить его в рабочий проект, но не единогласно.

Нижняя строка: exchange является второстепенной утилитой, не конкурирует с swap(x, y) и имеет гораздо меньше случаев использования.

std:: swap vs swap operator

N3553, предыдущая версия для N3746, обсуждался в рабочей группе по эволюции на встрече в апреле 2013 года в Бристоле. Минуты собрания признают "раздражающие проблемы ADL" с std::swap(x, y), но заключают, что оператор свопинга не будет решать эти проблемы. Из-за обратной совместимости EWG также считала, что если принято, std::swap и оператор свопа навсегда сосуществуют. EWG решила в Бристоле не продолжать N3553.

Протоколы встречи в Чикаго EWG за сентябрь 2013 года не упоминают N3746. Я не присутствовал на этой встрече, но полагаю, что EWG отказалась рассматривать N3746 из-за своего предыдущего решения в Бристоле на N3553.

Итог: комитет С++, похоже, не движется вперед с оператором свопинга в это время.

Обновление: может ли std:: exchange быть быстрее, чем std:: swap?

Предварительный просмотр: Нет. В лучшем случае exchange будет таким же быстрым, как swap. В худшем случае это может быть медленнее.

Рассмотрим такой тест:

using T = int;

void
test_swap(T& x, T& y)
{
    using std::swap;
    swap(x, y);
}

void
test_exchange(T& x, T& y)
{
    y = std::exchange(x, std::move(y));
}

Что генерирует более быстрый код?

Используя clang -O3, они оба генерируют идентичный код (за исключением искаженных имен функций):

__Z9test_swapRiS_:                      ## @_Z9test_swapRiS_
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    movl    (%rdi), %eax
    movl    (%rsi), %ecx
    movl    %ecx, (%rdi)
    movl    %eax, (%rsi)
    popq    %rbp
    retq
    .cfi_endproc

Для некоторого произвольного типа X, который не имеет специализированной функции swap, оба теста будут генерировать один вызов X(X&&) (предполагая, что элементы перемещения существуют для X), и два вызова X& operator=(X&&):

test_swap

__Z9test_swapR1XS0_:                    ## @_Z9test_swapR1XS0_
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    pushq   %r15
    pushq   %r14
    pushq   %rbx
    pushq   %rax
Ltmp3:
    .cfi_offset %rbx, -40
Ltmp4:
    .cfi_offset %r14, -32
Ltmp5:
    .cfi_offset %r15, -24
    movq    %rsi, %r14
    movq    %rdi, %rbx
    leaq    -32(%rbp), %r15
    movq    %r15, %rdi
    movq    %rbx, %rsi
    callq   __ZN1XC1EOS_
    movq    %rbx, %rdi
    movq    %r14, %rsi
    callq   __ZN1XaSEOS_
    movq    %r14, %rdi
    movq    %r15, %rsi
    callq   __ZN1XaSEOS_
    addq    $8, %rsp
    popq    %rbx
    popq    %r14
    popq    %r15
    popq    %rbp
    retq
    .cfi_endproc

test_exchange

    .globl  __Z13test_exchangeR1XS0_
    .align  4, 0x90
__Z13test_exchangeR1XS0_:               ## @_Z13test_exchangeR1XS0_
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Ltmp6:
    .cfi_def_cfa_offset 16
Ltmp7:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp8:
    .cfi_def_cfa_register %rbp
    pushq   %r14
    pushq   %rbx
    subq    $16, %rsp
Ltmp9:
    .cfi_offset %rbx, -32
Ltmp10:
    .cfi_offset %r14, -24
    movq    %rsi, %r14
    movq    %rdi, %rbx
    leaq    -24(%rbp), %rdi
    movq    %rbx, %rsi
    callq   __ZN1XC1EOS_
    movq    %rbx, %rdi
    movq    %r14, %rsi
    callq   __ZN1XaSEOS_
    leaq    -32(%rbp), %rsi
    movq    %r14, %rdi
    callq   __ZN1XaSEOS_
    addq    $16, %rsp
    popq    %rbx
    popq    %r14
    popq    %rbp
    retq
    .cfi_endproc

Снова почти тот же код.

Но для типов с оптимизированным swap, test_swap, вероятно, генерирует гораздо более совершенный код. Рассмотрим:

using T = std::string;

(используя libС++)

test_swap

    .globl  __Z9test_swapRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_
    .align  4, 0x90
__Z9test_swapRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_: ## @_Z9test_swapRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    movq    16(%rdi), %rax
    movq    %rax, -8(%rbp)
    movq    (%rdi), %rax
    movq    8(%rdi), %rcx
    movq    %rcx, -16(%rbp)
    movq    %rax, -24(%rbp)
    movq    16(%rsi), %rax
    movq    %rax, 16(%rdi)
    movq    (%rsi), %rax
    movq    8(%rsi), %rcx
    movq    %rcx, 8(%rdi)
    movq    %rax, (%rdi)
    movq    -8(%rbp), %rax
    movq    %rax, 16(%rsi)
    movq    -24(%rbp), %rax
    movq    -16(%rbp), %rcx
    movq    %rcx, 8(%rsi)
    movq    %rax, (%rsi)
    popq    %rbp
    retq
    .cfi_endproc

test_exchange

    .globl  __Z13test_exchangeRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_
    .align  4, 0x90
__Z13test_exchangeRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_: ## @_Z13test_exchangeRNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEES6_
Lfunc_begin0:
    .cfi_startproc
    .cfi_personality 155, ___gxx_personality_v0
    .cfi_lsda 16, Lexception0
## BB#0:                                ## %entry
    pushq   %rbp
Ltmp9:
    .cfi_def_cfa_offset 16
Ltmp10:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp11:
    .cfi_def_cfa_register %rbp
    pushq   %r14
    pushq   %rbx
    subq    $32, %rsp
Ltmp12:
    .cfi_offset %rbx, -32
Ltmp13:
    .cfi_offset %r14, -24
    movq    %rsi, %r14
    movq    %rdi, %rbx
    movq    16(%rbx), %rax
    movq    %rax, -32(%rbp)
    movq    (%rbx), %rax
    movq    8(%rbx), %rcx
    movq    %rcx, -40(%rbp)
    movq    %rax, -48(%rbp)
    movq    $0, 16(%rbx)
    movq    $0, 8(%rbx)
    movq    $0, (%rbx)
Ltmp3:
    xorl    %esi, %esi
                                        ## kill: RDI<def> RBX<kill>
    callq   __ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE7reserveEm
Ltmp4:
## BB#1:                                ## %_ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE5clearEv.exit.i.i
    movq    16(%r14), %rax
    movq    %rax, 16(%rbx)
    movq    (%r14), %rax
    movq    8(%r14), %rcx
    movq    %rcx, 8(%rbx)
    movq    %rax, (%rbx)
    movq    $0, 16(%r14)
    movq    $0, 8(%r14)
    movq    $0, (%r14)
    movw    $0, (%r14)
Ltmp6:
    xorl    %esi, %esi
    movq    %r14, %rdi
    callq   __ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE7reserveEm
Ltmp7:
## BB#2:                                ## %_ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEaSEOS5_.exit
    movq    -32(%rbp), %rax
    movq    %rax, 16(%r14)
    movq    -48(%rbp), %rax
    movq    -40(%rbp), %rcx
    movq    %rcx, 8(%r14)
    movq    %rax, (%r14)
    xorps   %xmm0, %xmm0
    movaps  %xmm0, -48(%rbp)
    movq    $0, -32(%rbp)
    leaq    -48(%rbp), %rdi
    callq   __ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEED1Ev
    addq    $32, %rsp
    popq    %rbx
    popq    %r14
    popq    %rbp
    retq
LBB1_3:                                 ## %terminate.lpad.i.i.i.i
Ltmp5:
    movq    %rax, %rdi
    callq   ___clang_call_terminate
LBB1_4:                                 ## %terminate.lpad.i.i.i
Ltmp8:
    movq    %rax, %rdi
    callq   ___clang_call_terminate
Lfunc_end0:
    .cfi_endproc
    .section    __TEXT,__gcc_except_tab
    .align  2
GCC_except_table1:
Lexception0:
    .byte   255                     ## @LPStart Encoding = omit
    .byte   155                     ## @TType Encoding = indirect pcrel sdata4
    .asciz  "\242\200\200"          ## @TType base offset
    .byte   3                       ## Call site Encoding = udata4
    .byte   26                      ## Call site table length
Lset0 = Ltmp3-Lfunc_begin0              ## >> Call Site 1 <<
    .long   Lset0
Lset1 = Ltmp4-Ltmp3                     ##   Call between Ltmp3 and Ltmp4
    .long   Lset1
Lset2 = Ltmp5-Lfunc_begin0              ##     jumps to Ltmp5
    .long   Lset2
    .byte   1                       ##   On action: 1
Lset3 = Ltmp6-Lfunc_begin0              ## >> Call Site 2 <<
    .long   Lset3
Lset4 = Ltmp7-Ltmp6                     ##   Call between Ltmp6 and Ltmp7
    .long   Lset4
Lset5 = Ltmp8-Lfunc_begin0              ##     jumps to Ltmp8
    .long   Lset5
    .byte   1                       ##   On action: 1
    .byte   1                       ## >> Action Record 1 <<
                                        ##   Catch TypeInfo 1
    .byte   0                       ##   No further actions
                                        ## >> Catch TypeInfos <<
    .long   0                       ## TypeInfo 1
    .align  2

Итак, никогда не используйте std::exchange для выполнения swap.

Ответ 2

Короткий ответ: он не нужен, но он полезен.

Длинный ответ:

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

Перенос семантики и шаблонов выражений были разработаны для ускорения определенных областей С++, главным образом путем устранения ненужных копий и временных значений. В случае семантики перемещения это резко увеличивало скорость числовых вычислений в основном без затрат для конечного пользователя; как только они были поддержаны, и семантика выбора по умолчанию была добавлена ​​к объектам, многие распространенные применения в численном выражении стали быстрее, просто позволяя уже существующим библиотекам прекратить делать полные копии для общих операций. Из-за драматического успеха семантики перемещения другие области языка, традиционно доминирующие в идиомах, таких как копирование и своп, рассматриваются в новом свете и стандартизированы. std:: array - пример одного такого снижения силы; где, как ранее, большинство стандартных авторов сказали бы "использовать векторы, они делают все, что вам нужно, и кто волнуется, если они медленные", теперь вызов предназначен для более специализированных и конкретных контейнеров, таких как статический std:: array.

Так зачем менять?

Если вы посмотрите boost:: swap, вы поймете, почему у нас есть потребность в новом операторе свопинга: Аргумент зависимый поиск затруднен чтобы инкапсулировать и использовать правильно, и приводит к взрыву необходимых функций, где, поскольку основная идея простого предоставления функции swap-элемента довольно проста. Наличие оператора, который может это сделать, и предоставление оператора обмена по умолчанию, который затем может использоваться для стандартного копирования и замены, является огромным увеличением производительности.

Почему? Поскольку std:: swap определяется в терминах MoveConstructible и MoveAssignable в С++ 11 (ранее построение копии и назначение копии, на С++ 98); это требует трех ходов и временного (намного быстрее, чем полные копии, необходимые на С++ 98). Это общий и довольно быстрый, но не такой быстрый, как пользовательский своп (который может быть в 2-3 раза быстрее, удалив временный и один ход во многих случаях). std:: swap также зависит от типа, который не является конструктивным и невозможен; можно подумать о классе, который не является, но который может предоставлять гарантии исключения при пользовательском свопе, что позволяет избежать поведения undefined.

ADL и std:: swap могут взаимодействовать очень красиво, но синтаксис несколько нечетный; вы добавляете

using std::swap;

чтобы ваша функция вызывала swap и предоставляла бесплатную функцию друга в качестве специализации свопа. Замена этого странного неявного углового случая ADL с явным оператором будет проще на глазах, но, как уже отмечалось, он кажется мертвым по прибытии.

Exchange - очень похожий зверь

Используя std:: move в обмен, полная копия больше не нужна. Используя универсальную ссылку для new_val, новое значение может быть прекрасно переадресовано или перемещено непосредственно в новое место. Теоретически обмен может работать с абсолютно нулевыми копиями, всего двумя ходами.

В резюме

Почему это необходимо? Поскольку он быстро и не требует затрат для конечных пользователей и расширяет С++ в качестве полезной альтернативы Fortran в научных вычислениях.