Как быстро std:: swap для целых типов?

STL реализует общую функцию std::swap для замены двух значений. Его можно представить следующим образом:

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

Однако существует алгоритм замены XOR для замены двух целых чисел (http://en.wikipedia.org/wiki/XOR_swap_algorithm):

void swap_u( size_t& x, size_t& y )
{
   x = x^y;
   y = x^y;
   x = x^y;
}

Мои вопросы:

Это оптимизация в настоящее время (на x86 или arm)?
Поддерживает ли стандарт С++ такую оптимизацию?
Существуют ли какие-либо реальные реалии STL в дикой природе, которые имеют std::swap специализацию для целых чисел?

Ответ 1

В подавляющем большинстве ситуаций сводка XOR не является оптимизацией.

Смотрите эту запись wiki.

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

На процессоре, где кодировка набора команд разрешает кодировку XOR кодироваться в меньшем количестве байтов,

В области с высоким регистрационным давлением это может позволить распределителю регистров избежать проливания регистра.

В микроконтроллерах, где доступная оперативная память очень ограничена.
Поскольку эти ситуации редки, большинство оптимизирующих компиляторов не генерируют код обмена XOR.

Также обратите внимание, что ваша реализация обмена XOR нарушена. Вы должны сначала проверить, что x и y не являются псевдонимом. Эта проверка, безусловно, заставит замену XOR медленнее.

Мне не известно о какой-либо стандартной реализации библиотеки, использующей замену XOR.

Обратите внимание, что независимо от того, что реализует стандартная библиотека, если обмен XOR был действительно быстрее обычного обмена, тогда оптимизация компиляторов сделает оптимизацию глазок, чтобы превратить ее в XOR своп. Это действительно случай, просто позволяющий компилятору выбрать для вас.

Ответ 2

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

XOR swap также не особенно эффективен, поскольку он имеет последовательные зависимости, поэтому он всегда будет занимать не менее трех циклов команд. Использование простой замены с временным имеет меньше зависимостей, что позволяет некоторым parallelism на современных суперскалярных CPU - на некоторых процессорах его можно даже реализовать в одной инструкции, но даже без специальных инструкций он вполне может выполняться за два цикла.

Ответ 3

На X86 тройная сводка XOR между ячейками памяти (а не регистры CPU) принимает те же самые процессорные циклы, что и тройная копия. Они могут быть еще меньше, если временным является регистр.