Почему swap не использует операцию Xor в C++

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

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

Но реализация свопа, которую я нашел в Интернете, по сути выглядит так:

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

Кажется, что компилятор не сгенерировал один и тот же код для двух вышеприведенных форм, потому что я тестировал его на VC++ 2010, и первый выполнил работу быстрее, чем std::swap. Есть ли портативные или какие-либо другие проблемы с первым? Не стесняйтесь исправлять любую мою ошибку, потому что я не являюсь носителем английского языка и плохо разбираюсь в C++.

(Примечание редактора: скорее всего, этот тест был выполнен с неоптимизированной отладочной сборкой, а не с выпускной сборкой, в которой std::swap может быть встроен. Сравнение отладочных сборок бессмысленно. Компиляторы обычно не оптимизируют xor-swap во что-то более эффективное.)


c++ swap xor micro-optimization premature-optimization
person Community    schedule 11.05.2012    source источник
comment
Просто предположение: по крайней мере процессоры x86 имеют XCHG инструкция, которая быстрее, чем три операции XOR.   -  person Joulukuusi    schedule 11.05.2012
comment
Вы запускали тест с включенной оптимизацией?   -  person R. Martinho Fernandes    schedule 11.05.2012
comment
@Joulukuusi Инструкция XCHG на x86 никогда не предназначалась для замены подкачки. Он имеет неявный префикс блокировки, если используется в операндах памяти, он используется как инструмент для синхронизации. XCHG reg, reg можно было бы использовать, хотя я сомневаюсь, что это когда-либо понадобится - переименование регистров еще быстрее. Я написал несколько тысяч строк на ассемблере, и у меня никогда не возникало желания использовать xchg для замены значений.   -  person Gunther Piez    schedule 11.05.2012
comment
@phresnel о боже, я обнаружил, что никогда не принимаю ответ, потому что не знаю, как его принять.   -  person    schedule 11.05.2012
comment
@drhirsch, спасибо! Оказалось, что gcc оптимизирует вторую функцию подкачки до нескольких movs на моей машине.   -  person Joulukuusi    schedule 11.05.2012
comment
Связанный вопрос Странное поведение подкачки XOR при обнулении данных   -  person Bo Persson    schedule 11.05.2012

Ответы (5)


arrow_upward
20
arrow_downward

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

Боюсь, вы неправильно учились. Подкачка XOR устарела: если она когда-либо была надежно быстрее, чем использование временного значения, то ее не должно быть на современных компиляторах и процессорах (где под «современными» я имею в виду примерно последние 20 или более лет). Вы говорите, что это было быстрее для вас, возможно, вам следует показать свой тестовый код и посмотреть, получают ли другие такие же результаты.

Помимо того, что ваш код вообще работает только с целочисленными типами, в нем есть фундаментальная ошибка. Попробуйте это с вашей версией подкачки:

int a = 1;
swap(a,a);
std::cout << a << '\n';
person Steve Jessop    schedule 11.05.2012

arrow_upward
11
arrow_downward

И эффективность зависит от того, где вы его используете.

На обычном процессоре обычный обмен для двух целочисленных переменных выглядит так

$1 <- a
$2 <- b
a <- $2
b <- $1

4 операции, 2 загрузки, 2 хранилища и самая длинная зависимость 2

В xor пути:

$1 <- a
$2 <- b
$3 <- $1 ^ $2
$4 <- $3 ^ $2
$5 <- $3 ^ $4
a <- $5
b <- $4

7 операций, 2 загрузки, 2 хранилища, 3 логики и самая длинная зависимость 4

Так что, по крайней мере, обычный обмен с помощью xor медленнее, даже когда это применимо.

person BlueWanderer    schedule 11.05.2012
comment
С современным компилятором SSA первое еще проще: Rename(a1,b2), Rename(b1,a2) - не отдельная инструкция процессора, а просто бухгалтерская штука для компилятора. Какая переменная попала в какой регистр? - person MSalters; 12.05.2012

arrow_upward
4
arrow_downward

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

person R. Martinho Fernandes    schedule 11.05.2012
comment
Однако вы всегда можете предложить перегрузки/специализацию для подходящих типов. - person Flexo; 11.05.2012
comment
Однако вы можете делать злые броски. - person Sebastian Mach; 11.05.2012
comment
@phresnel не в стандарте, надеюсь :) - person R. Martinho Fernandes; 11.05.2012
comment
Однако вы можете добавить специализацию самостоятельно, поэтому стандартная библиотека для этого не нужна. Могли бы, конечно, но неясно, действительно ли это стоит затраченных усилий. - person deong; 11.05.2012
comment
@deong нет, ты не можешь. Вы можете специализироваться только на пользовательских типах. Однако это могут сделать только разработчики стандартных библиотек. - person R. Martinho Fernandes; 11.05.2012
comment
@R.MartinhoFernandes, мне это нравится... просто нравится :)) - person johnathan; 11.05.2012
comment
@R.MartinhoFernandes: Скорее всего, ничего переносимого, но я уверен, что вы (как разработчик библиотеки) можете сделать это в соответствии с реализацией. (классный сомнительный трюк с каламбуром) - person Sebastian Mach; 11.05.2012
comment
Обертывание его в блоке пространства имен std {} всегда работало, но, по общему признанию, это явно не разрешено стандартом. Хотя это странное ограничение. Очевидная реализация, которая допускает специализацию для пользовательских типов, также допускает встроенные типы — специализация шаблона обычно не признает различий. Таким образом, поставщики должны будут приложить все усилия, чтобы предотвратить это, если, конечно, я не упустил что-то очевидное. - person deong; 12.05.2012
comment
@R.MartinhoFernandes, мне очень любопытно, почему пользователи не могут добавлять специализации?? Не могли бы вы объяснить? - person awakened; 13.06.2021

arrow_upward
2
arrow_downward

Конечно, потому что трюк xor работает для типов POD.

Если вы хотите поменять местами два определяемых пользователем сложных типа, xor не сработает. Вам понадобится глубокая копия, а не прямая копия необработанной памяти, что делает xor.

РЕДАКТИРОВАТЬ:

Я протестировал его на VC++ 2010, и первый работает быстрее (и быстрее, чем std::swap).

Действительно? Вы компилировали в режиме отладки? Каковы ваши результаты?

person Luchian Grigore    schedule 11.05.2012

arrow_upward
0
arrow_downward

Во-первых, оператор XOR определен только для целочисленных типов.

Во-вторых, вы можете использовать приемы приведения типов, чтобы привести нецелочисленные типы к интегральной форме.

Но в-третьих, для всех типов POD, кроме POD, это приводит к неопределенному поведению,

и, в-четвертых, для типов, которые не имеют хорошо поддерживаемого размера/выравнивания для операции XOR, потребуется больше возни (циклы являются наименьшим злом).

Вы можете перегрузить operator^, но это будет означать, что каждая специализация swap() должна обеспечивать его существование или определять его, и это может привести к большей путанице при поиске имени, чем того стоило бы. И, конечно же, если такой оператор уже существует, он не обязательно имеет правильное поведение, и вы можете получить худшую производительность, потому что такая перегрузка не обязательно inline или constexpr.

person Sebastian Mach    schedule 11.05.2012