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

Я узнал, что операция 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;
}

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

В нормальном cpu нормальная своп для двух целых переменных выглядит как

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

4 ops, 2 загрузки, 2 магазина и самая длинная зависимость 2

В любом случае:

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

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

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

Ответ 3

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

Ответ 4

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

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

EDIT:

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

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

Ответ 5

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

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

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

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

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