Этот алгоритм перестановки значений XOR все еще используется или полезен?

Когда я только начал работать, программист на мэйнфреймах показал мне, как они переключаются на значения без использования традиционного алгоритма:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

То, что они использовали для обмена двумя значениями - от битового к большому буферу - было:

a = 0xBABE
b = 0xFADE

a = a XOR b
b = b XOR a
a = a XOR b

в настоящее время

b == 0xBABE
a == 0xFADE

который поменял содержимое 2 объектов без необходимости в третьем временном пространстве.

Мой вопрос: этот алгоритм обмена XOR все еще используется и где он все еще применим.

При использовании xorswapсуществует опасность предоставления одной и той же переменной в качестве обоих аргументов функции, которая обнуляет указанную переменную, потому что она xorсама с собой, что превращает все биты в ноль. Конечно, это само по себе может привести к нежелательному поведению независимо от используемого алгоритма, но поведение может быть неожиданным и неочевидным на первый взгляд.

Традиционно xorswapиспользовался для низкоуровневых реализаций для обмена данными между регистрами. На практике есть лучшие альтернативы для замены переменных в регистрах. Например, в Intel x86 есть XCHGинструкция, которая меняет содержимое двух регистров. Много раз компилятор выясняет семантику такой функции (он меняет содержимое передаваемых ей значений) и может при необходимости вносить свои собственные оптимизации, поэтому попытка оптимизировать что-то столь же тривиальное, как функция подкачки, на самом деле ничего вам не дает на практике. Лучше всего использовать очевидный метод, если только нет доказанной причины, по которой было бы хуже сказать xorswap в проблемной области.

Ключ к ответу в вопросе - «работа программистом на мэйнфрейме» - за несколько дней до компилятора. Когда люди смирились с инструкциями по сборке и созданными вручную точными решениями для конкретного компонента оборудования (которое может работать или не работать на другой модели того же компьютера), такие вопросы, как синхронизация жестких дисков и памяти барабана, влияли на то, как код был написано - прочитайте «Историю Мела», если чувствуете необходимость испытывать ностальгию).

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

Те дни прошли. Хитрость в обмене двумя вещами без использования третьей - это хитрость. Память и регистры многочисленны в современных вычислениях, и люди больше не пишут ассемблер. Мы научили всех наших приемов нашим компиляторам, и они справляются с этим лучше, чем мы. Скорее всего, компилятор сделал что-то даже лучше, чем мы бы сделали. В большинстве случаев иногда нам нужно по какой-то причине записывать сборку в некотором внутреннем узком цикле ... но это не для сохранения регистра или слова памяти.

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

Это будет работать? Да.

Вы должны использовать это? Нет.

Это своего рода микро-оптимизации будет иметь смысл , если:

• Вы посмотрели на код, сгенерированный компилятором, для простого способа сделать это (назначение и временный) и решили, что подход XOR генерирует более быстрый код

• Вы профилировали свое приложение и обнаружили, что стоимость простого подхода перевешивает ясность кода (и, как следствие, экономию в обслуживании)

Прежде всего, если вы не сделали это измерение, вы должны доверять компилятору. Когда семантика того, что вы пытаетесь сделать, ясна, компилятор может сделать много хитростей, включая перестановку доступа к переменным так, чтобы своп вообще не требовался, или встраивание любых инструкций машинного уровня, обеспечивающих самый быстрый своп для данного типа данных. Такие «хитрости», как своп XOR, затрудняют компилятору видеть, что вы пытаетесь сделать, и, следовательно, уменьшают возможность применения такой оптимизации.

Во-вторых, что вы получаете за дополнительную сложность? Даже если вы измерили и нашли XOR-подход быстрее, достаточно ли это влияния, чтобы оправдать менее четкий подход? Откуда вы знаете?

Наконец, вы должны посмотреть, есть ли стандартная функция подкачки для вашей платформы / языка - например, C ++ STL предоставляет функцию подстановки шаблонов, которая, как правило, будет высоко оптимизирована для вашего компилятора / платформы.

Мой коллега сообщил, что это базовая уловка, которую он преподавал в университете для программиста автоматизированных систем. Многие такие системы являются встроенными с ограниченными ресурсами, и им может не хватить свободного регистра для хранения временной стоимости; в этом случае такой хитрый обмен (или его аналог с сложением и вычитанием) становится жизненно важным, поэтому все еще используется.

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

В x86 инструкции xchg и cmpxchg удовлетворяют потребности в большинстве случаев, но RISC обычно не покрываются ими (за исключением Sparc).