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

10

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

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

Но реализация swap всего, что я могу найти в интернете, по сути такова:

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

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

Вы запустили свой тест с включенной оптимизацией? R. Martinho Fernandes
@ phresnel Боже, я считаю, что никогда не принимаю ответ, потому что не знаю, как его принять. user955249
Просто предположение: по крайней мере, x86 процессоры имеютXCHG инструкция, которая быстрее, чем три XOR. Joulukuusi
@Joulukuusi Инструкция XCHG на x86 никогда не предназначалась для замены подкачки. Он имеет неявный префикс блокировки, если используется для операндов памяти, он используется как инструмент для синхронизации.XCHG reg, reg можно использовать, возможно, хотя я сомневаюсь, что это когда-либо понадобится - переименование регистров происходит еще быстрее. Я написал несколько k строк сборки, я никогда не чувствовал желание использоватьxchg для обмена значениями. Gunther Piez
Ваш xor swap глючит. PlasmaHH

Ваш Ответ

5   ответов
0

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

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

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

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

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

2

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

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

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

I tested it on VC++ 2010 and the first one is done the job more quickly(and is more quickly than std::swap).

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

4

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

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededyouError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
10

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

На обычном процессоре обычный обмен двумя целочисленными переменными выглядит следующим образом:

$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 происходит медленнее, даже если это применимо.

Error: User Rate Limit ExceededRename(a1,b2), Rename(b1,a2)Error: User Rate Limit Exceeded
18

I've learned that Xor operation can be used to implement effective swap function

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

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

int a = 1;
swap(a,a);
std::cout << a << '\n';

Похожие вопросы