Есть ли смысл менять две переменные без использования третьего?

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

x ^= y;
y ^= x;
x ^= y;

x = x + y
y = x - y
x = x - y

В классе профессор упомянул, что они были популярны 20 лет назад, когда память была очень ограниченной и до сих пор используется в высокопроизводительных приложениях. Это правда? Мое понимание того, почему бессмысленно использовать такие методы, заключается в следующем:

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

Так всегда ли хорошее время, чтобы не менять третью переменную? Это быстрее?

По сравнению с другими, это метод, который использует XOR против метода, который использует +/- быстрее? У большинства архитектур есть блок для сложения/вычитания и XOR, так что это не означает, что они имеют одинаковую скорость? Или только потому, что у процессора есть блок для операции, это не значит, что они имеют одинаковую скорость?

Ответ 1

Эти методы по-прежнему важны для программистов, которые пишут прошивку вашей средней стиральной машины или около того. Многие из таких аппаратов по-прежнему работают на процессорах Z80 или аналогичных устройствах, часто с объемом памяти не более 4 КБ. Вне этой сцены, зная эти алгоритмические "хитрости", как вы говорите, так же хорошо, как и нет реального практического использования.

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

Ответ 2

Нет никакого смысла. Это попытка продемонстрировать ум. Учитывая, что во многих случаях он не работает (с плавающей запятой, указатели, структуры), он не запрашивает и использует три зависимые операции, которые будут намного медленнее, чем просто обмен значениями, это абсолютно бессмысленно и демонстрирует неудачу на самом деле быть умной.

Вы правы, если это было быстрее, тогда оптимизация компиляторов будет определять шаблон при обмене двумя номерами и заменять его. Это достаточно легко сделать. Но компиляторы действительно замечают, когда вы обмениваетесь двумя переменными и вообще не создаете никакого кода, но начинаете использовать различные переменные после этого. Например, если вы меняете x и y, напишите + = x; b + = y; компилятор может просто изменить это на + = y; b + = x;, С другой стороны, шаблон xor или add/subtract не будет распознаваться, потому что он настолько редок и не будет улучшен.

Ответ 3

Да, есть, особенно в коде сборки.

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

Я фактически использовал 3-х хост для обмена регистром с ячейкой памяти на критическом пути высокопроизводительных ручных кодовых подпрограмм для x86, где давление в регистре было высоким, и не было (lock safe!) место для установки темпа. (на X86, полезно знать, что инструкция XCHG в память имеет высокую стоимость, связанную с ней, поскольку она включает в себя ее собственную блокировку, эффект которой мне не нужен. Учитывая, что x86 имеет код префикса LOCK, это было действительно ненужные, но исторические ошибки просто таковы).

Мораль: каждое решение, как бы уродливым выглядело, когда оно стояло изолированно, скорее всего, имеет какое-то применение. Хорошо знать их; вы всегда можете не использовать их, если они не подходят. И где они полезны, они могут быть очень эффективными.

Ответ 4

Такая конструкция может быть полезна для многих членов микроконтроллеров серии PIC, которые требуют, чтобы почти все операции проходили через один накопитель ( "рабочий регистр" ) [обратите внимание, что хотя это иногда может быть помехой, тот факт, что он только для каждой инструкции для кодирования одного регистра и бита адресата, а не двух адресов регистра, позволяет PIC иметь гораздо больший рабочий набор, чем другие микроконтроллеры].

Если рабочий регистр содержит значение и ему необходимо поменять его содержимое на содержимое ОЗУ, альтернатива:

xorwf other,w  ; w=(w ^ other)
xorwf other,f  ; other=(w ^ other)
xorwf other,w  ; w=(w ^ other)

будет

movwf temp1     ; temp1 = w
movf  other,w   ; w = other
movwf temp2     ; temp2 = w
movf  temp1,w   ; w = temp1 [old w]
movwf other     ; other = w
movf  temp2,w   ; w = temp2 [old other]

Три инструкции и отсутствие дополнительного хранилища по сравнению с шестью инструкциями и двумя дополнительными регистрами.

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

subwf other,w    ; w = other-w
btfss STATUS,C   ; Skip next instruction if carry set (other >= W)
 subwf other,f   ; other = other-w [i.e. other-(other-oldW), i.e. old W]

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

Ответ 5

Эти трюки вряд ли будут полезны, если вы хотите обменять два целых слова в памяти или два целых регистра. Тем не менее вы можете воспользоваться ими, если у вас нет свободных регистров (или только один бесплатный регистр для обмена с памятью на память), и нет никакой "обменной" инструкции (например, при замене двух регистров SSE в x86) или "обмена", слишком дорого (например, регистр-память xchg в x86), и невозможно избежать обмена или понижения давления в регистре.

Но если ваши переменные являются двумя битовыми полями в одном слове, модификация подхода с 3-XOR может быть хорошей идеей:

y = (x ^ (x >> d)) & mask
x = x ^ y ^ (y << d)

Этот фрагмент из Кнута "Искусство компьютерного программирования" vol. 4а. сек. 7.1.3. Здесь y является лишь временной переменной. Оба битовых поля для обмена находятся в x. mask используется для выбора битового поля, d - расстояние между битовыми полями.

Также вы можете использовать трюки, подобные этому, в доказательствах твердости (для сохранения планарности). См. Например, кроссоверный гаджет из этот слайд (стр. 7). Это из недавних лекций в "Алгоритмические нижние границы" проф. Эрик Демейн.

Ответ 6

Конечно, все же полезно знать. Какая альтернатива?

c = a
a = b
b = c

три операции с тремя ресурсами, а не три операции с двумя ресурсами?

Уверен, что набор команд может иметь обмен, но только вступает в игру, если вы 1) записываете сборку или 2) оптимизатор показывает это как своп, а затем кодирует эту инструкцию. Или вы можете сделать встроенную сборку, но это не переносимо и боль в обслуживании, если вы вызвали функцию asm, тогда компилятор должен настроить для вызова, сжигающего кучу больше ресурсов и инструкций. Хотя это может быть сделано, вы вряд ли сможете использовать функцию набора инструкций, если язык не имеет операции свопинга.

Теперь среднему программисту НЕ НУЖНО знать это сейчас больше, чем в тот же день, люди будут bash такого рода преждевременной оптимизации, и если вы не знаете трюк и часто его используете, если код не зарегистрирован, то это не является очевидным, так что это плохое программирование, потому что оно не читается и не поддается контролю.

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